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