'From Squeak3.10beta of 22 July 2007 [latest update: #7159] on 18 June 2008 at 2:43:11 am'!
"Change Set: Fraction-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 optimized implementation for rationals"!
!Fraction methodsFor: 'arithmetic' stamp: 'nice 6/18/2008 02:06'!
sqrtRounded
"see super. Optimized exact arithmetic version
Implementation Note:
Let x == self sqrt,
E(x) is sqrtTruncated, sqrtRounded is E(x+0.5)
E(x+0.5) = E(x) if x-E(x) < 0.5, E(x)+1 otherwise.
That is x < (E(x)+0.5)
That is x squared < (E(x) squared + E(x) + (1/4))
That is self < (E(x) squared + E(x) + 4 reciprocal)
Multiply each side with 4*denominator
That is (4*numerator) < (denominator * (4 * (E(x) squared + E(x)) + 1))"
| x |
x := self sqrtTruncated.
^((x squared + x bitShift: 2) bitOr: 1) * denominator > (numerator bitShift: 2)
ifTrue: [x]
ifFalse: [x + 1]! !
!Fraction methodsFor: 'arithmetic' stamp: 'nice 6/18/2008 02:30'!
sqrtTruncated
"see super. Optimized exact arithmetic version
Implementation notes:
Integer Square root using Newton's approximation.
Coded to involve Fraction-less Integer arithmetic.
See also Integer>>sqrtTruncated"
| sqrt |
self <= 0 ifTrue: [
self = 0
ifTrue: [^0]
ifFalse: [^ FloatingPointException signal: 'undefined if less than zero.']].
"This test assumes there cannot be a Fraction with both numerator and denominator negative"
numerator < denominator ifTrue: [^0].
"Initial guess"
sqrt := 1 bitShift: numerator highBit - denominator highBit // 2.
"Newtons method"
[sqrt := (numerator // (denominator * sqrt) + sqrt) bitShift: -1.
sqrt squared * denominator > numerator or: [(sqrt+1) squared * denominator <= numerator]] whileTrue.
^sqrt! !
!ScaledDecimal methodsFor: 'arithmetic' stamp: 'nice 6/18/2008 01:36'!
sqrtRounded
"see super. Optimized exact arithmetic version"
^fraction sqrtRounded! !
!ScaledDecimal methodsFor: 'arithmetic' stamp: 'nice 6/18/2008 01:36'!
sqrtTruncated
"see super. Optimized exact arithmetic version"
^fraction sqrtTruncated! !