[Cuis-dev] Really fast Fibonacci function

Agustín Sansone agustinsansone7 at gmail.com
Sat Dec 7 08:02:27 PST 2019


>
> 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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191207/a852f1e6/attachment.htm>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: Integer-karatsuba.st
Type: application/octet-stream
Size: 879 bytes
Desc: not available
URL: <http://lists.cuis.st/mailman/archives/cuis-dev/attachments/20191207/a852f1e6/attachment.obj>


More information about the Cuis-dev mailing list