Hi Tim,
I have published some Karatsuba implementation in squeak for years, it's
quite easy.
For example
http://smallissimo.blogspot.com/2011/07/optimizing-product-of-prime-powers.html?m=1

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>