Python 3.3 vs. MSDOS Basic

[Terry Reedy]

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