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

Oscar Nierstrasz oscar.nierstrasz at gmail.com
Thu Oct 4 08:54:42 UTC 2007

```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

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

```