Python 3.3 vs. MSDOS Basic

P

Piet van Oostrum

Terry Reedy said:
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.

That may explain why the Basic version is faster: it gets overflow and
then it may have taken some shortcuts.
 
O

Olive

max=0
m=0
while m<=1000000:
m+=1
count=0
n=m
while n!=1:
count+=1
if n%2==0:
n=n//2
else:
n=3*n+1
if count>max:
max=count
num=m
print(num,max)

I have tried to run your program with pypy (Python git compiler) (http://pypy.org/), it runs about 15x faster (8 sec instead of 2m2sec in my old Celeron M420 computer).

Olive
 
T

Tim Daneliuk

Well, I don't see anything that looks especially slow in that code,
but the algorithm that you're using is not very efficient. I rewrote
it using dynamic programming (details left as an exercise), which got
the runtime down to about 4 seconds.

Are you sure you wouldn't like to share with the class? I'd be interested
in seeing your approach...
 
I

Ian Kelly

Are you sure you wouldn't like to share with the class? I'd be interested
in seeing your approach...

Very well:

def collatz(n, memo):
if n not in memo:
if n % 2 == 0:
next_n = n // 2
else:
next_n = 3 * n + 1
memo[n] = collatz(next_n, memo) + 1
return memo[n]

def run_collatz(upper):
table = {1: 0}
max_n = max(range(1, upper), key=lambda n: collatz(n, table))
return max_n, table[max_n]
(837799, 524)

It could certainly be optimized further, but at about 4 seconds it's
already fast enough for most purposes.
 
S

Serhiy Storchaka

Are you sure you wouldn't like to share with the class? I'd be interested
in seeing your approach...

Very well:

def collatz(n, memo):
if n not in memo:
if n % 2 == 0:
next_n = n // 2
else:
next_n = 3 * n + 1
memo[n] = collatz(next_n, memo) + 1
return memo[n]

def run_collatz(upper):
table = {1: 0}
max_n = max(range(1, upper), key=lambda n: collatz(n, table))
return max_n, table[max_n]
(837799, 524)

It could certainly be optimized further, but at about 4 seconds it's
already fast enough for most purposes.

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))
 
C

Chris Angelico

10-15% faster:
... num = max(range(2, M + 1), key=g) ...

Yes, but 20-30% less clear and readable. Though I do like the idea of
playing this code in the key of G Major.

ChrisA
 
A

Alexander Blinne

Am 19.02.2013 12:42, schrieb Piet van Oostrum:
That may explain why the Basic version is faster: it gets overflow and
then it may have taken some shortcuts.

Consider this C program

#include <stdio.h>

int main(void) {

int max = 0;
int m = 0;
long int n;
int count;
int num;

while(m<=1000000) {
m++;
n = m;
count = 0;

while(n != 1) {
count++;
if(n % 2 == 0) {
n = n / 2;
}
else {
n = n*3 + 1;
}
}

if(count > max) {
max = count;
num = m;
}
}

printf("%d, %d\n", num, max);
}

If the line

long int n;

is changed into

unsigned int n;

the program runs in 0.68 sec instead of 0.79, so there is some shortcut.
If changed into

signed int n;

there is a veeery long, perhaps infinite loop.

Greetings
Alexander
 
I

Ian Kelly

If changed into

signed int n;

there is a veeery long, perhaps infinite loop.

Yes, infinite. Here's the first such sequence encountered with a
signed 32-bit int.

[113383, 340150, 170075, 510226, 255113, 765340, 382670, 191335,
574006, 287003, 861010, 430505, 1291516, 645758, 322879, 968638,
484319, 1452958, 726479, 2179438, 1089719, 3269158, 1634579, 4903738,
2451869, 7355608, 3677804, 1838902, 919451, 2758354, 1379177, 4137532,
2068766, 1034383, 3103150, 1551575, 4654726, 2327363, 6982090,
3491045, 10473136, 5236568, 2618284, 1309142, 654571, 1963714, 981857,
2945572, 1472786, 736393, 2209180, 1104590, 552295, 1656886, 828443,
2485330, 1242665, 3727996, 1863998, 931999, 2795998, 1397999, 4193998,
2096999, 6290998, 3145499, 9436498, 4718249, 14154748, 7077374,
3538687, 10616062, 5308031, 15924094, 7962047, 23886142, 11943071,
35829214, 17914607, 53743822, 26871911, 80615734, 40307867, 120923602,
60461801, 181385404, 90692702, 45346351, 136039054, 68019527,
204058582, 102029291, 306087874, 153043937, 459131812, 229565906,
114782953, 344348860, 172174430, 86087215, 258261646, 129130823,
387392470, 193696235, 581088706, 290544353, 871633060, 435816530,
217908265, 653724796, 326862398, 163431199, 490293598, 245146799,
735440398, 367720199, 1103160598, 551580299, 1654740898, 827370449,
-1812855948, -906427974, -453213987, -1359641960, -679820980,
-339910490, -169955245, -509865734, -254932867, -764798600,
-382399300, -191199650, -95599825, -286799474, -143399737, -430199210,
-215099605, -645298814, -322649407, -967948220, -483974110,
-241987055, -725961164, -362980582, -181490291, -544470872,
-272235436, -136117718, -68058859, -204176576, -102088288, -51044144,
-25522072, -12761036, -6380518, -3190259, -9570776, -4785388,
-2392694, -1196347, -3589040, -1794520, -897260, -448630, -224315,
-672944, -336472, -168236, -84118, -42059, -126176, -63088, -31544,
-15772, -7886, -3943, -11828, -5914, -2957, -8870, -4435, -13304,
-6652, -3326, -1663, -4988, -2494, -1247, -3740, -1870, -935, -2804,
-1402, -701, -2102, -1051, -3152, -1576, -788, -394, -197, -590, -295,
-884, -442, -221, -662, -331, -992, -496, -248, -124, -62, -31, -92,
-46, -23, -68, -34, -17, -50, -25, -74, -37, -110, -55, -164, -82,
-41, -122, -61, -182, -91, -272, -136, -68, ...]
 
T

Tim Daneliuk

Are you sure you wouldn't like to share with the class? I'd be interested
in seeing your approach...

Very well:

def collatz(n, memo):
if n not in memo:
if n % 2 == 0:
next_n = n // 2
else:
next_n = 3 * n + 1
memo[n] = collatz(next_n, memo) + 1
return memo[n]

def run_collatz(upper):
table = {1: 0}
max_n = max(range(1, upper), key=lambda n: collatz(n, table))
return max_n, table[max_n]
(837799, 524)

It could certainly be optimized further, but at about 4 seconds it's
already fast enough for most purposes.

Thanks. I was specifically curious about your use of dynamic programming.
What about this algorithm makes it particularly an example of this? Is
it your use of memoization or something other than this?
 
N

Neil Cerutti

Thanks,Chris. I'm a newbie to Python and didn't realize that
it's not as good at number crunching as some of the others. It
does seem to do better than Basic with numbers in lists as
opposed to arrays in Basic.

Python is good enough at number crunching for Project Euler. Its
data types and library make a few of the problems otherwise
uninteresting, in fact.

Sometimes, as in this case, memoization is good enough (a quick
look at my own code for this shows that's what I did, too). But
when it's a particularly good example of a Project Euler problem,
you'll need to do some mathematical analysis to improve your
approach, first.

But yeah, do not get in the habit of comparing your times to,
say, C++ programs. ;)
 
I

Ian Kelly

Thanks. I was specifically curious about your use of dynamic programming.
What about this algorithm makes it particularly an example of this? Is
it your use of memoization or something other than this?

In retrospect, I was using the term overly broadly, as the algorithm
does not really use dynamic programming. I should have written
"memoization" instead.
 
T

Tim Daneliuk

In retrospect, I was using the term overly broadly, as the algorithm
does not really use dynamic programming. I should have written
"memoization" instead.

That's why I asked. Dynamic Programming itself is a sort of wide
term and I was curious which version of it you found useful.

Thanks for the discussion.
 
T

Tim Daneliuk

That's why I asked. Dynamic Programming itself is a sort of wide
term and I was curious which version of it you found useful.

Thanks for the discussion.

One other point of interest: The formal notion of Dynamic Program
is to decompose problems into potentially overlapping subproblems
and only solve each subproblem once, and reapply the results as
needed. Hence, your use of memoization is indeed an example of
Dynamic Programming.

Notwithstanding the formal ideas of a Dynamic Program, my interest in this
context really had more to do with the word "dynamic". Languages
like Python are "dynamic" in the sense that a running program can
actually generate new code as it runs. This makes it possible to
write adaptive programs that morph as they run, typically in response
to their inputs and state.*** I was thinking that perhaps
you'd done something in this sense of the word in solving the OPs
problem.


*** To be sure, you can do this in assembler too, it's just much
more convenient in dynamic languages like Python.
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,906
Latest member
SkinfixSkintag

Latest Threads

Top