[Tutor] Can I speed this up?
Kent Johnson
kent_johnson at skillsoft.com
Wed Oct 13 11:45:19 CEST 2004
Dick,
There are a few places in your script where you are doing a lot of extra
work. I think one of them is responsible for the "anomalies" and another
could yield a 2x speedup.
First, look at something like
5,000,000,000,000,005,171 = 800104651*6249182521
At the beginning of factorsOfInteger() you call isPrime(n). This will check
to see if 5,000,000,000,000,005,171 is prime, which means dividing it by
every odd number up to 800104651. When you find that n is not prime, you
start the division all over from 2! If you could have isPrime return the
first divisor found, you could factor it out right away and avoid a lot of
work.
Then when you find a factor you check to see if the quotient is prime. You
say this speeds up some cases but I don't understand the explanation, it
looks like extra work to me. Especially in the case of two large prime
factors where you already know you have no divisors smaller than the factor
you just found.
Finally, the loop in factorsOfInteger() could increment x by 2 after
handling the special case of x = 2. Since you are finding prime factors you
don't have to check the even numbers; you have already factored out all the
2's.
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
More information about the Tutor
mailing list