[Newbies] Re: Beginners Digest, Vol 18, Issue 2

[Oscar Nierstrasz]

Cacheing Fibonacci is a nice standard example for memoizing that we  
use in our Smalltalk course.

See:

https://www.iam.unibe.ch/scg/svn_repos/Lectures/Smalltalk/

The relevant lecture is 07BestPractice.ppt

We start with a naive solution:

Fibs>>at: anIndex
	self assert: anIndex >= 1.
	anIndex = 1 ifTrue: [ ^ 1 ].
	anIndex = 2 ifTrue: [ ^ 1 ].
	^ (self at: anIndex - 1) + (self at: anIndex - 2)

Fibs new at: 35

works but is very slow.

We add a cache and slightly transform the #at: method:

Object subclass: #Fibs
	instanceVariableNames: 'fibCache'
	classVariableNames: ''
	poolDictionaries: ''
	category: 'Misc'

Fibs>>initialize
	fibCache := Dictionary new

Fibs>>fibCache
	^ fibCache

Fibs>>lookup: anIndex
	^ self fibCache at: anIndex ifAbsentPut: [ self at: anIndex ]

Fibs>>at: anIndex
	self assert: anIndex >= 1.
	anIndex = 1 ifTrue: [ ^ 1 ].
	anIndex = 2 ifTrue: [ ^ 1 ].
	^ (self lookup: anIndex - 1) + (self lookup: anIndex - 2)

Note that the change to the at: method is minimal.

Now Fibs new at: 100
is linear and virtually instantaneous.

Now you can use this method from Integer in the obvious way:

fib
	^ Fibs new at: self

1000 fib -->
434665576869374564356885276750406258025646605173717804024817290895365554 
179490518904038798400792551692959225930803226347752096896232398733224711 
61642996440906533187938298969649928516003704476137795166849228875

Oscar