Python 3.3 vs. MSDOS Basic
Terry Reedy
tjreedy at udel.edu
Mon Feb 18 19:50:51 EST 2013
On 2/18/2013 2:13 PM, John Immarino wrote:
> I coded a Python solution for Problem #14 on the Project Euler
> website. I was very surprised to find that it took 107 sec. to run
> even though it's a pretty simple program. I also coded an equivalent
> solution for the problem in the old MSDOS basic. (That's the 16 bit
> app of 1980s vintage.) It ran in 56 sec. Is there a flaw in my
> coding, or is Python really this slow in this particular application.
> MSDOS Basic usually runs at a snails pace compared to Python.
I find this surprising too. I am also surprised that it even works,
given that the highest intermediate value is about 57 billion and I do
not remember that Basic had infinite precision ints.
> The following iterative sequence is defined for the set of positive
> integers:
>
> n → n/2 (n is even) n → 3n + 1 (n is odd)
Note that if n is odd, 3n + 1 is even (and not 1!), so one may take two
steps with (3n + 1)/2.
> Using the rule above and starting with 13, we generate the following
> sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
>
> It can be seen that this sequence (starting at 13 and finishing at 1)
> contains 10 terms. Although it has not been proved yet (Collatz
> Problem), it is thought that all starting numbers finish at 1.
https://en.wikipedia.org/wiki/Collatz_conjecture
> Which starting number, under one million, produces the longest
> chain?
I suppose 'print(837799)' would not count as a proper solution.
> NOTE: Once the chain starts the terms are allowed to go above one
> million.
Here is my slightly revised code with timings on a good, 20 month old
win 7 machine.
from time import time
start = time()
num, max = 0, 0
for m in range(1, 1000001):
n = m
count=0
while n !=1:
if n & 1: #n % 2:
n = (3*n + 1) // 2
count += 2
else:
n = n//2
count += 1
if count > max:
num = m
max = count
print(num, max , time()-start)
# original: 837799, 524 steps, 53.9 secs
# for ... range: 52.3
# reverse inner if 49.0
# double step 39.1
# n & 1 instead of n % 2 for test: 36.0, 36.0, 35.9
# n>>1 instead of n//2: 34.7, 36.1, 36.2;
# this may be internally optimized, so skip
I do not see any fluff left to remove, unless one takes the major step
of saving already calculated values in an array.
Since the highest intermediate value of n is 56991483520 (445245965
*2**7, from adding "if n > maxn: maxn = n" to the odd branch, before
dividing by 2), the array would have to be limited to a much lower
value, say a few million.
--
Terry Jan Reedy
More information about the Python-list
mailing list