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

[Michael Davies]

> > > 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
	"Answer the fibonacci number at the receiver."
	| 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
	"Answer the fibonacci number at the receiver."
	| 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