<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Le mer. 17 avr. 2019 à 21:38, Nicolas Cellier <<a href="mailto:nicolas.cellier.aka.nice@gmail.com">nicolas.cellier.aka.nice@gmail.com</a>> a écrit :<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div>Let me see...</div><div>For example here in 2011:</div><div><br></div><div>MCHttpRepository<br>    location: '<a href="http://www.squeaksource.com/FactorialContest" target="_blank">http://www.squeaksource.com/FactorialContest</a>'<br>    user: ''<br>    password: ''.</div><div><br></div><div>I use Karatsuba a lot for ArbitraryPrecisionFloat... But there is even more efficient for monstruous integers, <span class="gmail-m_-5741391734490912839gmail-st">Schoenhage-<i>Strassen </i></span>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...<br></div></div></div></blockquote><div><br></div><div>O(N log N) of course...</div><div> <br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="ltr"><div dir="ltr"><div></div></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Le mer. 17 avr. 2019 à 21:28, Nicolas Cellier <<a href="mailto:nicolas.cellier.aka.nice@gmail.com" target="_blank">nicolas.cellier.aka.nice@gmail.com</a>> a écrit :<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><div dir="auto">Hi Tim,<div dir="auto">I have published some Karatsuba implementation in squeak for years, it's quite easy.</div><div dir="auto">For example <a href="http://smallissimo.blogspot.com/2011/07/optimizing-product-of-prime-powers.html?m=1" target="_blank">http://smallissimo.blogspot.com/2011/07/optimizing-product-of-prime-powers.html?m=1</a></div><div dir="auto"><br></div><div dir="auto">Andres Valloud did provide some in VW too, then probably in Cuis too...</div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Le mer. 17 avr. 2019 à 20:56, tim Rowledge <<a href="mailto:tim@rowledge.org" target="_blank">tim@rowledge.org</a>> a écrit :<br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex"><br>
<br>
> On 2019-04-17, at 4:26 AM, Levente Uzonyi <<a href="mailto:leves@caesar.elte.hu" rel="noreferrer" target="_blank">leves@caesar.elte.hu</a>> wrote:<br>
> <br>
> On Tue, 16 Apr 2019, tim Rowledge wrote:<br>
> <br>
>> 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 - <br>
>> Integer >> fastDoublingFib<br>
[snip]<br>
> <br>
> That's some pretty nifty code. Other than the typical tricks, you can't make it any quicker for larger receivers.<br>
> What are these typical tricks?<br>
> - inlining methods<br>
> - decreasing the number of temporaries needed<br>
> - reordering temporaries so that the more frequently used ones use registers<br>
> - declare all temporaries at the method level so that the compiler can skip a few bytecodes setting their values to nil in each loop<br>
> <br>
> 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.<br>
<br>
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.<br>
<br>
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?<br>
<br>
I'll note that a C implementation of the fast-doubling-fib-with-karatsuba code is on github at <a href="https://github.com/ZiCog/fibo_4784969/tree/master/c" rel="noreferrer noreferrer" target="_blank">https://github.com/ZiCog/fibo_4784969/tree/master/c</a> 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.<br>
<br>
> <br>
> 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.<br>
<br>
Perhaps I'll try it out just for fun.<br>
<br>
<br>
tim<br>
--<br>
tim Rowledge; <a href="mailto:tim@rowledge.org" rel="noreferrer" target="_blank">tim@rowledge.org</a>; <a href="http://www.rowledge.org/tim" rel="noreferrer noreferrer" target="_blank">http://www.rowledge.org/tim</a><br>
Useful random insult:- Wise as the world is flat.<br>
<br>
<br>
<br>
</blockquote></div>
</blockquote></div>
</blockquote></div></div>