[squeak-dev] Faster fibonacci

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Wed Apr 17 19:28:14 UTC 2019

Hi Tim,
I have published some Karatsuba implementation in squeak for years, it's
quite easy.
For example

Andres Valloud did provide some in VW too, then probably in Cuis too...

Le mer. 17 avr. 2019 à 20:56, tim Rowledge <tim at rowledge.org> a écrit :

> > On 2019-04-17, at 4:26 AM, Levente Uzonyi <leves at caesar.elte.hu> wrote:
> >
> > On Tue, 16 Apr 2019, tim Rowledge wrote:
> >
> >> I've been involved in a long and sometimes weird discussion on the
> RaspberryPi forums about fibonacci implementations in different languages
> and using assorted algorithms. I'd never really thought about alternatives
> to  recursive approaches before but it turns out there is massively faster
> way. Clearly, this is not to replace the benchFib code since that has a
> specific use, but if anyone with an interest in numerics wants a faster way
> to generate fib(8577) for example, this is how -
> >> Integer >> fastDoublingFib
> [snip]
> >
> > That's some pretty nifty code. Other than the typical tricks, you can't
> make it any quicker for larger receivers.
> > What are these typical tricks?
> > - inlining methods
> > - decreasing the number of temporaries needed
> > - reordering temporaries so that the more frequently used ones use
> registers
> > - declare all temporaries at the method level so that the compiler can
> skip a few bytecodes setting their values to nil in each loop
> >
> > But as the receiver gets larger, the LargeInteger primitives will
> dominate the run time more and more, so the tricks will have neglibile
> effect on performance.
> A spyOn of the amusing fib(4784969) (find the first fib which has more
> than a million digits, apparently) showed 99.8%  in primitives, within the
> limits of the spyOn code.
> There  is also "Karatsuba fast multiplication" on that same site, which is
> apparently faster for biiiiiig numbers. There is even example code in
> python and java. Who feels like trying it out?
> I'll note that a C implementation of the fast-doubling-fib-with-karatsuba
> code is on github at https://github.com/ZiCog/fibo_4784969/tree/master/c
> and declares a runtime of 63 seconds on a Pi 3. I got 72 on Squeak on my Pi
> 3 (without karatsuba multiply). So pretty good so far.
> >
> > And yes, we do have a better profiler: AndreasSystemProfiler. It hasn't
> been integrated into Squeak yet for some reason, but it's available on
> SqueakMap.
> Perhaps I'll try it out just for fun.
> tim
> --
> tim Rowledge; tim at rowledge.org; http://www.rowledge.org/tim
> Useful random insult:- Wise as the world is flat.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.squeakfoundation.org/pipermail/squeak-dev/attachments/20190417/fa455f3e/attachment.html>

More information about the Squeak-dev mailing list