[Tutor] Can I speed this up?

[Kent Johnson]

Using psyco gives a small speedup - in my limited testing, about 15%.

Install psyco from http://psyco.sourceforge.net, then put these two lines 
after the definition of factorsOfInteger:
import psyco
psyco.bind(factorsOfInteger)

One way to speed it up would be to precompute all the possible prime 
factors up to the square root of the number you are interested in and store 
them in a file. Of course it might take a while to compute the list...it's 
a good example of speeding up an algorithm by precomputing part of it.

If you do compute such a list, a sieve of Eratosthenes algorithm 
(http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes) would probably be 
faster than using your isPrime function.

Kent

At 01:27 AM 10/12/2004 -0700, 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
>
>_______________________________________________
>Tutor maillist  -  Tutor at python.org
>http://mail.python.org/mailman/listinfo/tutor