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!