Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.python > #39148
| From | Terry Reedy <tjreedy@udel.edu> |
|---|---|
| Subject | Re: Python 3.3 vs. MSDOS Basic |
| Date | 2013-02-18 19:50 -0500 |
| References | <e8a634af-4e29-4f45-b327-2dfd1fab5269@googlegroups.com> |
| Newsgroups | comp.lang.python |
| Message-ID | <mailman.1986.1361235083.2939.python-list@python.org> (permalink) |
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
Back to comp.lang.python | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread
Python 3.3 vs. MSDOS Basic John Immarino <johimm@gmail.com> - 2013-02-18 11:13 -0800
Re: Python 3.3 vs. MSDOS Basic Chris Angelico <rosuav@gmail.com> - 2013-02-19 08:55 +1100
Re: Python 3.3 vs. MSDOS Basic Ian Kelly <ian.g.kelly@gmail.com> - 2013-02-18 14:54 -0700
Re: Python 3.3 vs. MSDOS Basic Tim Daneliuk <tundra@tundraware.com> - 2013-02-19 08:46 -0600
Re: Python 3.3 vs. MSDOS Basic Ian Kelly <ian.g.kelly@gmail.com> - 2013-02-19 11:31 -0700
Re: Python 3.3 vs. MSDOS Basic Tim Daneliuk <tundra@tundraware.com> - 2013-02-20 08:21 -0600
Re: Python 3.3 vs. MSDOS Basic Ian Kelly <ian.g.kelly@gmail.com> - 2013-02-20 11:38 -0700
Re: Python 3.3 vs. MSDOS Basic Tim Daneliuk <tundra@tundraware.com> - 2013-02-20 16:49 -0600
Re: Python 3.3 vs. MSDOS Basic Tim Daneliuk <tundra@tundraware.com> - 2013-02-20 16:59 -0600
Re: Python 3.3 vs. MSDOS Basic Serhiy Storchaka <storchaka@gmail.com> - 2013-02-19 22:28 +0200
Re: Python 3.3 vs. MSDOS Basic Chris Angelico <rosuav@gmail.com> - 2013-02-20 08:39 +1100
Re: Python 3.3 vs. MSDOS Basic Gregory Ewing <greg.ewing@canterbury.ac.nz> - 2013-02-20 18:32 +1300
Re: Python 3.3 vs. MSDOS Basic Chris Angelico <rosuav@gmail.com> - 2013-02-19 08:56 +1100
Re: Python 3.3 vs. MSDOS Basic Chris Angelico <rosuav@gmail.com> - 2013-02-19 08:58 +1100
Re: Python 3.3 vs. MSDOS Basic John Immarino <johimm@gmail.com> - 2013-02-18 17:39 -0800
Re: Python 3.3 vs. MSDOS Basic Chris Angelico <rosuav@gmail.com> - 2013-02-19 14:01 +1100
Re: Python 3.3 vs. MSDOS Basic Nick Mellor <thebalancepro@gmail.com> - 2013-02-18 20:17 -0800
Re: Python 3.3 vs. MSDOS Basic Nick Mellor <thebalancepro@gmail.com> - 2013-02-18 20:17 -0800
Re: Python 3.3 vs. MSDOS Basic John Immarino <johimm@gmail.com> - 2013-02-18 17:39 -0800
Re: Python 3.3 vs. MSDOS Basic Neil Cerutti <neilc@norwich.edu> - 2013-02-20 17:06 +0000
Re: Python 3.3 vs. MSDOS Basic Chris Angelico <rosuav@gmail.com> - 2013-02-19 09:01 +1100
Re: Python 3.3 vs. MSDOS Basic Ian Kelly <ian.g.kelly@gmail.com> - 2013-02-18 15:15 -0700
Re: Python 3.3 vs. MSDOS Basic Alexander Blinne <news@blinne.net> - 2013-02-19 01:11 +0100
Re: Python 3.3 vs. MSDOS Basic Dennis Lee Bieber <wlfraed@ix.netcom.com> - 2013-02-18 19:36 -0500
Re: Python 3.3 vs. MSDOS Basic John Immarino <johimm@gmail.com> - 2013-02-18 17:47 -0800
Re: Python 3.3 vs. MSDOS Basic John Immarino <johimm@gmail.com> - 2013-02-18 17:47 -0800
Re: Python 3.3 vs. MSDOS Basic Terry Reedy <tjreedy@udel.edu> - 2013-02-18 19:50 -0500
Re: Python 3.3 vs. MSDOS Basic Piet van Oostrum <piet@vanoostrum.org> - 2013-02-19 12:42 +0100
Re: Python 3.3 vs. MSDOS Basic Alexander Blinne <news@blinne.net> - 2013-02-20 01:23 +0100
Re: Python 3.3 vs. MSDOS Basic Ian Kelly <ian.g.kelly@gmail.com> - 2013-02-19 18:04 -0700
Re: Python 3.3 vs. MSDOS Basic Terry Reedy <tjreedy@udel.edu> - 2013-02-19 00:28 -0500
Re: Python 3.3 vs. MSDOS Basic Anssi Saari <as@sci.fi> - 2013-02-19 12:52 +0200
Re: Python 3.3 vs. MSDOS Basic Serhiy Storchaka <storchaka@gmail.com> - 2013-02-19 13:13 +0200
Re: Python 3.3 vs. MSDOS Basic Olive <diolu.remove_this_part@bigfoot.com> - 2013-02-19 15:02 +0100
csiph-web