[Cuis-dev] Really fast Fibonacci function

[Nicolas Cellier]

Hi Agustin,
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...

Le sam. 7 déc. 2019 à 19:01, Agustín Sansone via Cuis-dev <
cuis-dev at lists.cuis.st> a écrit :

> A small improvement, still not faster:
> f := 170 factorial.
> [1000 timesRepeat: [f squared]] timeToRun.      5
> [1000 timesRepeat: [f karatsuba: f]] timeToRun.      77
>
> El sáb., 7 dic. 2019 a las 13:02, Agustín Sansone (<
> agustinsansone7 at gmail.com>) escribió:
>
>> Very quickly, Karatsuba's multiplication complexity of about n^1.6
>>> soundly beats the usual elementary n^2 multiplication algorithm, even if
>>> Karatsuba is implemented in the image while the n^2 algorithm is a VM
>>> primitive.
>>>
>>
>> Here is an implementation of Karatsuba's multiplication, but it doesn't
>> seem to work faster for big numbers, maybe I did something wrong:
>> f := 170 factorial.
>> [1000 timesRepeat: [f squared]] timeToRun. 5
>> [1000 timesRepeat: [f karatsuba: f]] timeToRun.  161
>>
>>
> --
> Cuis-dev mailing list
> Cuis-dev at lists.cuis.st
> https://lists.cuis.st/mailman/listinfo/cuis-dev
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191207/afb52312/attachment.htm>