FAQ
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

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

- --
Anthony Papillion
Phone: 1.918.533.9699
SIP: 17772098750 at in.callcentric.com
XMPP: cypherpunk at patts.us

www.cajuntechie.org

## Search Discussions

• at Aug 13, 2013 at 12:42 pm ⇧ On Tue, Aug 13, 2013 at 1:12 PM, Anthony Papillion wrote:
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

The error is being thrown on this line:

for x in range(3, int(n**0.5)+1, 2):

Python's integers are unbounded, storing arbitrary precision. Python's
floats are limited to the range of the underlying IEEE implementation.
You'll have a certain cutoff above which your system bombs.

float(1<<1023)
8.98846567431158e+307
float(1<<1024)
Traceback (most recent call last):
File "<pyshell#68>", line 1, in <module>
float(1<<1024)
OverflowError: long int too large to convert to float

(The exact cutoff may depend on how your Python is built, I think;
that was running on a 32-bit Python on Windows.)

Everything else in your code will work, so your only problem is this
square rooting. So here's an alternative:

for x in range(3, n, 2):
div, mod = divmod(n, x)
if mod == 0:
return False
if div < n:
break

Once the quotient is lower than the divisor, you've passed the square
root. (Note the use of divmod to do a single division and return both
quotient and remainder. You could alternatively use // and % but it'd
divide twice.)

By the way, the "== True" in your final condition is redundant. Just
test "if isNumberPrime:", or even just "if isprime(a):". :) Though
with something like this that simply returns boolean, I'd be inclined
to make it return a bit more - for instance, it returns the first-seen
factor.

if n < 2:
return 1 # Only way this will ever return a non-prime integer
if n == 2:
return None # Prime!
if not n & 1:
return 2
# and inside the loop: "return x"

Rename the function to "iscomposite", because prime numbers return
None (false) and composites return a positive integer (true), and
you've just made the function that bit more useful. :)

ChrisA
• at Aug 13, 2013 at 3:33 pm ⇧ On 13/08/2013 13:42, Chris Angelico wrote:
On Tue, Aug 13, 2013 at 1:12 PM, Anthony Papillion wrote:
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

The error is being thrown on this line:

for x in range(3, int(n**0.5)+1, 2):
Python's integers are unbounded, storing arbitrary precision. Python's
floats are limited to the range of the underlying IEEE implementation.
You'll have a certain cutoff above which your system bombs.
float(1<<1023)
8.98846567431158e+307
float(1<<1024)
Traceback (most recent call last):
File "<pyshell#68>", line 1, in <module>
float(1<<1024)
OverflowError: long int too large to convert to float

(The exact cutoff may depend on how your Python is built, I think;
that was running on a 32-bit Python on Windows.)
[snip]
Here's a way to calculate the integer square root:

def int_sqrt(number):
root = 1

while True:
new_root = (root + number // root) // 2
if new_root == root:
break

root = new_root

return root

It's result is the largest integer whose square doesn't exceed the
original number.
• at Aug 13, 2013 at 5:01 pm ⇧ On Tue, Aug 13, 2013 at 4:33 PM, MRAB wrote:
Here's a way to calculate the integer square root:

Yes, but the actual value of the square root isn't needed. All that's
needed is to stop the loop once the sqrt is reached.

ChrisA
• at Aug 13, 2013 at 12:57 pm ⇧ 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

## Related Discussions

Discussion Overview
 group python-list categories python posted Aug 13, '13 at 12:12p active Aug 13, '13 at 5:01p posts 5 users 4 website python.org

### 4 users in discussion

Content

People

Support

Translate

site design / logo © 2021 Grokbase