[squeak-dev] Faster fibonacci

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


Le mer. 17 avr. 2019 à 21:39, Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com> a écrit :

>
>
> Le mer. 17 avr. 2019 à 21:38, Nicolas Cellier <
> nicolas.cellier.aka.nice at gmail.com> a écrit :
>
>> 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...
>>
>
> O(N log N) of course...
>
> https://hal.archives-ouvertes.fr/hal-02070778/document

>
>> 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/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/ba619054/attachment.html>


More information about the Squeak-dev mailing list