Thursday, June 26, 2008

Source code for FibonacciCachedSplitRecursionCalculator

As requested, here is the source code for the fast Fibonacci calculator. The class has an instance variable called cache, accessed via accessors. The class side has new implemented as a singleton. There is also fibonacci: on the class side, which redirects as ^self new fibonacci: anInteger.

    FibonacciCachedSplitRecursionCalculator>>initialize

      super initialize.
      self cache: self newCache


    FibonacciCachedSplitRecursionCalculator>>newCache

      ^Dictionary new
        at: 0 put: 0;
        at: 1 put: 1;
        at: 2 put: 1;
        yourself


    FibonacciCachedSplitRecursionCalculator>>fibonacci: anInteger

      ^self cache
        at: anInteger
        ifAbsent: [self privateFibonacci: anInteger]


    FibonacciCachedSplitRecursionCalculator>>privateFibonacci: anInteger

      | firstHalf secondHalf answer |
      firstHalf := self firstHalfIndexFor: anInteger.
      secondHalf := anInteger - firstHalf.
      answer := (self fibonacci: firstHalf + 1) * (self fibonacci: secondHalf)
        + ((self fibonacci: firstHalf) * (self fibonacci: secondHalf - 1)).
      self cacheFibonacci: anInteger withValue: answer.
      ^answer


    FibonacciCachedSplitRecursionCalculator>>firstHalfIndexFor: anInteger
      "For example, 17 should be split into 9 + 8 instead of 16 + 1"

      ^1 bitShift: (anInteger - 2) highBit - 1


    FibonacciCachedSplitRecursionCalculator>>cacheFibonacci: anIndex withValue: aValue

      (self isCacheableIndex: anIndex) ifFalse: [^self].
      self cache at: anIndex put: aValue


    FibonacciCachedSplitRecursionCalculator>>isCacheableIndex: anIndex

      ^(anIndex + 1) highBit > anIndex highBit
        or: [(anIndex - 2) highBit < anIndex highBit]


Enjoy!

3 comments:

Nick Smith said...

It's reading code like this makes me realise just how much I have yet to learn. But what a great way to learn.

Thank you Andres.

Andres said...

Nick,

Thank you for your kind remarks :).

Andres.

Andres said...

Also, more in general... a while after I wrote this I realized that hashed collections with power of two table sizes will work horribly in this case. Yet another reason to use well chosen primes :).

Andres.