Paul.Zimmermann at loria.fr
Fri Sep 16 14:45:49 CEST 2005
Someone who claims to be Torbjo"rn Granlund said on the list:
If you got "orders of magnitude", i.e., >= 100 times improvement,
I bow and promise never to write any more arithmetic routines in
y life. But I'd be brash enough to suggest that you remember
I got the following speedup with my code (I claim to be Paul Zimmermann):
mermoz% ./fac_ui 40000000
mpz_fac_ui took 727056ms # reference gmp-4.1.4 code
mpz_fac_ui2 took 255384ms # my new code
This is only a 2.85-fold speedup, but when 40000000 goes to infinity,
I believe the 2.85 ratio goes to infinity too. Unfortunately my computer
has not enough memory to try...
I've also tried the "current GMP code" [*] and I get:
mermoz% ./fac_ui_gmp 40000000
mpz_fac_ui took 727820ms # reference gmp-4.1.4 code
mpz_fac_ui2 took 445347ms # current GMP code
I actually think the GMP 4.1.4 code is close to asymptically
optimal, but others have shown that a 2-3 fold speedup is
As far as I can see, both the gmp-4.1.4 code and the "current GMP code"
have complexity O(M(n) log(n)^2), whereas my implementation of Scho"nhage
and al.'s algorithm has complexity O(M(n) log(n)), so with a big enough
computer, it should be possible to get a speedup of >= 100.
More information about the gmp-discuss