Packages April 2019

packages@lists.squeakfoundation.org

1 participants
46 discussions

The Trunk: ToolBuilder-Morphic-jr.225.mcz
by commits＠source.squeak.org 29 Apr '19

29 Apr '19

Patrick Rein uploaded a new version of ToolBuilder-Morphic to project The Trunk: http://source.squeak.org/trunk/ToolBuilder-Morphic-jr.225.mcz ==================== Summary ==================== Name: ToolBuilder-Morphic-jr.225 Author: jr Time: 3 February 2019, 12:02:36.955839 am UUID: f93f39b3-2e20-ea44-b023-1ec44691e5e1 Ancestors: ToolBuilder-Morphic-mt.224 Fix: FileSaverDialog would answer 'nil' instead of nil when nothing was done except for accepting the dialog =============== Diff against ToolBuilder-Morphic-mt.224 =============== Item was changed: ----- Method: FileSaverDialog>>inputText: (in category 'filename') ----- inputText: aText "Initialize the filename entry field to aString. If a file with that name already exists, set up to highlight it." + aText ifNil: [^ self]. fileName := aText asString. self selectExistingFilename!

1 0

The Trunk: ToolBuilder-Morphic-pre.226.mcz
by commits＠source.squeak.org 29 Apr '19

29 Apr '19

Patrick Rein uploaded a new version of ToolBuilder-Morphic to project The Trunk: http://source.squeak.org/trunk/ToolBuilder-Morphic-pre.226.mcz ==================== Summary ==================== Name: ToolBuilder-Morphic-pre.226 Author: pre Time: 29 April 2019, 8:34:39.917145 pm UUID: 2f50877e-d948-2a4d-a14b-e73efca9711f Ancestors: ToolBuilder-Morphic-jr.225 Fix: FileSaverDialog would answer 'nil' instead of nil when nothing was done except for accepting the dialog Merged from inbox commit ToolBuilder-Morphic-jr.225 =============== Diff against ToolBuilder-Morphic-mt.224 =============== Item was changed: ----- Method: FileSaverDialog>>inputText: (in category 'filename') ----- inputText: aText "Initialize the filename entry field to aString. If a file with that name already exists, set up to highlight it." + aText ifNil: [^ self]. fileName := aText asString. self selectExistingFilename!

1 0

The Trunk: Morphic-pre.1488.mcz
by commits＠source.squeak.org 29 Apr '19

29 Apr '19

Patrick Rein uploaded a new version of Morphic to project The Trunk: http://source.squeak.org/trunk/Morphic-pre.1488.mcz ==================== Summary ==================== Name: Morphic-pre.1488 Author: pre Time: 29 April 2019, 8:20:28.689145 pm UUID: 72aff730-f2b8-9e4b-b830-b56fcf18438b Ancestors: Morphic-cmm.1487 Improves the check for whether a keystroke for the text morph for edit view will change the text to send the #editText callback. Refactors the check by creating a cached character set. =============== Diff against Morphic-cmm.1487 =============== Item was changed: TextMorph subclass: #TextMorphForEditView instanceVariableNames: 'editView acceptOnCR' + classVariableNames: 'DraggableTextSelection TextModificationCharacterSet' - classVariableNames: 'DraggableTextSelection' poolDictionaries: '' category: 'Morphic-Text Support'! Item was added: + ----- Method: TextMorphForEditView class>>defaultTextModificationCharacterSet (in category 'constants') ----- + defaultTextModificationCharacterSet + + ^ (ByteCharacterSet newFrom: (((0 to: 30) collect: [:code | Character value: code]) difference: Character separators asArray , {Character backspace})) complement! Item was added: + ----- Method: TextMorphForEditView class>>initialize (in category 'class initialization') ----- + initialize + + TextModificationCharacterSet := self defaultTextModificationCharacterSet! Item was added: + ----- Method: TextMorphForEditView class>>textModificationCharacterSet (in category 'constants') ----- + textModificationCharacterSet + + ^ TextModificationCharacterSet! Item was added: + ----- Method: TextMorphForEditView>>eventCharacterModifiesText: (in category 'private') ----- + eventCharacterModifiesText: aCharacter + + ^ self class textModificationCharacterSet includes: aCharacter! Item was changed: ----- Method: TextMorphForEditView>>keyStroke: (in category 'event handling') ----- keyStroke: evt | view | + editView deleteBalloon. self editor model: editView model. "For evaluateSelection" view := editView. "Copy into temp for case of a self-mutating doit" (acceptOnCR and: [evt keyCharacter = Character cr]) ifTrue: [^ self editor accept]. super keyStroke: evt. view scrollSelectionIntoView. "Make a cheap check and guess editing. (Alternative would be to copy the old contents and then compare them against the new ones. Maybe add a better hook in the TextEditor." + (self readOnly not and: [self eventCharacterModifiesText: evt keyCharacter]) + ifTrue: [view textEdited: self contents]! - (self readOnly not and: [evt keyCharacter isAlphaNumeric or: [evt keyCharacter isSeparator]]) - ifTrue: [view textEdited: self contents].!

1 0

The Trunk: MorphicTests-pre.50.mcz
by commits＠source.squeak.org 29 Apr '19

29 Apr '19

Patrick Rein uploaded a new version of MorphicTests to project The Trunk: http://source.squeak.org/trunk/MorphicTests-pre.50.mcz ==================== Summary ==================== Name: MorphicTests-pre.50 Author: pre Time: 29 April 2019, 8:16:16.145145 pm UUID: ac21cd61-1da9-5a47-9186-f3b430ce2218 Ancestors: MorphicTests-mt.49 Adds tests for the text morph for edit view which checks whether the right characters are filtered for editText: callbacks =============== Diff against MorphicTests-mt.49 =============== Item was added: + TestCase subclass: #TextMorphForEditViewTest + instanceVariableNames: 'morph' + classVariableNames: '' + poolDictionaries: '' + category: 'MorphicTests-Text Support'! Item was added: + ----- Method: TextMorphForEditViewTest>>setUp (in category 'running') ----- + setUp + + morph := TextMorphForEditView new! Item was added: + ----- Method: TextMorphForEditViewTest>>testCharactersModifyingText (in category 'tests') ----- + testCharactersModifyingText + + {$a . $: . $+ . Character backspace . Character delete . $2 . Character space . Character tab .$ü } do: [:char | + self assert: (morph eventCharacterModifiesText: char)] + ! Item was added: + ----- Method: TextMorphForEditViewTest>>testCharactersNotModifyingText (in category 'tests') ----- + testCharactersNotModifyingText + + #(0 1 2 3) do: [:charCode | + self deny: (morph eventCharacterModifiesText: (Character value: charCode))]!

1 0

The Trunk: Collections-fn.828.mcz
by commits＠source.squeak.org 29 Apr '19

29 Apr '19

Fabio Niephaus uploaded a new version of Collections to project The Trunk: http://source.squeak.org/trunk/Collections-fn.828.mcz ==================== Summary ==================== Name: Collections-fn.828 Author: fn Time: 29 April 2019, 12:52:37.794699 pm UUID: a663df49-93bf-413e-a942-29f1d0fa4605 Ancestors: Collections-nice.827 Character shouldNotImplement postCopy. =============== Diff against Collections-nice.827 =============== Item was added: + ----- Method: Character>>postCopy (in category 'copying') ----- + postCopy + "I will never be copied" + ^self shouldNotImplement!

1 0

The Trunk: Kernel-fn.1223.mcz
by commits＠source.squeak.org 29 Apr '19

29 Apr '19

Fabio Niephaus uploaded a new version of Kernel to project The Trunk: http://source.squeak.org/trunk/Kernel-fn.1223.mcz ==================== Summary ==================== Name: Kernel-fn.1223 Author: fn Time: 29 April 2019, 12:52:13.424813 pm UUID: 910aa151-72fe-4f6c-9645-fa735fb17f63 Ancestors: Kernel-nice.1222 SmallInteger and SmallFloat64 shouldNotImplement postCopy. =============== Diff against Kernel-nice.1222 =============== Item was added: + ----- Method: SmallFloat64>>postCopy (in category 'copying') ----- + postCopy + "I will never be copied" + ^self shouldNotImplement! Item was added: + ----- Method: SmallInteger>>postCopy (in category 'copying') ----- + postCopy + "I will never be copied" + ^self shouldNotImplement!

1 0

The Trunk: Kernel-nice.1222.mcz
by commits＠source.squeak.org 28 Apr '19

28 Apr '19

Nicolas Cellier uploaded a new version of Kernel to project The Trunk: http://source.squeak.org/trunk/Kernel-nice.1222.mcz ==================== Summary ==================== Name: Kernel-nice.1222 Author: nice Time: 28 April 2019, 3:55:49.124486 pm UUID: e697844c-d6bd-4781-a572-553f79c98644 Ancestors: Kernel-nice.1221 Make fastMultiply: the default for multiplying integers The scheme is: - first try 64bit imul (primitive 29) if receiver is Large, or (primitive 9) if receiver is Small. - then check for operand type in super *, use fastMultiply: if Integer - then check receiver length and invoke O(N^2) schoolbook multiply if too small ( invoke LargeIntegers primitive thru digitMultiply:neg: ) - then check operand byte length - then dispatch to Karatsuba or Toom3 (or future enhancements) For medium integers (>64 bits) that's only 1 indirection more than previous implementation, so a very small (negligible) penalty. For larger integers (a few thousand bits) that's a win. Note that the length threshold heuristics may vary from one platform to another, one VM to another, and wether images are 32 or 64 bits... We could make them class var, and offer some initialize method so as to automatically tune them. =============== Diff against Kernel-nice.1221 =============== Item was changed: ----- Method: Integer>>* (in category 'arithmetic') ----- * aNumber "Refer to the comment in Number * " aNumber isInteger ifTrue: + [^ self fastMultiply: aNumber]. - [^ self digitMultiply: aNumber - neg: self negative ~~ aNumber negative]. ^ aNumber adaptToInteger: self andSend: #*! Item was changed: + ----- Method: Integer>>fastMultiply: (in category 'private') ----- - ----- Method: Integer>>fastMultiply: (in category 'arithmetic') ----- fastMultiply: anInteger + ^self digitMultiply: anInteger + neg: self negative ~~ anInteger negative! - ^self * anInteger! Item was changed: + ----- Method: Integer>>karatsubaTimes: (in category 'private') ----- - ----- Method: Integer>>karatsubaTimes: (in category 'arithmetic') ----- karatsubaTimes: anInteger "Eventually use Karatsuba algorithm to perform the multiplication. This is efficient only for large integers (see subclass). By default, use regular multiplication." + ^ self digitMultiply: anInteger + neg: self negative ~~ anInteger negative! - ^self * anInteger! Item was changed: + ----- Method: Integer>>toom3Times: (in category 'private') ----- - ----- Method: Integer>>toom3Times: (in category 'arithmetic') ----- toom3Times: anInteger + ^ self digitMultiply: anInteger + neg: self negative ~~ anInteger negative! - ^self * anInteger! Item was changed: ----- Method: LargePositiveInteger>>digitDiv32: (in category 'private') ----- digitDiv32: anInteger "This is part of the recursive division algorithm from Burnikel - Ziegler Divide 3 limb (a2,a1,a0) by 2 limb (b1,b0). Each limb is made of p bytes (8*p bits). This step transforms the division problem into multiplication It must use the fastMultiply: to be worth the overhead costs." | a2 b1 d p q qr r | p := anInteger digitLength + 1 bitShift: -1. (a2 := self butLowestNDigits: 2*p) < (b1 := anInteger butLowestNDigits: p) ifTrue: [qr := (self butLowestNDigits: p) digitDiv21: b1. q := qr first. r := qr last] ifFalse: [q := (1 bitShift: 8*p) - 1. r := (self butLowestNDigits: p) - (b1 bitShift: 8*p) + b1]. + d := q * (anInteger lowestNDigits: p). - d := q fastMultiply: (anInteger lowestNDigits: p). r := (self lowestNDigits: p) + (r bitShift: 8*p) - d. [r < 0] whileTrue: [q := q - 1. r := r + anInteger]. ^Array with: q with: r ! Item was changed: + ----- Method: LargePositiveInteger>>fastMultiply: (in category 'private') ----- - ----- Method: LargePositiveInteger>>fastMultiply: (in category 'arithmetic') ----- fastMultiply: anInteger + "Return the result of multiplying the receiver by the Integer argument. + This method dispatch to the fastest algorithm based on operands length." - "Eventually use Karatsuba or 3-way Toom-Cook algorithm to perform the multiplication" + | length | + "Revert to schoolbook multiplication if short" + (length := self digitLength) < 600 + ifTrue: [^ self digitMultiply: anInteger + neg: self negative ~~ anInteger negative]. + + "Arrange to have the receiver be the shorter and retry" + length > anInteger digitLength - | xLen | - "arrange to have the receiver be the shorter" - (xLen := self digitLength) > anInteger digitLength ifTrue: [^ anInteger fastMultiply: self ]. + "Choose the fastest algorithm based on another heuristic" + length < 6000 ifTrue: [^self karatsubaTimes: anInteger]. - "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>>karatsubaTimes: (in category 'private') ----- - ----- Method: LargePositiveInteger>>karatsubaTimes: (in category 'arithmetic') ----- karatsubaTimes: anInteger "Eventually use Karatsuba algorithm to perform the multiplication The Karatsuba algorithm divide number in two smaller parts. Then it uses tricks to perform only 3 multiplications. See https://en.wikipedia.org/wiki/Karatsuba_algorithm" | half xHigh xLow yHigh yLow low high mid xLen yLen | + "Revert to schoolbook multiplication if short" + (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) - "arrange to have the receiver be the shorter" - (xLen := self digitLength) > (yLen := anInteger digitLength) ifTrue: [^ anInteger karatsubaTimes: self ]. - - "If too short to be worth, fallback to naive algorithm" - (xLen >= 600) ifFalse: [^self * anInteger]. "Seek for integers of about the same length, else split the long one" yLen >= (7 * xLen bitShift: -2) ifTrue: [^(0 to: yLen - 1 by: xLen + 1) digitShiftSum: [:yShift | self karatsubaTimes: (anInteger copyDigitsFrom: yShift + 1 to: yShift + 1 + xLen)]]. "At this point, lengths are similar, divide each integer in two halves" half := (yLen + 1 bitShift: -1) bitClear: 2r11. xLow := self lowestNDigits: half. xHigh := self butLowestNDigits: half. yLow := anInteger lowestNDigits: half. yHigh := anInteger butLowestNDigits: half. "Karatsuba trick: perform with 3 multiplications instead of 4" low := xLow karatsubaTimes: yLow. high := xHigh karatsubaTimes: yHigh. mid := high + low + (xHigh - xLow karatsubaTimes: yLow - yHigh). "Sum the parts of decomposition" ^low + (mid bitShiftMagnitude: 8*half) + (high bitShiftMagnitude: 16*half) " | a b | a := 650 factorial-1. b := 700 factorial-1. {a digitLength. b digitLength}. self assert: (a karatsubaTimes: b) - (a * b) = 0. [Smalltalk garbageCollect. [1000 timesRepeat: [a karatsubaTimes: b]] timeToRun] value / [Smalltalk garbageCollect. [1000 timesRepeat: [a * b]] timeToRun] value asFloat "! Item was changed: ----- Method: LargePositiveInteger>>squaredToom4 (in category 'mathematical functions') ----- squaredToom4 "Use a 4-way Toom-Cook divide and conquer algorithm to perform the multiplication. See Asymmetric Squaring Formulae Jaewook Chung and M. Anwar Hasan https://www.lirmm.fr/arith18/papers/Chung-Squaring.pdf" | p a0 a1 a2 a3 a02 a13 s0 s1 s2 s3 s4 s5 s6 t2 t3 | "divide in 4 parts" p := (self digitLength + 3 bitShift: -2) bitClear: 2r11. a3 := self butLowestNDigits: p * 3. a2 := self copyDigitsFrom: p * 2 + 1 to: p * 3. a1 := self copyDigitsFrom: p + 1 to: p * 2. a0 := self lowestNDigits: p. "Toom-4 trick: 7 multiplications instead of 16" a02 := a0 - a2. a13 := a1 - a3. s0 := a0 squared. + s1 := (a0 * a1) bitShift: 1. + s2 := (a02 + a13) * (a02 - a13). - s1 := (a0 fastMultiply: a1) bitShift: 1. - s2 := (a02 + a13) fastMultiply: (a02 - a13). s3 := ((a0 + a1) + (a2 + a3)) squared. + s4 := (a02 * a13) bitShift: 1. + s5 := (a3 * a2) bitShift: 1. - s4 := (a02 fastMultiply: a13) bitShift: 1. - s5 := (a3 fastMultiply: a2) bitShift: 1. s6 := a3 squared. "Interpolation" t2 := s1 + s5. t3 := (s2 + s3 + s4 bitShift: -1) - t2. s3 := t2 - s4. s4 := t3 - s0. s2 := t3 - s2 - s6. "Sum the parts of decomposition" ^s0 + (s1 bitShift: 8*p) + (s2 + (s3 bitShift: 8*p) bitShift: 16*p) +(s4 + (s5 bitShift: 8*p) + (s6 bitShift: 16*p) bitShift: 32*p) " | a | a := 770 factorial-1. a digitLength. [a * a - a squaredToom4 = 0] assert. [Smalltalk garbageCollect. [1000 timesRepeat: [a squaredToom4]] timeToRun] value / [Smalltalk garbageCollect. [1000 timesRepeat: [a squaredKaratsuba]] timeToRun] value asFloat "! Item was changed: + ----- Method: LargePositiveInteger>>toom3Times: (in category 'private') ----- - ----- 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" | third x2 x1 x0 y2 y1 y0 xLen yLen y20 z4 z3 z2 z1 z0 x20 | + "Revert to schoolbook multiplication if short" + (xLen := self digitLength) < 6000 + ifTrue: [^ self karatsubaTimes: anInteger ]. - "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]. + "Arrange to have the receiver be the shorter and retry" + xLen > (yLen := anInteger digitLength) + ifTrue: [^ anInteger toom3Times: self ]. + "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 "!

1 0

The Trunk: Kernel-nice.1221.mcz
by commits＠source.squeak.org 28 Apr '19

28 Apr '19

Nicolas Cellier uploaded a new version of Kernel to project The Trunk: http://source.squeak.org/trunk/Kernel-nice.1221.mcz ==================== Summary ==================== Name: Kernel-nice.1221 Author: nice Time: 28 April 2019, 2:31:07.899491 am UUID: 4aeee53e-f320-4ece-bf93-a5458f65bef3 Ancestors: Kernel-nice.1220 Fix broken pre-condition a3>=b/4 in sqrtRem. While at it, care to explain. =============== Diff against Kernel-nice.1220 =============== Item was changed: ----- Method: LargePositiveInteger>>sqrtRem (in category 'mathematical functions') ----- sqrtRem "Like super, but use a divide and conquer method to perform this operation. See Paul Zimmermann. Karatsuba Square Root. [Research Report] RR-3805, INRIA. 1999, pp.8. <inria-00072854> https://hal.inria.fr/inria-00072854/PDF/RR-3805.pdf" + | n qr q s r sr a3a2 a1 a0 | + "Split self in 4 digits a3,a2,a1,a0 in base b, + such that most significant digit a3 >= b/4 + It is not a problem to have a3 >= b, + so we can round b down to a whole number of bytes n" + n := self highBit bitShift: -5. "bitShift: -2 divide in 4 parts, bitShift: -3 round down in bytes" - | n qr q s r sr high mid low | - n := self digitLength bitShift: -2. n >= 16 ifFalse: [^super sqrtRem]. + a3a2 := self butLowestNDigits: n * 2. + a1 := self copyDigitsFrom: n + 1 to: n * 2. + a0 := self lowestNDigits: n. - high := self butLowestNDigits: n * 2. - mid := self copyDigitsFrom: n + 1 to: n * 2. - low := self lowestNDigits: n. + sr := a3a2 sqrtRem. + qr := (sr last bitShift: 8 * n) + a1 digitDiv: (sr first bitShift: 1) neg: false. - sr := high sqrtRem. - qr := (sr last bitShift: 8 * n) + mid digitDiv: (sr first bitShift: 1) neg: false. q := qr first normalize. s := (sr first bitShift: 8 * n) + q. + r := (qr last normalize bitShift: 8 * n) + a0 - q squared. - r := (qr last normalize bitShift: 8 * n) + low - q squared. r negative ifTrue: [r := (s bitShift: 1) + r - 1. s := s - 1]. sr at: 1 put: s; at: 2 put: r. ^sr !

1 0

The Trunk: KernelTests-nice.358.mcz
by commits＠source.squeak.org 28 Apr '19

28 Apr '19

Nicolas Cellier uploaded a new version of KernelTests to project The Trunk: http://source.squeak.org/trunk/KernelTests-nice.358.mcz ==================== Summary ==================== Name: KernelTests-nice.358 Author: nice Time: 28 April 2019, 1:51:22.467166 am UUID: 607e8c38-5586-4894-8e92-013e69fe774b Ancestors: KernelTests-nice.357 Slightly change the set of LargePositiveInteger probe and exhibit a problem in sqrtRem. This is because I did not respect the pre-condition that most significant digit a3 be at least 1/4th of the digit base b. a3 >= b/4 I made a confusion of log scale... I thought that a3 having at least 3/4 of the byte length of b was enough... Err! b/4 means that we can only offer 2 bit less than b! if self digitLength is a multiple of 4 bytes, and self most significand byte has two leading zero bits or more, the pre-condition is not OK... =============== Diff against KernelTests-nice.357 =============== Item was changed: ----- Method: LargePositiveIntegerTest>>x13kbits (in category 'accessing') ----- x13kbits "Return a 13 kilo bits integer" ^(15 to: 44 by: 4) + inject: 9753102468 - inject: 9876543210 into: [:big :bits | big * big << bits + bits]! Item was changed: ----- Method: LargePositiveIntegerTest>>x92kbits (in category 'accessing') ----- x92kbits "Return a 92 kilo bits integer" ^(11 to: 51 by: 4) + inject: 1357924680 - inject: 1234567890 into: [:big :bits | big * big << bits + bits]!

1 0

The Trunk: Collections-nice.827.mcz
by commits＠source.squeak.org 27 Apr '19

27 Apr '19

Nicolas Cellier uploaded a new version of Collections to project The Trunk: http://source.squeak.org/trunk/Collections-nice.827.mcz ==================== Summary ==================== Name: Collections-nice.827 Author: nice Time: 27 April 2019, 10:34:08.261332 pm UUID: 6dd69760-fdb4-4e8c-8809-38a4fb90b11e Ancestors: Collections-nice.826 Provide fastMultiply: helper #digitShiftSum: =============== Diff against Collections-nice.826 =============== Item was added: + ----- Method: Interval>>digitShiftSum: (in category 'enumerating') ----- + digitShiftSum: aBlock + "Reconstruct an Integer that has been split in chunks by using shift and add. + Each of my element represent a digitShift, an my step size repreent the digit length of chunks. + The block is evaluated with each digitShift to produce the chunks. + + Algorithm insights: + Let d0,d1,d2,... be the chunks, and s be the bit shift (8*step because digitLength is 8bits) + The naive loop does shift each chunk and accumulate into a sum: + ((d0 + (d1<<s)) + (d2<<s)) + (d3<<s) + ... + The length of accumulator increase at each iteration (1+2+3...) resulting in a cost (size+1)*size/2, or O(size^2) + Note that Horner scheme would be of about same cost + (((... + d3) << s + d2) << s + d1) << s + d0 + (a bit like so called Shlemiel the painter) + If we instead divide and conquer, we add smaller parts (1+1+2+...) resulting into a cost of O(size*log2(size)) + (d0 + (d1<<s)) + ((d2 + (d3<<s)) << s) + ... + However, the divide and conquer split comes with an additionnal cost, so do it only if worth it." + + | sz half offset | + "Naive loop in O(size^2)/2 is best for small size" + (sz := self size) <= 8 ifTrue: [^self inject: 0 into: [:sum :shift | ((aBlock value: shift) bitShift: 8 * shift) + sum]]. + half := sz // 2. + offset := half * step + start. + ^((start to: half - 1 * step + start by: step) digitShiftSum: aBlock) + + (((0 to: self last - offset by: step) digitShiftSum: [:k | aBlock value: offset + k]) bitShift: 8 * offset)!

1 0

2024

2023

2022

2021

2020

2019

2018

2017

2016

2015

2014

2013

2012

2011

2010

2009

2008

2007

2006

2005

Packages April 2019