processing limitation in Python

[Steven D'Aprano]

On Tue, 14 Feb 2006 08:42:38 -0800, pdr14 at comcast.net wrote:

> If I un-comment any line in this program below the line where I
> commented " all OK up to this point " This program locks up my
> computer.

It locks up the operating system as well? Shame on Windows.

What happens if you type ctrl-C to interrupt the processing?


> I'm just wondering if any one else has noticed any problems with
> working with large numbers in Python ind if there is anything that can
> work around this issue.

Yes, you need a better algorithm.

You can prove to yourself that it isn't a problem with Python handling big
numbers by running this simple test:

factor(100000000000000000)

and watch how quickly it completes -- a fraction of a second. The problem
is that your test data have few factors, and so your function spends a
LONG time increasing d by one each iteration. Worst case, if your number
is a prime, it has to try to divide against *every* number, 2, 3, 4, ...
all the way up to the prime itself. This takes a LONG time if the number
is very large.

Some improvements you might like to try:

You have to check for factors of two. But after you have done that, you
are just wasting time to check for factors of 4, 6, 8, ... because they
can't possibly be factors. Pull the factor of two test out of the loop,
then start the test with d = 3 and increase by two instead of one.

You can stop looking for factors once you have reached the square root of
the original number. The square root is the biggest possible factor.

There are other improvements you can make, but they make the code more
complicated. Just these few things will give you a HUGE performance boost:

def factor(n):
    factors = []
    while n % 2 == 0:
        factors.append(2)
        n = n/2
    d = 3
    mx = int(n**0.5)
    while (n > 1) and (d <= mx):
        if n % d:
            d = d+2
        else:
            factors.append(d)
            n = n/d
    if n != 1:
        factors.append(n)
    return factors


Using this new improved version, I get this calculation in about two
seconds:

>>> factor(12345678987654)
[2, 3, 2057613164609L]

and this in less than a second:

>>> factor(12345678987654321)
[3, 3, 3, 3, 37, 37, 333667, 333667]



-- 
Steven.