Learning Lisp, part 2

[grok_mctanys]

Gosh. It's been a long time since the first one of these. I have been slacking.

I meant to get round to doing Project Euler, problem 2 last weekend, but, well, life. So I've been having a go this weekend, and tore chunks of my hair out over it for the past couple of days.

Still, I figured it out in the end. Only took 'til Monday lunchtime.

Comments

[astatine210]

Just for the record, here's how I did it in Python:

top=4000000
penultimate=0
last=1
current=1
sum=0
while current<=top:
if current%2==0:
sum+=current
(penultimate, last)=(last, current)
current=penultimate+last
print sum

Not sure how I'd go about that in a functional programming idiom, though.

[grok_mctanys]

Let me have a go at a functional idiom in python in a simple all-in-one program, bearing in mind I don't actually know Python (I'm making it up from the brief bit of example code in the wikipedia python page)

def add_even_fib(max, prev, cur):
if prev + cur > max:
return 0
if prev + cur % 2 == 0:
return prev + cur + add_even_fib(max, cur, prev + cur)
else:
return add_even_fib(max, cur, prev + cur)

print add_even_fib(4000000, 0, 1)

[astatine210]

Having had a think about doing it in a more functional manner, it'd probably need a generator:

def fibgen(top):
last,cur=1,1
while cur<=top:
yield cur
last,cur=cur,last+cur

print sum(n for n in fibgen(4e6) if n%2==0)

[grok_mctanys]

Yes, my approach was done with generators/continuations in mind. Rather than creating a list of Fibonacci numbers, it would be better to have a continuation create them, and then pass them through a filter and accumulator/adder.

However, I'm not nearly at the point where I can do continuations yet, so I stuck to creating the whole list at once.

[wibblymat]

I decided to look at how I'd solved the same problem when I had a go a long time ago, and found the following in PHP

$phi = ( 1 + pow( 5, 0.5 ) ) / 2;
$psi = 1 - $phi;

$sum = 0;
$f = 2;

for( $i = 3; $f < 4000000; $i += 3 )
{
$sum += $f;
// http://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression
$f = ( pow( $phi, $i ) - pow( $psi, $i ) ) / pow( 5, 0.5 );
}

print "{$sum}\n";

I can only assume I was being deliberately perverse!

[grok_mctanys]

Well, it's not really much fun if you do it in the most straightforward way. I could have implemented mine in the lisp equivalent of the python version I did a couple of comments above. But I wouldn't have learned anything from that.