[squeak-dev] Faster fibonacci
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:
> 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
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
>> 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>
>>> > 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 SqueakMap.
>>> 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