## [squeak-dev] The Trunk: Kernel-nice.1221.mcz

commits at source.squeak.org commits at source.squeak.org
Sun Apr 28 00:43:50 UTC 2019

```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
!

```