On Tue, 14 Feb 2006 08:42:38 -0800, [EMAIL PROTECTED] 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. -- http://mail.python.org/mailman/listinfo/python-list