<div dir="auto"><div>Hi Agustin,</div><div dir="auto">Naive factorial is not karatsuba friendly because you multiply a large integer with a small one in O(n). I have another blog post on Smallissimo about factorial...<br><br><div class="gmail_quote" dir="auto"><div dir="ltr" class="gmail_attr">Le sam. 7 déc. 2019 à 19:01, Agustín Sansone via Cuis-dev <<a href="mailto:cuis-dev@lists.cuis.st">cuis-dev@lists.cuis.st</a>> a écrit :<br></div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex"><div dir="ltr">A small improvement, still not faster:<div>f := 170 factorial.<br>[1000 timesRepeat: [f squared]] timeToRun. 5 <br>[1000 timesRepeat: [f karatsuba: f]] timeToRun. 77<br></div></div><br><div class="gmail_quote"><div dir="ltr" class="gmail_attr">El sáb., 7 dic. 2019 a las 13:02, Agustín Sansone (<<a href="mailto:agustinsansone7@gmail.com" target="_blank" rel="noreferrer">agustinsansone7@gmail.com</a>>) escribió:<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">Very quickly, Karatsuba's multiplication complexity of about n^1.6 <br>
soundly beats the usual elementary n^2 multiplication algorithm, even if <br>
Karatsuba is implemented in the image while the n^2 algorithm is a VM <br>
primitive.<br></blockquote><div><br></div><div>Here is an implementation of Karatsuba's multiplication, but it doesn't seem to work faster for big numbers, maybe I did something wrong:</div>f := 170 factorial.<br>[1000 timesRepeat: [f squared]] timeToRun. 5 <br><div>[1000 timesRepeat: [f karatsuba: f]] timeToRun. 161</div><div> </div></div></div>
</blockquote></div>
-- <br>
Cuis-dev mailing list<br>
<a href="mailto:Cuis-dev@lists.cuis.st" target="_blank" rel="noreferrer">Cuis-dev@lists.cuis.st</a><br>
<a href="https://lists.cuis.st/mailman/listinfo/cuis-dev" rel="noreferrer noreferrer" target="_blank">https://lists.cuis.st/mailman/listinfo/cuis-dev</a><br>
</blockquote></div></div></div>