Wednesday, June 25, 2008

Fun with Fibonacci

A couple nights ago I had the chance of showing Smalltalk to someone who had never seen it before. As it happens, we went over Fibonacci stuff. Why not, it's so much fun in Smalltalk because there's no overflow and things...

Some 10 years ago, I did Fibonacci stuff in Squeak, and I remembered that at one point I had abused the identity

F(a+b) = F(a+1) * F(b) + F(a) * F(b-1)

into a super fast Fibonacci number calculator because if F(k) had to be calculated, then the above could be used with a = k // 2 and b = k - a.

In addition, one can take things further and make the whole thing run even faster. For example, an option is to split k along powers of two while caching the value triplets F(2^n - 1), F(2^n) and F(2^n + 1). But, since I did that 10 years ago, the code was horrible and because of that I had been neglecting to merge it into my dev image.

So today, and given that I had done Fibonacci stuff again the other night, I decided enough was enough and I reimplemented the calculators. I am happy to report that

FibonacciCachedSplitRecursion fibonacci: 15625

evaluates in 4 milliseconds starting from scratch. Also,

FibonacciCachedSplitRecursion fibonacci: 390625

evaluates in about 1.1 seconds starting from scratch, and about twice faster the second time. Implementing it beautifully (including a fantastic check to detect triplet indices) took about 20-30 minutes.

Smalltalk is great.

PS1: did you know that F(5^k) = 5^k (mod 100)?

PS2: I wrote the tests in SUnit and ran them in Assessments :).

3 comments:

Nick Smith said...

This is both a token of appreciation and a request.

First the appreciation: I'm just working my way through 'A mentoring course' and, although it is way above my head (I have neither a programming or math background), it really is stretching my mind. I'm struggling to understand how 'a pattern of perception' works but I've already come to appreciate just how expressive and powerful Smalltalk can be. So thank you...even though I get stuck, I appreciate that this is a great book.

Now the request: I get the feeling that a good way for me to learn is to read examples of good code. So, with that in mind, would it be possible to see the code behind FibonacciCachedSplitRecursion. Maybe I'll also learn how to do recursion in Smalltalk. :)

Andres said...

Nick,

I am glad you like the mentoring course book. In a couple weeks, the FTP server should be back up and then you will be able to get two sample applications of the pattern of perception. IIRC, one is the code I wrote for the Smalltalk Solutions 2006 Coding Contest, and the other one is the code for the Smalltalk Solutions 2007 Coding Contest I organized. This one has a reference solution written using the pattern of perception as well.

Andres.

Nick Smith said...

That's great news Andres. I'll check back in a couple of weeks. Thank you.