Path: csiph.com!usenet.pasdenom.info!aioe.org!news.stack.nl!newsfeed.xs4all.nl!newsfeed3.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
MIME-Version: 1.0
In-Reply-To: <520A2295.5040605@gmail.com>
References: <520A2295.5040605@gmail.com>
Date: Tue, 13 Aug 2013 13:42:56 +0100
Subject: Re: Question about function failing with large number
From: Chris Angelico <rosuav@gmail.com>
To: python-list@python.org
Content-Type: text/plain; charset=ISO-8859-1
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.534.1376397784.1251.python-list@python.org>
Lines: 60
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:52457

On Tue, Aug 13, 2013 at 1:12 PM, Anthony Papillion <papillion@gmail.com> 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