[squeak-dev] Faster fibonacci

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


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...


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


More information about the Squeak-dev mailing list