[Cuis-dev] Really fast Fibonacci function

[Andres Valloud]

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
>>>
>>>