[Cuis-dev] Really fast Fibonacci function

[Andres Valloud]

(never mind the divisions, ouch!)

On 12/7/19 18:29, Andres Valloud via Cuis-dev wrote:
> 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
>>
>>