Python 3.3 vs. MSDOS Basic

[workshed]

On Tuesday, February 19, 2013 3:28:25 PM UTC-5, Serhiy Storchaka wrote:
> 10-15% faster:
>
>
> def f(M):
>      def g(n, cache = {1: 0}):
>          if n in cache:
>              return cache[n]
>          if n % 2:
>              m = 3 * n + 1
>          else:
>              m = n // 2
>          cache[n] = count = g(m) + 1
>          return count
>      num = max(range(2, M + 1), key=g)
>      return num, g(num)
>
> print(*f(1000000))

I managed another 15-20% (on my machine) with a different caching scheme.

def g(n):
    cache = [1,1] + [0]*(n - 2)
    longest = 0
    for x in range(1, n):
        num = 0
        y = x
        while True:
            if x < n and cache[x]:
                cache[y] = num + cache[x]
                break
            if x&1:
                x = (3*x + 1)//2    #Credit to Terry
                num += 2
            else:
                x = x//2
                num += 1
    ans = cache.index(max(cache))
    return ans, cache[ans] - 1

Python 3.2.3 (default, Oct 19 2012, 19:53:57)
[GCC 4.7.2] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import timeit
>>> timeit.Timer('euler014.f(10**6)', 'import euler014').timeit(10)
16.590431928634644
>>> timeit.Timer('euler014.f(10**7)', 'import euler014').timeit(1)
17.689634084701538
>>> timeit.Timer('euler014.g(10**6)', 'import euler014').timeit(10)
13.558412790298462
>>> timeit.Timer('euler014.g(10**7)', 'import euler014').timeit(1)
14.075398921966553

In this code only entries less than n (1000000 in the project Euler problem)
are cached, and only one is cached per run of the inner loop, which to
me would seem to me much less efficient. I supposed the advantages are no
overhead from dict lookups, function calls, or recursion, plus it uses Terry
Reedy's nice observation that one can take two steps at a time for odd
values. I would think my version uses less memory as well, since the cache
dict/list would be maximally dense for indices less than n in either scheme.

I'm still surprised that both algorithm's seem pretty much O(n) tho.
Intuitively I'd have thought mine would start to lose out with larger
numbers, given the much lower degree of caching.

With PyPy the results are more striking:

Python 2.7.2 (1.9+dfsg-1, Jun 19 2012, 23:23:45)
[PyPy 1.9.0 with GCC 4.7.0] on linux2
Type "help", "copyright", "credits" or "license" for more information.
And now for something completely different: ``Is rigobot around when the
universe ceases to exist?''
>>>> import timeit
>>>> timeit.Timer('euler014.f(10**6)', 'import euler014').timeit(10)
26.138880014419556
>>>> timeit.Timer('euler014.g(10**6)', 'import euler014').timeit(10)
1.5725858211517334

I guess PyPy can JIT the iterative loop more effectively than it can the
recursion.

This is my first post on this list btw, please let me know if I screwed
anything up.

workshed