The Trunk: Kernel-nice.1221.mcz

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
  !