Fwd: Factorial improvements

Torbjorn Granlund tege at swox.com
Thu Sep 15 22:38:05 CEST 2005

Paul.Zimmermann at loria.fr (Paul Zimmermann) writes:

  the best known algorithm is the one from Schönhage, Grotefeld and Vetter.
  See the implementation below. Timings on a 1.7Ghz Athlon with gmp-4.1.4:
  % ./fac_ui 100000
  mpz_fac_ui took 439ms
  mpz_fac_ui2 took 250ms
  % ./fac_ui 1000000
  mpz_fac_ui took 10641ms
  mpz_fac_ui2 took 5717ms
  % ./fac_ui 2000000
  mpz_fac_ui took 27371ms
  mpz_fac_ui2 took 13764ms
  % ./fac_ui 5000000
  mpz_fac_ui took 99720ms
  mpz_fac_ui2 took 42751ms
Nice speedups!
Here is the current GMP code, contributed by Jason Moxham:

-------------- next part --------------
A non-text attachment was scrubbed...
Name: fac_ui.c
Type: application/octet-stream
Size: 11572 bytes
Desc: not available
Url : http://gmplib.org/list-archives/gmp-discuss/attachments/20050915/213ba335/fac_ui-0001.obj
-------------- next part --------------


More information about the gmp-discuss mailing list