1 Benchmark for Computer-Algebra Libraries
2 ========================================
4 (jointly developed by the LiDIA and CLN developers, 1996)
6 A. Elementary integer computations
7 B. Transcendental functions
8 C. Elementary polynomial functions
9 D. Polynomial factorization
11 A. Elementary integer computations:
12 The tests are run with N = 100, 1000, 10000, 100000 decimal digits.
13 Precompute x1 = floor((sqrt(5)+1)/2 * 10^(2N))
14 x2 = floor(sqrt(3) * 10^N)
16 Then time the following operations:
17 1. Multiplication x1*x2,
18 2. Division (with remainder) x1 / x2,
22 u=1;v=1;p=1;q=1;for(k=1..1000){w=u+v;u=v;v=w;p=p*w;q=lcm(q,w);}
24 B. Transcendental functions: The tests are run with a precision of
25 N = 100, 1000, 10000, 100000 decimal digits.
26 Precompute x1 = sqrt(2)
29 Then time the following operations:
30 1. Multiplication x1*x2,
31 2. Square root sqrt(x3),
33 4. Euler's constant C (once),
48 C. Univariate polynomials: The tests are run with degree N = 100, 1000, and
49 with coefficient bound M = 10^9, 10^20.
50 Precompute p1(X) = sum(i=0..2N, (floor(sqrt(5)*M*i) mod M)*(-1)^i * X^i)
51 p2(X) = sum(i=0..N, (floor(sqrt(3)*M*i) mod M) * x^i
52 Then time the following operations:
53 1. Multiplication p1(X)*p2(X),
54 2. Pseudo-division p1(X)*c^N = p2(X)*q(X)+r(X),
57 D. Factorization of univariate polynomials: The benchmark by J. von zur Gathen.
58 For N = 500, precompute p := smallest prime >= pi*2^N.
59 Then time the following operation:
60 1. Factorize X^N+X+1 mod p in the ring F_p[X].
61 [von zur Gathen: A Polynomial Factorization Challenge.
62 SIGSAM Bulletin 26,2 (1992), 22-24.]