Update: Schönhage 's algorithm for fast integer GCD

[Niels Möller]

nisse at lysator.liu.se (Niels Möller) writes:

> ;-) I'll run the benchmark on my non-ancient x86 machine at work too.
> But for the earlier incarnations of the code, the thresholds turned
> out to be quite similar for the two machines.

Ok, here's the interesting part of the figures for x86. Benchmark run
on a "Mobile Intel(R) Pentium(R) 4 - M CPU 2.20GHz".

Gcd of fibonacci numbers.

limbs    gcd     fgcd    gcd/fgcd
...
  686   4.17ms   6.25ms  0.67             *
 1029   9.09ms  10.00ms  0.91              *
 1544  18.33ms  18.33ms  1.00               *
 2316  40.00ms  33.33ms  1.20               *
...
59333  26.02s    4.01s   6.49                       *
88999  79.20s    7.06s  11.22                         *
Gcd of pseudorandom numbers.

limbs    gcd     fgcd    gcd/fgcd
...
  391   1.43ms   1.75ms  0.81              *
  587   2.94ms   3.12ms  0.94              *
  879   6.25ms   5.26ms  1.19               *
 1318  14.29ms   9.09ms  1.57                *
...
50646  19.35s    2.05s   9.44                        *
75969  51.71s    3.63s  14.25                          *

gprof top ten:

  %   cumulative   self              self     total
 time   seconds   seconds    calls  ms/call  ms/call  name
 30.96      1.28     1.28 25820723     0.00     0.00  div2
 23.61      2.27     0.98   889945     0.00     0.00  nhgcd2
  8.55      2.62     0.35   514972     0.00     0.00  nhgcd_gcd_lehmer
  4.82      2.82     0.20   538837     0.00     0.00  nhgcd2_mul
  3.86      2.98     0.16  1707522     0.00     0.00  nhgcd2_fix
  3.37      3.12     0.14 17401552     0.00     0.00  nhgcd_quotient_stack_push_1
  2.89      3.24     0.12    94761     0.00     0.02  nhgcd_lehmer
  2.89      3.36     0.12    91557     0.00     0.00  nhgcd_final
  2.17      3.45     0.09  1031398     0.00     0.00  nhgcd_update_uv
  1.93      3.53     0.08   165415     0.00     0.00  nhgcd_mul

div2 and hgcd2 are still operations on two-limb values.

nhgcd_gcd_lehmer and nhgcd_lehmer are basecases for gcd and hgcd, both
using nhgcd2.

hgcd2_mul and nhgcd2_fix use one-limb x n-limb multiplications.

Regards,
/Niels