<div dir="ltr"><div dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Le ven. 26 avr. 2019 à 18:10, 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 dir="ltr"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">Le ven. 26 avr. 2019 à 13:55, Fabio Niephaus <<a href="mailto:lists@fniephaus.com" target="_blank">lists@fniephaus.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"><br></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">On Fri, Apr 26, 2019 at 4:02 AM tim Rowledge <<a href="mailto:tim@rowledge.org" target="_blank">tim@rowledge.org</a>> wrote:<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-24, at 1:29 PM, Nicolas Cellier <<a href="mailto:nicolas.cellier.aka.nice@gmail.com" target="_blank">nicolas.cellier.aka.nice@gmail.com</a>> wrote:<br>
> <br>
> Hi Tim,<br>
> I've posted some enhancements with a  3-way Toom-Cook multiplication algorithm<br>
> (it is a generalization of karatsuba, but we divide in n parts instead of 2, here 3 parts for Toom-3)<br>
<br>
Wow. That's nearly twice as fast for the  fib(4784969) - 8.4 sec. Amazing. So about 10x over the original.<br>
Now *printing* the number is rather slower and if you have any magic code to improve that it would be interesting.<br>
<br>
I would *strongly* support putting the algorithm improvements into trunk. Very little code for colossal speedup and a really interesting exemplar of advanced algorithms.<br></blockquote><div><br></div><div>+1<br></div><div> </div></div></div></blockquote><div>changes are in inbox now<br></div><div>they should have associated tests</div><div><br></div><div>For the printing, cost is dominated by division.</div><div>division cost is dominated by multiplication.</div><div>We could opt for a divide and conquer algorithm too, or mixed Barett-Newton-Raphson which is the most efficient known algorithm</div><div>See for example <a href="http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Lec5-Fast-Division-Hasselstrom2003.pdf" target="_blank">http://bioinfo.ict.ac.cn/~dbu/AlgorithmCourses/Lectures/Lec5-Fast-Division-Hasselstrom2003.pdf</a></div><div><br></div></div></div></div></blockquote><div><br></div><div>Just ask, it's in the inbox now :)</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 class="gmail_quote"><div></div><div>Another interesting POV is that most of these divide and conquer lead to easy parallelisation...</div><div>If we could spawn image clones above a certain level, and communicate the results via sockets.</div><div>The printing though would require to share the target String memory, or we could end in a O(n*log(n)) reconstruction cost to gather the pieces.<br></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 class="gmail_quote"><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left:1px solid rgb(204,204,204);padding-left:1ex">
<br>
<br>
tim<br>
--<br>
tim Rowledge; <a href="mailto:tim@rowledge.org" target="_blank">tim@rowledge.org</a>; <a href="http://www.rowledge.org/tim" rel="noreferrer" target="_blank">http://www.rowledge.org/tim</a><br>
Strange OpCodes: ESBD: Erase System and Burn Documentation<br>
<br>
<br>
<br>
</blockquote></div></div>
<br>
</blockquote></div></div></div>
</blockquote></div></div>