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

[Bert Freudenberg]

On Oct 3, 2007, at 16:31 , Michael Davies wrote:

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

Now that is plain silly. If you just iterate, why store in an array?  
(Also note that you want an Array, not an IntegerArray which are only  
32 bits. Fibonaccis get large quickly.)

fibIter
	| a b c |
	a := 0.
	b := 1.
	1 to: self do: [:i |
		c := b.
		b := a.
		a := b + c].
	^ a

I doubt you can do much better in Squeak. 100000 fibIter takes under  
a second on my machine. Well, printing that  large number (more than  
20000 digits) takes 7 seconds.

- Bert -