I came across this post while clearing out my Google Reader items this morning. While I'm not particularly interested in F# I am interested in math problems so I skimmed the post. I have nothing against F#, I just don't have time to learn yet another thing.
I'll describe Euler 14 in a minute, but I need to get some attribution out of the way. As I said, this post was my introduction to the problem. It turned out to be a response to this post, asking for a faster F# solution. So here, is problem 14 of Project Euler.net:
The following iterative sequence is defined for the set of positive integers:
n → n/2 (n is even)
n → 3n + 1 (n is odd)
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.
Which starting number, under one million, produces the longest chain?
NOTE: Once the chain starts the terms are allowed to go above one million.
I thought I'd do it in ruby, mainly to pass the time and give me an excuse to use ruby. I first started out just printing the first hundred Euler chains. Then I thought I'd see if I could solve the problem, the longest chain generated from a number less than 1,000,000. My first, brute force implementation looked something like this:
require 'benchmark'
def even?(num)
num % 2 == 0
end
def euler_chain_size(start)
length = 0
while start > 1
if even?(start)
start = start/2
else
start = 3*start+1
end
length += 1
end
length
end
max_chain_size = 0
max_chain_start = 1
Benchmark.bm do |x|
x.report do
1.upto(1000000) do |i|
chain_size = euler_chain_size(i)
if chain_size > max_chain_size
max_chain_size = chain_size
max_chain_start = i
end
end
end
puts "(#{max_chain_start}, #{max_chain_size})"
end
I had saved that off to euler14.rb and typed this in at my console:
time ruby euler14.rb
For my windows readers unfamiliar with time, it "runs programs and summarizes system resources". Basically it's a cheap way to see how long it took to run. The benchmark was added so I can get timings in windows (or anywhere).
For me that came back at:
real 7m34.232s
Ugh. The geriatric gerbil generating juice for my X41T must have died halfway through and his twin somehow resuscitated him (it's a core2 duo, of course). To make matters worse, I'm doing this all on Ubuntu in a VM on Windows Vista SP1.
I was playing a bit and mentioned the problem to a buddy of mine. He's a python dev and he whipped up a nearly identical brute force method in python. His took 1m17s. He does have some crazy fast laptop, but still, that's it's like 5x faster.
I don't know why, but I thought I'd move even? into an inline ternary. That version didn't change much, so here is the new euler_chain_size method:
require 'benchmark'
def euler_chain_size(start)
length = 0
while start > 1
start = start%2 == 0 ? start/2 : 3*start+1
length += 1
end
length
end
That run, for me, was nearly twice as fast.
C:\development\InstantRails2\dev>ruby euler14.rb
|
user |
system |
total |
real |
|
207.898000 |
0.010000 |
207.908000 |
(252.110000) |
I'm still new to ruby but, I remember reading about methods and messages in ruby and think this may be an issue with ruby messaging having to call even?(num) 1,000,000 times. Maybe not, someone that knows, would you let me know?
Not bad, but I'm still not even close to my buddies time. So I applied a quick optimization and now I'm down to:
C:\development\InstantRails2\dev>ruby euler14a.rb
| user |
system |
total |
real |
| 17.585 |
0.030000 |
17.615000 |
( 21.230000) |
How am I going from 208 seconds to 18? I'm not recalculating the lengths of chains we encountered before (or already calculated).
require 'benchmark'
def euler_chain_size(start)
length = 0
while start > 1
start = start%2 == 0 ? start/2 : 3*start+1
length += 1
if @chains.has_key?(start)
length += @chains[start]
break
end
end
length
end
@chains = {}
max_chain_size = 0
max_chain_start = 1
Benchmark.bm do |x|
x.report do
1.upto(1000000) do |i|
chain_size = euler_chain_size(i)
@chains[i] = chain_size
if chain_size > max_chain_size
max_chain_size = chain_size
max_chain_start = i
end
end
end
puts "(#{max_chain_start}, #{max_chain_size})"
end
I store the length of chains in a hash, keyed off of their start value. When I get to the start value of a chain that I already know (is in the hash) I just add that length to my current length and break out of my while loop.
I'm sure I could optimize this more and it's probably horribly ugly ruby in a c# mind set, so I'd love input on how to refactor my code.
The answer? You should really work it out on your own. If you're really curious post a comment or send me an email.