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@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.h...
Andres Valloud did provide some in VW too, then probably in Cuis too...
Le mer. 17 avr. 2019 à 20:56, tim Rowledge tim@rowledge.org a écrit :
On 2019-04-17, at 4:26 AM, Levente Uzonyi leves@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@rowledge.org; http://www.rowledge.org/tim Useful random insult:- Wise as the world is flat.