[squeakdev] Faster fibonacci
Nicolas Cellier
nicolas.cellier.aka.nice at gmail.com
Wed Apr 17 19:38:14 UTC 2019
Let me see...
For example here in 2011:
MCHttpRepository
location: 'http://www.squeaksource.com/FactorialContest'
user: ''
password: ''.
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
published...
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
> http://smallissimo.blogspot.com/2011/07/optimizingproductofprimepowers.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 20190417, 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 fastdoublingfibwithkaratsuba
>> 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/squeakdev/attachments/20190417/1a5c38b1/attachment.html>
More information about the Squeakdev
mailing list
