[Cuis-dev] Really fast Fibonacci function

[Andres Valloud]

Use base 2 rather than base 10, then those multiplications become bit 
shifts.

On 12/7/19 10:01, Agustín Sansone via Cuis-dev wrote:
> 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 <mailto: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
> 
>