The Trunk: Kernel-nice.1234.mcz

 Classic List Threaded
1 message
Reply | Threaded
Open this post in threaded view
|

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: '' 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 + + ^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 + + ^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 + + ^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 + + ^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 + + ^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!