'From Squeak3.10beta of 22 July 2007 [latest update: #7159] on 18 June 2008 at 1:12:30 am'!
"Change Set: Integer-sqrtTruncated-M7099
Date: 18 June 2008
Author: nice
(x sqrtTrunctaed) is better than (x sqrt truncated) if these conditions are met:
- computation is fast
- result is not subject to rounding errors (Float inexact arithmetic)
This is an implementation"!
!Number methodsFor: 'arithmetic' stamp: 'nice 6/18/2008 01:12'!
sqrtRounded
"answer the square root of the receiver rounded to nearest integer.
This unvaluable default implementation is to be optimized in subclasses."
^self sqrt rounded! !
!Number methodsFor: 'arithmetic' stamp: 'nice 6/18/2008 01:12'!
sqrtTruncated
"answer the square root of the receiver truncated to nearest integer
This unvaluable default implementation is to be optimized in subclasses."
^self sqrt truncated! !
!Integer methodsFor: 'arithmetic' stamp: 'nice 6/18/2008 00:07'!
sqrtRounded
"see super. Optimized exact arithmetic version"
| x |
x := self sqrtTruncated.
^x squared + x - self >= 0
ifTrue: [x]
ifFalse: [x + 1]! !
!Integer methodsFor: 'arithmetic' stamp: 'nice 6/18/2008 00:08'!
sqrtTruncated
"see super. Optimized exact arithmetic version
Implementation notes:
Integer Square root using Newton's approximation.
Algorithm from Dr. Dobb's Journal of Software Tools for the Professional Programmer.
December 1987, page 50 by Ray Mariella -- with some help by Isaac Newton.
Performance over floating sqrt is on the order of 10 to 1.
Modified by nicolas cellier"
| sqrt |
self <= 0 ifTrue: [
self = 0
ifTrue: [^0]
ifFalse: [^ FloatingPointException signal: 'undefined if less than zero.']].
"Initial guess (under estimated)"
sqrt := 1 bitShift: self highBit - 1 // 2.
"Newtons method"
[sqrt := (self // sqrt + sqrt) bitShift: -1.
sqrt squared > self or: [(sqrt+1) squared <= self]] whileTrue.
^sqrt! !