[Cuis-dev] Really fast Fibonacci function

[Andres Valloud]

Hmmm, that code could have added a temporary variable to hold the sym of 
the digit lengths... that's essentially basicSize, btw.

On 12/7/19 18:42, Andres Valloud via Cuis-dev wrote:
> Like this:
> 
> Integer>>karatsubaTimes: anInteger
> 
>      ^anInteger * self
> 
> 
> LargeInteger>>karatsubaTimes: aLargeInteger
> 
>      | splitThreshold
>          selfHigh selfLow aLargeIntegerHigh aLargeIntegerLow
>          highProduct lowProduct mixedProduct lowTerm |
>      self digitLength + aLargeInteger digitLength > 768 ifFalse: [^self 
> * aLargeInteger].
>      splitThreshold := self digitLength + aLargeInteger digitLength * 2.
>      selfHigh := self bitShift: splitThreshold negated.
>      selfLow := self - (selfHigh bitShift: splitThreshold).
>      aLargeIntegerHigh := aLargeInteger bitShift: splitThreshold negated.
>      aLargeIntegerLow := aLargeInteger - (aLargeIntegerHigh bitShift: 
> splitThreshold).
>      highProduct := selfHigh karatsubaTimes: aLargeIntegerHigh.
>      lowProduct := selfLow karatsubaTimes: aLargeIntegerLow.
>      mixedProduct := selfLow + selfHigh karatsubaTimes: aLargeIntegerLow 
> + aLargeIntegerHigh.
>      lowTerm := mixedProduct - (lowProduct + highProduct).
>      ^((highProduct bitShift: splitThreshold)
>          + lowTerm bitShift: splitThreshold)
>              + lowProduct
> 
> 
> Note the care taken with the specific operations as well as the order in 
> which they are performed.
> 
> By the way, it looks like I didn't remember well: the threshold was 384 
> bytes, not bits --- so about 3k bits for both, or 1.5k bits each.
> 
> Andres.
> 
> On 12/7/19 18:32, Andres Valloud via Cuis-dev wrote:
>> (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
>>>>
>>>>