[squeak-dev] Faster fibonacci
nicolas.cellier.aka.nice at gmail.com
Wed Apr 17 19:38:14 UTC 2019
Let me see...
For example here in 2011:
I use Karatsuba a lot for ArbitraryPrecisionFloat... But there is even more
efficient for monstruous integers, Schoenhage-*Strassen *which use kind of
Fourier Transform, but harder to program... And I think that I recently
heard that an algorithm approching the O(log N) barrier has been
Le mer. 17 avr. 2019 à 21:28, Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com> a écrit :
> 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
>> > 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
>> > - 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
>> Perhaps I'll try it out just for fun.
>> 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...
More information about the Squeak-dev