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

Michael Davies mykdavies+squeak at gmail.com
Wed Oct 3 14:31:42 UTC 2007

```> > > I want to apply smalltalk to fibonacci numbers. I

> > > Next, I would like to memoize this method,

Hi Mark,
By coincidence, I was playing with this myself yesterday. If you're
interested in the numbers rather than the technique, there's a couple
of alternative approaches to speed it up, iteration and matrix
manipulation.

Michael

fibonacci
| fib |
self < 0 ifTrue: [self error: 'Not valid for negative integers'].
self = 0 ifTrue: [^ 0].
self = 1 ifTrue: [^ 1].
fib := IntegerArray new: self.
fib at: 1 put: 1.
fib at: 2 put: 1.
3 to: self do: [ :each | fib at: each put: ((fib at: (each - 1)) +
fib at: (each - 2))].
^ fib at: self.

fibonacci
| m mx f |
"Writing f1 = f1 and f2 = f0 + f1 in matrix notation and generalising
shows us that:
n
( fn  ) = ( 0 1 )   . ( f0 )
( fn+1) = ( 1 1 )     ( f1 )
"
self < 0 ifTrue: [self error: 'Not valid for negative integers'].
self = 0 ifTrue: [^ 0].
m := (Matrix ones: 2) "ie 2x2 matrix all set to 1"
at: 1 at: 1 put: 0;
yourself.
mx := m copy.
(self - 1) timesRepeat: [ mx := mx +* m ]. "could speed up by hand
crafted multiply"
f := Matrix column: #(0 1). "ie single column defined as shown"
^ (mx +* f) at: 1 at: 1
```