Question about function failing with large number

[Dave Angel]

Anthony Papillion wrote:

> -----BEGIN PGP SIGNED MESSAGE-----
> Hash: SHA512
>
> So I'm using the function below to test a large (617 digit) number for
> primality. For some reason, when I execute the code, I get an error
> telling me:
>
> OverflowError: long int too large to convert to float

In general, you should quote the entire traceback.  it's no trouble in
this case, as the problem is clearly in the n**0.5 portion.  You should
also specify the Python version.  But it's a safe bet that you're using
2.x, since your print statements are illegal in 3.x
>
> The error is being thrown on this line:
>
> for x in range(3, int(n**0.5)+1, 2):
>
> The odd thing is that the error is not thrown every single time. I can
> run the function a few times, it will generate a large number (always
> the same length) and run it through the function. After I do this a
> few times, it fails with the error. I might get the error on the next
> few runs but then, all of a sudden, it functions again.
>
> Any ideas? The entire program, including the method, is below.
>
> #!/usr/bin/env python
>
> from random import getrandbits
>
> bits = 2048
>
> # Test if the number is a prime
> def isprime(n):
>
> 	# make sure n is a positive integer
> 	n = abs(int(n))
> 	# 0 and 1 are not primes
> 	if n < 2:
> 		return False
> 	# 2 is the only even prime number
> 	if n == 2:
> 		return True
> 	# all other even numbers are not primes
> 	if not n & 1:
> 		return False
> 	# range starts with 3 and only needs to go up the 		squareroot 		of 	n
> 	# for all odd numbers
> 	for x in range(3, int(n**0.5)+1, 2):
> 		if n % x == 0:
> 			return False
> 	return True
> 	
> a = getrandbits(bits)
> print "\nGenerated Number: ", a, "\n"
> print "Number of digits: ", len(str(a))
> isNumberPrime = isprime(a)
> if isNumberPrime == True:
> 	print "\nThis number is a prime.\n"
> else:
> 	print "\nThis number is not a prime.\n"
>
> Thanks!
> Anthony
>

The operator ** works by first converting its arguments to float.  if
the long value is too large for a Python float (which is a C double),
then you get this error.  You'll get the same one with math.sqrt().
Nothing you can do about that unless you want to write your own square
root function.

However, you can change your algorithm.  You'll need to anyway, since a
range that large would take a ridiculous amount of RAM, if it even was
willing to start.

The cure is to use a while loop, and test x*x agains the limit

while x*x < n:
    if n%x == 0:
        return False
    n+=2

BTW, I can't believe that getrandbits(2048) is going to be small enough
to 'work" for any noticeable probability.  So when you find it working,
perhaps you're using a smaller value for bits.

BTW, when you get this all done, you'll find that testing a prime of
600 digits is going to take an effectively infiinite time.  You need a
faster method.



-- 
DaveA