Re: Re: Beginners Digest, Vol 18, Issue 2

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