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 !
packages@lists.squeakfoundation.org