The Trunk: Kernel-nice.1234.mcz

Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-nice.1234.mcz

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

Name: Kernel-nice.1234
Author: nice
Time: 14 May 2019, 12:40:59.140364 am
UUID: 3c271006-81c5-49e7-8131-b65c154b009f
Ancestors: Kernel-nice.1233

Introduce settable parameters for tuning the Large Integer arithmetic thresholds.

Use these parameters in the accelerated arithmetic.

For Burnikel Ziegler, ensure at least two recursions by using twice the threshold of digitDiv21: before engaging a digitDivSplit: - this somehow mitigates the overhead cost of digitDivSplit:

=============== Diff against Kernel-nice.1233 ===============

Item was changed:
  Integer variableByteSubclass: #LargePositiveInteger
  instanceVariableNames: ''
+ classVariableNames: 'ThresholdForDiv21 ThresholdForMul22 ThresholdForMul33 ThresholdForSqrt ThresholdForSquaredByFourth ThresholdForSquaredByHalf'
- classVariableNames: ''
  poolDictionaries: ''
  category: 'Kernel-Numbers'!
 
  !LargePositiveInteger commentStamp: '<historical>' prior: 0!
  I represent positive integers of more than 30 bits (ie, >= 1073741824).  These values are beyond the range of SmallInteger, and are encoded here as an array of 8-bit digits.  Care must be taken, when new values are computed, that any result that COULD BE a SmallInteger IS a SmallInteger (see normalize).
 
  Note that the bit manipulation primitives, bitAnd:, bitShift:, etc., = and ~= run without failure (and therefore fast) if the value fits in 32 bits.  This is a great help to the simulator.!

Item was added:
+ ----- Method: LargePositiveInteger class>>thresholdForDiv21 (in category 'accessing') -----
+ thresholdForDiv21
+ <preference: 'Threshold for division by Burnikel-Ziegler recursive split'
+ category: 'Arithmetic'
+ description: 'The number of byte-digit above which recursive division is more efficient than schoolbook division'
+ type: #Number>
+ ^ThresholdForDiv21 ifNil: [256]!

Item was added:
+ ----- Method: LargePositiveInteger class>>thresholdForDiv21: (in category 'accessing') -----
+ thresholdForDiv21: anIntegerOrNil
+ "the number of byte-digit above which schoolbook division is more efficient than recursive division"
+ ThresholdForDiv21 := anIntegerOrNil ifNotNil: [:t | t max: Smalltalk wordSize]!

Item was added:
+ ----- Method: LargePositiveInteger class>>thresholdForMul22 (in category 'accessing') -----
+ thresholdForMul22
+ <preference: 'Threshold for multiplication by 2-way Karatsuba'
+ category: 'Arithmetic'
+ description: 'The number of byte-digit above which Karatsuba is more efficient than schoolbook'
+ type: #Number>
+ ^ThresholdForMul22 ifNil: [600]!

Item was added:
+ ----- Method: LargePositiveInteger class>>thresholdForMul22: (in category 'accessing') -----
+ thresholdForMul22: anIntegerOrNil
+ "the number of byte-digit above which Karatsuba is more efficient than schoolbook"
+ ThresholdForMul22 := anIntegerOrNil ifNotNil: [:t | t max: Smalltalk wordSize + 1]!

Item was added:
+ ----- Method: LargePositiveInteger class>>thresholdForMul33 (in category 'accessing') -----
+ thresholdForMul33
+ <preference: 'Threshold for multiplication by 3-way Toom-Cook'
+ category: 'Arithmetic'
+ description: 'The number of byte-digit above which 3-way Toom-Cook is more efficient than Karatsuba'
+ type: #Number>
+ ^ThresholdForMul33 ifNil: [2000]!

Item was added:
+ ----- Method: LargePositiveInteger class>>thresholdForMul33: (in category 'accessing') -----
+ thresholdForMul33: anIntegerOrNil
+ "the number of byte-digit above which 3-way Toom-Cook is more efficient than Karatsuba"
+ ThresholdForMul33 := anIntegerOrNil ifNotNil: [:t | t max: Smalltalk wordSize + 1]!

Item was added:
+ ----- Method: LargePositiveInteger class>>thresholdForSquaredByFourth (in category 'accessing') -----
+ thresholdForSquaredByFourth
+ <preference: 'Threshold for squaring by 4-way Toom-Cook'
+ category: 'Arithmetic'
+ description: 'The number of byte-digit above which 4-way Toom-Cook squaring is more efficient than Karatsuba'
+ type: #Number>
+ ^ThresholdForSquaredByFourth ifNil: [800]!

Item was added:
+ ----- Method: LargePositiveInteger class>>thresholdForSquaredByFourth: (in category 'accessing') -----
+ thresholdForSquaredByFourth: anIntegerOrNil
+ "the number of byte-digit above which 4-way Toom-Cook squaring is more efficient than Karatsuba"
+ ^ThresholdForSquaredByFourth := anIntegerOrNil ifNotNil: [:t | t max: Smalltalk wordSize]!

Item was added:
+ ----- Method: LargePositiveInteger class>>thresholdForSquaredByHalf (in category 'accessing') -----
+ thresholdForSquaredByHalf
+ <preference: 'Threshold for squaring by 2-way Karatsuba'
+ category: 'Arithmetic'
+ description: 'The number of byte-digit above which Karatsuba squaring is more efficient than schoolbook multiplication'
+ type: #Number>
+ ^ThresholdForSquaredByHalf ifNil: [400]!

Item was added:
+ ----- Method: LargePositiveInteger class>>thresholdForSquaredByHalf: (in category 'accessing') -----
+ thresholdForSquaredByHalf: anIntegerOrNil
+ "the number of byte-digit above which Karatsuba squaring is more efficient than schoolbook multiplication"
+ ^ThresholdForSquaredByHalf := anIntegerOrNil ifNotNil: [:t | t max: Smalltalk wordSize]!

Item was changed:
  ----- Method: LargePositiveInteger>>digitDiv21: (in category 'private') -----
  digitDiv21: anInteger
  "This is part of the recursive division algorithm from Burnikel - Ziegler
  Divide a two limbs receiver by 1 limb dividend
  Each limb is decomposed in two halves of p bytes (8*p bits)
  so as to continue the recursion"
 
  | p qr1 qr2 |
  p := (anInteger digitLength + 1 bitShift: -1) bitClear: 2r11.
+ p < self class thresholdForDiv21 ifTrue: [^(self digitDiv: anInteger neg: false) collect: #normalize].
- p <= 256 ifTrue: [^(self digitDiv: anInteger neg: false) collect: #normalize].
  qr1 := (self butLowestNDigits: p) digitDiv32: anInteger.
  qr2 := (self lowestNDigits: p) + (qr1 last bitShift: 8*p) digitDiv32: anInteger.
  qr2 at: 1 put: (qr2 at: 1) + ((qr1 at: 1) bitShift: 8*p).
  ^qr2!

Item was changed:
  ----- Method: LargePositiveInteger>>divideByInteger: (in category 'private') -----
  divideByInteger: anInteger
  "If length is worth, engage a recursive divide and conquer strategy,
  more efficient than super"
  | qr |
+ (anInteger digitLength < (self class thresholdForDiv21 * 2)
- (anInteger digitLength <= 256
  or: [self digitLength <= anInteger digitLength])
  ifTrue: [^ self digitDiv: anInteger neg: self negative ~~ anInteger negative].
  qr := self abs digitDivSplit: anInteger abs.
  self negative ifTrue: [qr at: 2 put: qr second negated].
  self negative = anInteger negative ifFalse: [qr at: 1 put: qr first negated].
  ^qr!

Item was changed:
  ----- Method: LargePositiveInteger>>multiplyByInteger: (in category 'private') -----
  multiplyByInteger: anInteger
  "Return the result of multiplying the receiver by the Integer argument.
  This method dispatch to the fastest algorithm based on operands length."
 
  | xLen yLen |
  "Revert to schoolbook multiplication if short"
+ (xLen := self digitLength) < self class thresholdForMul22
- (xLen := self digitLength) < 600
  ifTrue: [^ self digitMultiply: anInteger
  neg: self negative ~~ anInteger negative].
 
  "Arrange to have the receiver be the shorter and retry"
  xLen > (yLen := anInteger digitLength)
  ifTrue: [^ anInteger multiplyByInteger: self ].
 
  "Seek for integers of about the same length, else split the long one"
  yLen > (2 * xLen) ifTrue: [^self digitMulSplit: anInteger].
 
  "Choose the fastest divide and conquer algorithm based on another heuristic"
+ xLen >= self class thresholdForMul33 ifTrue: [^self digitMul33: anInteger].
- xLen >= 2000 ifTrue: [^self digitMul33: anInteger].
  yLen * 2 >= (3 * xLen) ifTrue: [^self digitMul23: anInteger].
  ^self digitMul22: anInteger!

Item was changed:
  ----- Method: LargePositiveInteger>>squared (in category 'mathematical functions') -----
  squared
  "Eventually use a divide and conquer algorithm to perform the multiplication"
 
+ (self digitLength >= self class thresholdForSquaredByHalf) ifFalse: [^self * self].
+ (self digitLength >= self class thresholdForSquaredByFourth) ifFalse: [^self squaredByHalf].
- (self digitLength >= 400) ifFalse: [^self * self].
- (self digitLength >= 800) ifFalse: [^self squaredByHalf].
  ^self squaredByFourth!