[Tutor] Can I speed this up?

[Dick Moores]

Barry Sperling wrote at 09:05 10/12/2004:
>As a newbie, I'd like to know why you used a "for" loop in 
>isPrimeSmall(n) and a "while" loop in isPrimeBig(n).  Is there a 
>performance difference?
>Thanks,
>         Barry

Barry,

Yes, the "for" loop using xrange() in isPrimeSmall(n) is a bit faster 
(maybe by 10% in the 400 trillion range) than the "while" loop in 
isPrimeBig(n), so I'd like to use xrange() for large integers as well as 
small. But I found that if n is larger than about 4.6616 quintillion I 
get this error:

Traceback (most recent call last):
   File "C:/Python23/factorIntegers.py", line 284, in -toplevel-
     factors = factorsOfInteger(n)
   File "C:/Python23/factorIntegers.py", line 248, in factorsOfInteger
     if isPrime(n):
   File "C:/Python23/factorIntegers.py", line 153, in isPrime
     return isPrimeSmall(n)
   File "C:/Python23/factorIntegers.py", line 169, in isPrimeSmall
     for x in xrange(3,limit,2):
OverflowError: long int too large to convert to int

I got this by temporarily modifying isPrime(n) to

def isPrime(n):
     #if n < 4611600000000000000:
     if n < 4700000000000000000:
         return isPrimeSmall(n)
     else:
         return isPrimeBig(n)

and entering min max as 4611700000000000000 4611700000000000050.

The change to 4700000000000000000 in isPrime() forced the use of 
isPrimeSmall(n) (and xrange()), thereby producing the OverflowError.

As for why 4.6117 quintillion, see this thread in the Tutor archive:
<http://mail.python.org/pipermail/tutor/2004-September/032069.html>,

especially 
<http://mail.python.org/pipermail/tutor/2004-September/032074.html>.

Dick


>Dick Moores wrote:
>
>>I'd greatly appreciate some tutors taking a look at my 
>>factorIntegers.py at 
>><http://www.rcblue.com/Python/factorIntegers-forWeb.py>. I've worked 
>>hard to make it as efficient as possible, but suspect there is more 
>>that could be done. Or maybe I'm completely on the wrong track as far 
>>as speed is concerned.
>>I've made use of the program to compute prime factors for integers in 
>>the 5 quintillion range. Please see 
>><http://www.rcblue.com/Python/IntegerFactorsForWeb.txt>
>>for some results from the latest revision of factorIntegers.py.
>>You'll note that in almost all cases the primes take the longest time 
>>to compute (29 minutes and change). But note also the anomalies listed 
>>at the top of the script. Is there something I've missed that would 
>>eliminate these? Or are these to be expected, given the nature of the 
>>prime factors of these integers?
>>I also did some computing in the 400 trillion range, and found a bunch 
>>of these anomalies. The worst I could find was 42 seconds (primes took 
>>11 seconds):
>>400,000,000,040,471 = 19502713*20509967
>>42 seconds
>>400,000,000,040,507 = 400000000040507 is PRIME
>>11 seconds
>>
>>Also, of course, I'd appreciate criticism (or even deserved praise) of 
>>anything that catches your wise and experienced eyes.
>>BTW the line drawn in isPrime(n) at 4,611,600,000,000,000,000 is for my 
>>computer and operating system. Yours may require a different line. See 
>>the "large number question" Tutor thread of 9/25 and 9/26.
>>Thanks, tutors.
>>Dick Moores
>>rdm at rcblue.com
>>Python 2.3.4, Win XP
>>
>>"Few persons have sufficient wisdom to prefer censure, which is useful, 
>>to praise which deceives them."
>>- Francois De La Rochefoucauld __