Nicolas Cellier uploaded a new version of Kernel to project The Inbox:
http://source.squeak.org/inbox/Kernel-nice.1219.mcz

==================== Summary ====================

Name: Kernel-nice.1219
Author: nice
Time: 27 April 2019, 12:17:47.293648 pm
UUID: dc581577-0fd6-470c-82ed-58eaafcb7dbf
Ancestors: Kernel-nice.1218

Fix large digitDiv:neg: sign mess.
Remove a useless temp in fastMultiply
Comment toom3 reference better (The work of Bodrato Zanoni deserve it)

=============== Diff against Kernel-nice.1218 ===============

Item was changed:
  ----- Method: LargePositiveInteger>>digitDiv:neg: (in category 'private') -----
  digitDiv: anInteger neg: aBoolean 
  	"If length is worth, engage a recursive divide and conquer strategy"
  	| qr |
  	(anInteger digitLength <= 256
  			or: [self digitLength <= anInteger digitLength])
  		ifTrue: [^ self primDigitDiv: anInteger neg: aBoolean].
  	qr := self abs recursiveDigitDiv: anInteger abs.
+ 	self negative ifTrue: [qr at: 2 put: qr second negated].
+ 	aBoolean ifTrue: [qr at: 1 put: qr first negated].
+ 	^qr!
- 	^ aBoolean
- 		ifTrue: [qr collect: #negated]
- 		ifFalse: [qr]!

Item was changed:
  ----- Method: LargePositiveInteger>>fastMultiply: (in category 'arithmetic') -----
  fastMultiply: anInteger
  	"Eventually use Karatsuba or 3-way Toom-Cook algorithm to perform the multiplication"
  	
+ 	| xLen |
- 	| xLen yLen |
  	"arrange to have the receiver be the shorter"
+ 	(xLen := self digitLength) > anInteger digitLength
- 	(xLen := self digitLength) > (yLen := anInteger digitLength)
  		ifTrue: [^ anInteger fastMultiply: self ].
  
  	"If too short to be worth, fallback to naive algorithm"
  	(xLen >= 600) ifFalse: [^self * anInteger].
  	(xLen >= 6000) ifFalse: [^self karatsubaTimes: anInteger].
  	^self toom3Times: anInteger!

Item was changed:
  ----- Method: LargePositiveInteger>>toom3Times: (in category 'arithmetic') -----
  toom3Times: anInteger
  	"Eventually use a variant of Toom-Cooke for performing multiplication.
  	Toom-Cooke is a generalization of Karatsuba divide and conquer algorithm.
  	It divides operands in n parts instead of 2.
  	See https://en.wikipedia.org/wiki/Toom%E2%80%93Cook_multiplication
+ 	Here we divide each operand in 3 parts, thus the name Toom-3.
+ 	And use a Bodrato-Zanoni variant for the choice of interpolation points and matrix inversion
+ 	See What about Toom-Cook matrices optimality? - Marco Bodrato, Alberto Zanoni - Oct. 2006
+ 	http://www.bodrato.it/papers/WhatAboutToomCookMatricesOptimality.pdf"
- 	Here we divide each operand in 3 parts, thus the name Toom-3."
  	
  	| third x2 x1 x0 y2 y1 y0 xLen yLen y20 z4 z3 z2 z1 z0 x20 |
  	"arrange to have the receiver be the shorter"
  	(xLen := self digitLength) > (yLen := anInteger digitLength)
  		ifTrue: [^anInteger toom3Times: self ].
  
  	"If too short to be worth, fallback to Karatsuba algorithm"
  	(xLen > 6000) ifFalse: [^self karatsubaTimes: anInteger].
  	
  	"Seek for well balanced integers"
  	yLen > (5 * xLen bitShift: -2)
  		ifTrue: [^(0 to: yLen - 1 by: xLen + 1)  digitShiftSum: [:yShift |
  				self toom3Times: (anInteger copyDigitsFrom: yShift + 1 to: yShift +1 + xLen)]].
  	
  	"At this point, lengths are well balanced, divide in 3 parts"
  	third := yLen + 2 // 3 bitClear: 2r11.
  	x2 := self butLowestNDigits: third * 2.
  	x1 := self copyDigitsFrom: third + 1 to: third * 2.
  	x0 := self lowestNDigits: third.
  	y2 := anInteger butLowestNDigits: third * 2.
  	y1 := anInteger copyDigitsFrom: third + 1 to: third * 2.
  	y0 := anInteger lowestNDigits: third.
  	
  	"Toom-3 trick: 5 multiplications instead of 9"
  	z0 := x0 toom3Times: y0.
  	z4 := x2 toom3Times: y2.
  	x20 := x2 + x0.
  	y20 := y2 + y0.
  	z1 := x20 + x1 toom3Times: y20 + y1.
  	x20 := x20 - x1.
  	y20 := y20 - y1.
  	z2 := x20 toom3Times: y20.
  	z3 := (x20 + x2 bitShift: 1) - x0 toom3Times: (y20 + y2 bitShift: 1) - y0.
  	
  	"Sum the parts of decomposition"
  	z3 := z3 - z1 quo: 3.
  	z1 := z1 - z2 bitShift: -1.
  	z2 := z2 - z0.
  	
  	z3 := (z2 - z3 bitShift: -1) + (z4 bitShift: 1).
  	z2 := z2 + z1 - z4.
  	z1 := z1 - z3.
  	^z0 + (z1 bitShift: 8*third) + (z2 bitShift: 16*third) + (z3 + (z4 bitShift: 8*third) bitShift: 24*third)
  	
  "
  | a b |
  a :=5000 factorial - 1.
  b := 6000 factorial - 1.
  a digitLength min: b digitLength.
  a digitLength max: b digitLength.
  (a toom3Times: b) = (a * b) ifFalse: [self error].
  [Smalltalk garbageCollect.
  [300 timesRepeat: [a toom3Times: b]] timeToRun] value /
  [Smalltalk garbageCollect.
  [300 timesRepeat: [a karatsubaTimes: b]] timeToRun] value asFloat
  "!