[Tutor] Can I speed this up?

[Dick Moores]

Kent,

It's late on the Left Coast, and I've only got time to try the 
"incrementing x by 2" idea, the easiest one to implement. Great! On the 
worst of my "anomalies" in the 400 trillion range,
400000000021199 = 19814533*20187203, doing that cut the time from 45 
seconds to 27! Don't know why I didn't see that before.

I replaced  x += 1  with

if x > 2: x += 2
else: x = 3

Thanks!

Dick

Kent Johnson wrote at 02:45 10/13/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
>
>_______________________________________________
>Tutor maillist  -  Tutor at python.org
>http://mail.python.org/mailman/listinfo/tutor