Re: Beginners Digest, Vol 18, Issue 2

So. You would have an array called Fibs or Primes, and
just stack up a collection of Primes that would hang
around?

I think that I would enjoy that. I think I get it.

(Thanks I think)
or
Thanks I: think.
 


       
____________________________________________________________________________________
Building a website is a piece of cake. Yahoo! Small Business gives you all the tools to get online.
http://smallbusiness.yahoo.com/webhosting 
_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

> > > 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
_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

On Oct 3, 2007, at 15:55 , Mark Smithfield wrote:

>>> I want to apply smalltalk to fibonacci numbers. I
>> add
>>> this method
>>> to Integer,
>>>
>>> fib:
>>>     (self = 0) ifTrue: (^0)
>>>     (self = 1) ifTrue: (^1)
>>>     ^ (self - 1 fib) + (self - 2 fib).

This is not Smalltalk. Blocks need square brackets, and unary  
messages bind more closely that binary messages (a.k.a. operators):

fib
        ^self <= 1
                ifTrue: [self]
                ifFalse: [(self - 1) fib + (self - 2) fib]

fibMemo
        ^ self fibMemoizeIn: (Array new: self withAll: 0)

fibMemoizeIn: anArray
        | fib |
        self <= 1 ifTrue: [^self].
        (fib := anArray at: self) > 0 ifTrue: [^ fib].
        ^ anArray at: self
                put: (self - 1 fibMemoizeIn: anArray) + (self - 2 fibMemoizeIn:  
anArray)

- Bert -


_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

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

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 -


_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

On Oct 3, 2007, at 16:49 , Bert Freudenberg wrote:

Hmm, this is better - don't need to initialize with zeroes:

fibMemo
        ^ self fibMemoizeIn: (Array new: self)

fibMemoizeIn: anArray
        self <= 1 ifTrue: [^ self].
        (anArray at: self) ifNotNilDo: [:fib | ^ fib].
        ^ anArray at: self
                put: (self - 1 fibMemoizeIn: anArray) + (self - 2 fibMemoizeIn:  
anArray)

But note that the iterative method is still faster.

- Bert -


_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

On 03/10/2007, Bert Freudenberg <[hidden email]> wrote:
>
>
> Now that is plain silly. If you just iterate, why store in an array?

Good question. No good answer :-(
Your solution is >20x faster, thanks!
_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

On Oct 3, 2007, at 7:31 AM, Michael Davies wrote:

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

Actually, in the case of the Fibonacci sequence, the best way to  
speed it up is to use the closed-form formula:

nthFibonacci
        |phi1 phi2 term1 term2|
        phi1 := (1 + 5 sqrt) / 2.
        phi2 := (1 - 5 sqrt) / 2.
        term1 := phi1 raisedTo: self.
        term2 := phi2 raisedTo: self.
        ^((term1 - term2) / (5 sqrt)) rounded.
       
Sorry, I realize the OP requested a recursive solution, but I  
couldn't resist. :)


_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

On Oct 4, 2007, at 6:41 , Gregory Hinton wrote:

This is inaccurate for many numbers and fails for most:

"100 nthFibonacci" gives 354224848179262259200 (actually  
354224848179261915075)

"1500 nthFibonacci" error

whereas the iterative version gives exact results and works as long  
as we can store the result in memory. Iterative fib of 1500 takes 1.3  
ms on my machine.


- Bert -


_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

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

We start with a naive solution:

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


_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

On Oct 4, 2007, at 10:54 , Oscar Nierstrasz wrote:

> Cacheing Fibonacci is a nice standard example for memoizing that we  
> use in our Smalltalk course.
> [...]
> Now Fibs new at: 100
> is linear and virtually instantaneous.

... though with "real" memoization you would get sub-linear amortized  
cost on repeated calls (by reusing the Fibs instance or in a class var).

Which makes me wonder if there is a standard Smalltalk practice for  
generic memoization. The only thing that comes to my mind is Method  
Wrappers, but for some reason that doesn't seem to be a common  
application or even example for their use.

- Bert -


_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

On Oct 4, 2007, at 12:23 AM, Bert Freudenberg wrote:

Hmmmm, good catch.  I had overlooked the finite precision of floating  
point.

Looks like it's accurate up to "75 nthFibonacci" but thereafter  
diverges from reality.

This is why I prefer mathematics to computer science: mathematicians  
can assume the existence of irrational numbers. ;)
_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

On Oct 4, 2007, at 11:15 , Gregory Hinton wrote:

Right. At least we use true Integers, in contrast to most popular  
languages.

- Bert -



_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

Here's another solution that, like Bert's, does not require an  
instance variable or an additional class.  the advantage, I think, is  
that the concerns of computing the result and managing the cache are  
separated, so it is easy to adapt to other situations:

Integer>>fib
        self assert: self >= 1.
        ^ self fibWithCache: Dictionary new.! !

Integer>>fibLookup: cache
        ^ cache at: self ifAbsentPut: [ self fibWithCache: cache ] ! !

Integer>>fibWithCache: cache
        self assert: self >= 1.
        (self == 1) ifTrue: [ ^1].
        (self == 2) ifTrue: [ ^1].
        ^ ((self - 1) fibLookup: cache) + ((self - 2) fibLookup: cache)! !

Here too, the caching version is only slightly modified from the  
slow, non-caching version.

Integer>>fibSlow
        self assert: self >= 1.
        (self == 1) ifTrue: [ ^1].
        (self == 2) ifTrue: [ ^1].
        ^ (self - 1) fib + (self - 2) fib! !

Oscar

_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners

Maybe you could try with ArbitraryPrecisionFloat package (browse
http://www.squeaksource.com).
But you should then know the Number of bits to use in advance...

Or try a package that can deal with AlgebraicNumber, maybe MathMorph
would do that?

In Smalltalk, ideas are programmed so fast that it's fun...

Gregory Hinton a écrit :
>
> Hmmmm, good catch.  I had overlooked the finite precision of floating
> point.
>
> Looks like it's accurate up to "75 nthFibonacci" but thereafter diverges
> from reality.
>
> This is why I prefer mathematics to computer science: mathematicians can
> assume the existence of irrational numbers. ;)

_______________________________________________
Beginners mailing list
[hidden email]
http://lists.squeakfoundation.org/mailman/listinfo/beginners