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

  • Chris Angelico 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
  • MRAB 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.
  • Chris Angelico 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
  • Dave Angel 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 Navigation
viewthread | post
Discussion Overview
grouppython-list @
categoriespython
postedAug 13, '13 at 12:12p
activeAug 13, '13 at 5:01p
posts5
users4
websitepython.org

People

Translate

site design / logo © 2021 Grokbase