Infinite loop in mpz_probab_prime_p
Torbjorn Granlund
tege at swox.com
Fri Mar 4 16:23:52 CET 2005
"Darin Ohashi" <darin242 at hotmail.com> writes:
Yeah, I did some more experimentation overnight and found that eventually it
did complete. As long as it is expected to take that long then it is not a
bug.
It takes time O(n^2*log(n)), where n is the number of digits in the
number. This means that doubling the number of digits more than
quadruples the run time.
I'd estimate that your number needs 2 to 3 hours (depending on CPU
clock) on an Athlon64 or Opteron in 64-bit mode. Current Pentiums or
current 32-bit AMD processors will take perhaps 2-3 times longer.
Did you add a check for the potential overflow from ln2 = ln2*ln2 ?
For very very large integers this could be a problem.
That code is gone. Note however that overflow in that expression
isn't going to cause any miscomputation; it will only affect
performance.
It is an interesting problem to look for small divisors; what
algorithm and and what limits to use.
--
Torbjörn
More information about the gmp-bugs
mailing list