benchmarks/bench2.txt

   1 Benchmark for Computer-Algebra Libraries
   2 ========================================
   3
   4 (jointly developed by the LiDIA and CLN developers, 1996)
   5
   6 A. Elementary integer computations
   7 B. Transcendental functions
   8 C. Elementary polynomial functions
   9 D. Polynomial factorization
  10
  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)
  15               x3 = 10^N+1
  16    Then time the following operations:
  17    1. Multiplication x1*x2,
  18    2. Division (with remainder) x1 / x2,
  19    3. integer_sqrt(x3),
  20    4. gcd(x1,x2),
  21 A'. (from Pari)
  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);}
  23
  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)
  27               x2 = sqrt(3)
  28               x3 = log(2)
  29    Then time the following operations:
  30    1. Multiplication x1*x2,
  31    2. Square root sqrt(x3),
  32    3. pi (once),
  33    4. Euler's constant C (once),
  34    5. e (once),
  35    6. exp(-x1),
  36    7. log(x2),
  37    8. sin(5*x1),
  38    9. cos(5*x1),
  39   10. asin(x3),
  40   11. acos(x3),
  41   12. atan(x3),
  42   13. sinh(x2),
  43   14. cosh(x2),
  44   15. asinh(x3),
  45   16. acosh(1+x3),
  46   17. atanh(x3).
  47
  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),
  55    3. gcd(p1(X),p2(X)).
  56
  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.]
  63