[squeak-dev] Exact #sqrt
Nicolas Cellier
nicolas.cellier.aka.nice at gmail.com
Mon Oct 17 20:46:21 UTC 2011
Hi Juan,
Finally, why didn't you just tried some sort of Newton ?
nthRootTruncated: aPositiveInteger
"Answer the integer part of the nth root of the receiver."
| guess guessToTheNthMinusOne delta |
self = 0 ifTrue: [^0].
self negative
ifTrue:
[aPositiveInteger even ifTrue: [ ArithmeticError signal: 'Negative
numbers don''t have even roots.' ].
^(self negated nthRootFloor: aPositiveInteger) negated].
guess := 1 bitShift: self highBitOfMagnitude + aPositiveInteger - 1
// aPositiveInteger.
[
guessToTheNthMinusOne := guess raisedToInteger: aPositiveInteger - 1.
delta := (guess * guessToTheNthMinusOne - self) //
(guessToTheNthMinusOne * aPositiveInteger).
delta = 0 ] whileFalse:
[ guess := guess - delta ].
( (guess := guess - 1) raisedToInteger: aPositiveInteger) > self ifTrue:
[ guess := guess - 1 ].
^guess
It's not exactly cheap (repeated raisedTo:) but it should work without Fraction.
Note that selector is named Truncated not Floor, because it better
reflects the operation on negative receivers.
Nicolas
2011/10/14 Juan Vuletich <juan at jvuletich.org>:
> Nicolas Cellier wrote:
>>
>> You might also want another way to quickly discriminate non square
>> large integers
>>
>> http://en.wikipedia.org/wiki/Square_number
>>
>> if (n & 7 == 1) or (n & 31 == 4) or (n & 127 == 16) or (n & 191 == 0) then
>> return n is probably square
>> else
>> return n is definitely not square
>>
>> LargePositiveInteger>>canBeASquare
>> | lsb |
>> lsb := self digitAt: 1.
>> ^((lsb bitAnd: 7) = 1
>> or: [(lsb bitAnd: 31) = 4
>> or: [(lsb bitAnd: 127) = 16
>> or: [(lsb bitAnd: 191) = 0]]])
>>
>> Nicolas
>>
>> 2011/10/13 Nicolas Cellier <nicolas.cellier.aka.nice at gmail.com>:
>>
>>>
>>> This can cause an overflow...
>>>
>>> ((1 << 1024 + 1) / (1 << 1024 + 3)) sqrt
>>>
>>> I'd expect 1.0 (inexact, but not that much).
>>>
>
> Thanks, Nicolas. This new version addresses all the issues you raised.
>
> Cheers,
> Juan Vuletich
>
> 'From Cuis 3.3 of 2 June 2011 [latest update: #1024] on 14 October 2011 at
> 7:57:15 am'!
>
> !FloatTest methodsFor: 'testing' stamp: 'jmv 10/11/2011 08:55'!
> testMaxExactInteger
> "
> FloatTest new testMaxExactInteger
> "
>
> self assert: Float maxExactInteger asFloat truncated = Float
> maxExactInteger.
> 0 to: 10000 do: [ :j |
> self assert: (Float maxExactInteger-j) asFloat truncated =
> (Float maxExactInteger-j) ].
> self deny: (Float maxExactInteger+1) asFloat truncated = (Float
> maxExactInteger+1)
> ! !
>
> !FloatTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/13/2011 09:06'!
> testNthRoot
> "
> FloatTest new testNthRoot
> "
> self should: [ -1.23 nthRoot: 4 ] raise: ArithmeticError! !
>
> !FloatTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/13/2011 09:06'!
> testRaisedTo
> "
> FloatTest new testRaisedTo
> "
> self should: [ -1.23 raisedTo: 1/4 ] raise: ArithmeticError! !
>
>
> !FractionTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/11/2011 22:27'!
> testExactRaisedTo
> "
> FractionTest new testExactRaisedTo
> "
> | f |
> self assert: (4/9 raisedTo: 1/2) classAndValueEquals: 2/3.
> self assert: (9/4 raisedTo: 1/2) classAndValueEquals: 3/2.
> #( 1 5 29 135 1234 567890 123123123 456456456456
> 98765432109876543210987654321
> 987123987123987123987123987123987123987123987123) pairsDo: [ :a :b |
> f _ a / b.
> self assert: (f squared raisedTo: 1/2) classAndValueEquals:
> f.
> self assert: (f negated squared raisedTo: 1/2)
> classAndValueEquals: f.
> f _ b / a.
> self assert: (f squared raisedTo: 1/2) classAndValueEquals:
> f.
> self assert: (f negated squared raisedTo: 1/2)
> classAndValueEquals: f ].
>
> self assert: (8/27 raisedTo: 1/3) classAndValueEquals: 2/3.
> self assert: (27/8 raisedTo: 1/3) classAndValueEquals: 3/2.
> #( 1 5 29 135 1234 567890 123123123 456456456456
> 98765432109876543210987654321
> 987123987123987123987123987123987123987123987123) pairsDo: [ :a :b |
> f _ a / b.
> self assert: ((f raisedTo: 3) raisedTo: 1/3)
> classAndValueEquals: f.
> self assert: ((f negated raisedTo: 3) raisedTo: 1/3)
> classAndValueEquals: f negated.
> f _ b / a.
> self assert: ((f raisedTo: 3) raisedTo: 1/3)
> classAndValueEquals: f.
> self assert: ((f negated raisedTo: 3) raisedTo: 1/3)
> classAndValueEquals: f negated ].
>
> self assert: (4/9 raisedTo: 3/2) classAndValueEquals: 8/27.
> self assert: (8/27 raisedTo: 2/3) classAndValueEquals: 4/9.
> #( 1 5 29 135 1234 567890 123123123 456456456456
> 98765432109876543210987654321
> 987123987123987123987123987123987123987123987123) pairsDo: [ :a :b |
> f _ a / b.
> self assert: ((f raisedTo: 3) raisedTo: 2/3)
> classAndValueEquals: f*f.
> self assert: ((f raisedTo: 2) raisedTo: 3/2)
> classAndValueEquals: f*f*f.
> self assert: ((f negated raisedTo: 3) raisedTo: 2/3)
> classAndValueEquals: f*f.
> self assert: ((f negated raisedTo: 2) raisedTo: 3/2)
> classAndValueEquals: f*f*f.
> f _ b / a.
> self assert: ((f raisedTo: 3) raisedTo: 2/3)
> classAndValueEquals: f*f.
> self assert: ((f raisedTo: 2) raisedTo: 3/2)
> classAndValueEquals: f*f*f.
> self assert: ((f negated raisedTo: 3) raisedTo: 2/3)
> classAndValueEquals: f*f.
> self assert: ((f negated raisedTo: 2) raisedTo: 3/2)
> classAndValueEquals: f*f*f ].
>
> self assert: (32/243 raisedTo: 3/5) classAndValueEquals: 8/27.
> self assert: (8/27 raisedTo: 5/3) classAndValueEquals: 32/243.
> #( 1 5 29 135 1234 567890 123123123 456456456456
> 98765432109876543210987654321
> 987123987123987123987123987123987123987123987123) pairsDo: [ :a :b |
> f _ a / b.
> self assert: ((f raisedTo: 5) raisedTo: 3/5)
> classAndValueEquals: f*f*f.
> self assert: ((f raisedTo: 3) raisedTo: 5/3)
> classAndValueEquals: f*f*f*f*f.
> self assert: ((f negated raisedTo: 5) raisedTo: 3/5)
> classAndValueEquals: (f*f*f) negated.
> self assert: ((f negated raisedTo: 3) raisedTo: 5/3)
> classAndValueEquals: (f*f*f*f*f) negated.
>
> self assert: ((f raisedTo: -5) raisedTo: 3/5)
> classAndValueEquals: 1/(f*f*f).
> self assert: ((f raisedTo: -3) raisedTo: 5/3)
> classAndValueEquals: 1/(f*f*f*f*f).
> self assert: ((f negated raisedTo: -5) raisedTo: 3/5)
> classAndValueEquals: -1/(f*f*f).
> self assert: ((f negated raisedTo: -3) raisedTo: 5/3)
> classAndValueEquals: -1/(f*f*f*f*f).
> self assert: ((f raisedTo: 5) raisedTo: -3/5)
> classAndValueEquals: 1/(f*f*f).
> self assert: ((f raisedTo: 3) raisedTo: -5/3)
> classAndValueEquals: 1/(f*f*f*f*f).
> self assert: ((f negated raisedTo: 5) raisedTo: -3/5)
> classAndValueEquals: -1/(f*f*f).
> self assert: ((f negated raisedTo: 3) raisedTo: -5/3)
> classAndValueEquals: -1/(f*f*f*f*f).
>
> "No exact result => Float result"
> self assert: ((f raisedTo: 3) +1 raisedTo: 5/3) isFloat.
> self assert: ((f negated raisedTo: 3) -1 raisedTo: 5/3)
> isFloat.
>
> f _ b / a.
> self assert: ((f raisedTo: 5) raisedTo: 3/5)
> classAndValueEquals: f*f*f.
> self assert: ((f raisedTo: 3) raisedTo: 5/3)
> classAndValueEquals: f*f*f*f*f.
> self assert: ((f negated raisedTo: 5) raisedTo: 3/5)
> classAndValueEquals: (f*f*f) negated.
> self assert: ((f negated raisedTo: 3) raisedTo: 5/3)
> classAndValueEquals: (f*f*f*f*f) negated.
>
> "No exact result => Float result"
> self assert: ((f raisedTo: 3) +1 raisedTo: 5/3) isFloat.
> self assert: ((f negated raisedTo: 3) -1 raisedTo: 5/3)
> isFloat ].! !
>
> !FractionTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/11/2011 22:12'!
> testExactSqrt
> "
> FractionTest new testExactSqrt
> "
> | f |
> self assert: (4/9) sqrt classAndValueEquals: 2/3.
> #( 1 5 29 135 1234 567890 123123123 456456456456
> 98765432109876543210987654321
> 987123987123987123987123987123987123987123987123) pairsDo: [ :i :j |
> f _ i / j.
> self assert: f squared sqrt classAndValueEquals: f.
> f _ j / i.
> self assert: f squared sqrt classAndValueEquals: f ]! !
>
> !FractionTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/13/2011 21:38'!
> testInexactRaisedTo
> "
> FractionTest new testInexactRaisedTo
> "
> self assert: (((1 << 1024 + 1) / (1 << 1024 + 3)) raisedTo: 1/3) =
> 1.0.
> self assert: (((1 << 1024 + 1) / (1 << 1024 + 3)) negated raisedTo:
> 1/3) = -1.0! !
>
> !FractionTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/13/2011 21:27'!
> testInexactSqrt
> "
> FractionTest new testInexactSqrt
> "
> self assert: ((1 << 1024 + 1) / (1 << 1024 + 3)) sqrt = 1.0! !
>
> !FractionTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/13/2011 21:49'!
> testRaisedToErrorConditions
> "
> FractionTest new testRaisedToErrorConditions
> "
> self should: [ (-1/16) raisedTo: 1/4 ] raise: ArithmeticError.
> self should: [ ((1 << 1024 + 1) / (1 << 1024 + 3)) negated raisedTo:
> 1/4 ] raise: ArithmeticError! !
>
> !FractionTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/13/2011 21:48'!
> testSqrtErrorConditions
> "
> FractionTest new testSqrtErrorConditions
> "
> self should: [ (-1/4) sqrt ] raise: DomainError.
> self should: [ ((1 << 1024 + 1) / (1 << 1024 + 3)) negated sqrt ]
> raise: DomainError! !
>
> !FractionTest methodsFor: 'private' stamp: 'jmv 10/11/2011 22:12'!
> assert: a classAndValueEquals: b
> self assert: a class = b class.
> self assert: a = b! !
>
>
> !IntegerTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/13/2011 21:46'!
> testExactRaisedTo
> "
> IntegerTest new testExactRaisedTo
> "
> self assert: (4 raisedTo: 1/2) classAndValueEquals: 2.
> self assert: (9 raisedTo: 1/2) classAndValueEquals: 3.
> self assert: (9 raisedTo: -1/2) classAndValueEquals: 1/3.
> self assert: (-1 raisedTo: 1/3) classAndValueEquals: -1.
> #( 1 5 29 135 1234 567890 123123123 456456456456
> 98765432109876543210987654321
> 987123987123987123987123987123987123987123987123) do: [ :i |
> self assert: (i squared raisedTo: 1/2) classAndValueEquals:
> i.
> self assert: (i negated squared raisedTo: 1/2)
> classAndValueEquals: i ].
>
> self assert: (8 raisedTo: 1/3) classAndValueEquals: 2.
> self assert: (27 raisedTo: 1/3) classAndValueEquals: 3.
> #( 1 5 29 135 1234 567890 123123123 456456456456
> 98765432109876543210987654321
> 987123987123987123987123987123987123987123987123) do: [ :i |
> self assert: ((i raisedTo: 3) raisedTo: 1/3)
> classAndValueEquals: i.
> self assert: ((i negated raisedTo: 3) raisedTo: 1/3)
> classAndValueEquals: i negated ].
>
> self assert: (4 raisedTo: 3/2) classAndValueEquals: 8.
> self assert: (8 raisedTo: 2/3) classAndValueEquals: 4.
> self assert: (8 raisedTo: -2/3) classAndValueEquals: 1/4.
> #( 1 5 29 135 1234 567890 123123123 456456456456
> 98765432109876543210987654321
> 987123987123987123987123987123987123987123987123) do: [ :i |
> self assert: ((i raisedTo: 3) raisedTo: 2/3)
> classAndValueEquals: i*i.
> self assert: ((i raisedTo: 2) raisedTo: 3/2)
> classAndValueEquals: i*i*i.
> self assert: ((i negated raisedTo: 3) raisedTo: 2/3)
> classAndValueEquals: i*i.
> self assert: ((i negated raisedTo: 2) raisedTo: 3/2)
> classAndValueEquals: i*i*i ].
>
> self assert: (32 raisedTo: 3/5) classAndValueEquals: 8.
> self assert: (8 raisedTo: 5/3) classAndValueEquals: 32.
> #( 1 5 29 135 1234 567890 123123123 456456456456
> 98765432109876543210987654321
> 987123987123987123987123987123987123987123987123) do: [ :i |
> self assert: ((i raisedTo: 5) raisedTo: 3/5)
> classAndValueEquals: i*i*i.
> self assert: ((i raisedTo: 3) raisedTo: 5/3)
> classAndValueEquals: i*i*i*i*i.
> self assert: ((i negated raisedTo: 5) raisedTo: 3/5)
> classAndValueEquals: (i*i*i) negated.
> self assert: ((i negated raisedTo: 3) raisedTo: 5/3)
> classAndValueEquals: (i*i*i*i*i) negated.
>
> self assert: ((i raisedTo: -5) raisedTo: 3/5)
> classAndValueEquals: 1/(i*i*i).
> self assert: ((i raisedTo: -3) raisedTo: 5/3)
> classAndValueEquals: 1/(i*i*i*i*i).
> self assert: ((i negated raisedTo: -5) raisedTo: 3/5)
> classAndValueEquals: -1/(i*i*i).
> self assert: ((i negated raisedTo: -3) raisedTo: 5/3)
> classAndValueEquals: -1/(i*i*i*i*i).
>
> self assert: ((i raisedTo: 5) raisedTo: -3/5)
> classAndValueEquals: 1/(i*i*i).
> self assert: ((i raisedTo: 3) raisedTo: -5/3)
> classAndValueEquals: 1/(i*i*i*i*i).
> self assert: ((i negated raisedTo: 5) raisedTo: -3/5)
> classAndValueEquals: -1/(i*i*i).
> self assert: ((i negated raisedTo: 3) raisedTo: -5/3)
> classAndValueEquals: -1/(i*i*i*i*i).
>
> "No exact result => Float result"
> self assert: ((i raisedTo: 3) +1 raisedTo: 5/3) isFloat.
> self assert: ((i negated raisedTo: 3) -1 raisedTo: 5/3)
> isFloat ].! !
>
> !IntegerTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/11/2011 22:09'!
> testExactSqrt
> "
> IntegerTest new testExactSqrt
> "
> self assert: 4 sqrt classAndValueEquals: 2.
> self assert: 9 sqrt classAndValueEquals: 3.
> self assert: Float maxExactInteger squared sqrt classAndValueEquals:
> Float maxExactInteger.
> self assert: (Float maxExactInteger+1) squared sqrt
> classAndValueEquals: Float maxExactInteger+1.
> #( 1 5 29 135 1234 567890 123123123 456456456456
> 98765432109876543210987654321
> 987123987123987123987123987123987123987123987123) do: [ :i |
> self assert: i squared sqrt classAndValueEquals: i ]! !
>
> !IntegerTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/13/2011 09:09'!
> testNthRootErrorConditions
> "
> IntegerTest new testExactRaisedToErrorConditions
> "
>
> self should: [ -2 nthRoot: 1/4 ] raise: ArithmeticError.
> self should: [ -2 nthRoot: 1.24 ] raise: ArithmeticError.! !
>
> !IntegerTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/13/2011 21:45'!
> testRaisedToErrorConditions
> "
> IntegerTest new testRaisedToErrorConditions
> "
>
> self should: [ -2 raisedTo: 1/4 ] raise: ArithmeticError.
> self should: [ -2 raisedTo: 1.24 ] raise: ArithmeticError.! !
>
> !IntegerTest methodsFor: 'tests - mathematical functions' stamp: 'jmv
> 10/13/2011 21:46'!
> testSqrtErrorConditions
> "
> IntegerTest new testSqrtErrorConditions
> "
>
> self should: [ -1 sqrt ] raise: ArithmeticError! !
>
> !IntegerTest methodsFor: 'private' stamp: 'jmv 10/11/2011 08:14'!
> assert: a classAndValueEquals: b
> self assert: a class = b class.
> self assert: a = b! !
>
>
> !Number methodsFor: 'mathematical functions' stamp: 'jmv 10/13/2011 08:36'!
> nthRoot: aPositiveInteger
> "Answer the nth root of the receiver."
>
> self subclassResponsibility! !
>
> !Number methodsFor: 'mathematical functions' stamp: 'jmv 10/13/2011 08:50'!
> raisedTo: aNumber
> "Answer the receiver raised to aNumber."
>
> aNumber isInteger ifTrue: [
> "Do the special case of integer power"
> ^ self raisedToInteger: aNumber].
> aNumber isFraction ifTrue: [
> "Special case for fraction power"
> ^ (self nthRoot: aNumber denominator) raisedToInteger:
> aNumber numerator ].
> self < 0 ifTrue: [
> ^ ArithmeticError signal: 'Negative numbers can''t be raised
> to float powers.' ].
> 0 = aNumber ifTrue: [^ self class one]. "Special case of exponent=0"
> 1 = aNumber ifTrue: [^ self]. "Special case of exponent=1"
> 0 = self ifTrue: [ "Special case of self
> = 0"
> aNumber < 0
> ifTrue: [^ (ZeroDivide dividend: self) signal]
> ifFalse: [^ self]].
> ^ (aNumber * self ln) exp "Otherwise use logarithms"! !
>
> !Number methodsFor: 'mathematical functions' stamp: 'jmv 10/11/2011 08:34'!
> sqrt
> "Answer the square root of the receiver."
>
> self subclassResponsibility! !
>
>
> !Float methodsFor: 'mathematical functions' stamp: 'jmv 10/13/2011 09:03'!
> nthRoot: aPositiveInteger
> "Answer the nth root of the receiver."
> aPositiveInteger = 2 ifTrue: [
> ^self sqrt ].
>
> (aPositiveInteger isInteger not or: [ aPositiveInteger negative ])
> ifTrue: [^ ArithmeticError signal: 'nth root only defined for
> positive Integer n.'].
>
> ^self negative
> ifTrue: [
> aPositiveInteger odd
> ifTrue: [ (self negated raisedTo: 1.0 /
> aPositiveInteger) negated ]
> ifFalse: [ ArithmeticError signal: 'Negative
> numbers don''t have even roots.' ]]
> ifFalse: [ self raisedTo: 1.0 / aPositiveInteger ]! !
>
>
> !Float class methodsFor: 'constants' stamp: 'jmv 10/13/2011 19:57'!
> maxExactInteger
> "Answer the biggest integer such that it is exactly represented in a
> float, and all smaller integers also are"
> ^1 bitShift: self precision! !
>
>
> !Fraction methodsFor: 'mathematical functions' stamp: 'jmv 10/13/2011
> 21:38'!
> nthRoot: aPositiveInteger
> "Answer the nth root of the receiver."
>
> | d n |
> n _numerator nthRoot: aPositiveInteger.
> d _ denominator nthRoot: aPositiveInteger.
> "The #sqrt method in integer will only answer a Float if there's no
> exact square root.
> So, we need a float anyway."
> (n isInfinite or: [ d isInfinite ]) ifTrue: [
> ^self asFloat nthRoot: aPositiveInteger ].
> ^n / d! !
>
> !Fraction methodsFor: 'mathematical functions' stamp: 'jmv 10/13/2011
> 20:16'!
> sqrt
> | d n |
> n _numerator sqrt.
> d _ denominator sqrt.
> "The #sqrt method in integer will only answer a Float if there's no
> exact square root.
> So, we need a float anyway."
> (n isInfinite or: [ d isInfinite ]) ifTrue: [
> ^self asFloat sqrt ].
> ^n / d! !
>
>
> !Integer methodsFor: 'mathematical functions' stamp: 'jmv 10/13/2011 20:19'!
> nthRoot: aPositiveInteger
> "Answer the nth root of the receiver."
>
> | selfAsFloat floatResult guess raised higher lower delta |
> selfAsFloat _ self asFloat.
> floatResult _ selfAsFloat nthRoot: aPositiveInteger.
>
> "If we can't do Float arithmetic, currently we can't look for an
> exact answer"
> floatResult isInfinite ifTrue: [
> ^floatResult ].
>
> guess _ floatResult rounded.
>
> "If got an exact answer, answer it."
> raised _ guess raisedToInteger: aPositiveInteger.
> raised = self
> ifTrue: [ ^ guess ].
>
> "In this case, maybe it failed because we are such a big integer that
> the Float
> method gets inexact, even if we are a whole square number.
> Note (jmv): The algorithms I found for computing the nthRoot would
> havily use
> very large fractions. I wrote this one, that doesn't create
> fractions."
> selfAsFloat abs >= (Float maxExactInteger asFloat raisedToInteger:
> aPositiveInteger)
> ifTrue: [
> raised > self
> ifTrue: [
> higher _ guess.
> delta _ floatResult predecessor -
> floatResult.
> [
> floatResult _ floatResult +
> delta.
> lower _ floatResult rounded.
> (lower raisedToInteger:
> aPositiveInteger) > self ] whileTrue: [
> delta _ delta * 2.
> higher _ lower ] ]
> ifFalse: [
> lower _ guess.
> delta _ floatResult successor -
> floatResult.
> [
> floatResult _ floatResult +
> delta.
> higher _ floatResult rounded.
> (higher raisedToInteger:
> aPositiveInteger) < self ] whileTrue: [
> delta _ delta * 2.
> lower _ higher ]].
> [ higher - lower > 1 ] whileTrue: [
> guess _ lower + higher // 2.
> raised _ guess raisedToInteger:
> aPositiveInteger.
> raised = self
> ifTrue: [
> ^ guess ].
> raised > self
> ifTrue: [ higher _ guess ]
> ifFalse: [ lower _ guess ]]].
>
> "We need an approximate result"
> ^floatResult! !
>
> !Integer methodsFor: 'mathematical functions' stamp: 'jmv 10/13/2011 20:17'!
> sqrt
> "Answer the square root of the receiver."
>
> | selfAsFloat floatResult guess |
> selfAsFloat _ self asFloat.
> floatResult _ selfAsFloat sqrt.
>
> floatResult isInfinite ifFalse: [
> guess _ floatResult truncated.
>
> "If got an exact answer, answer it. Otherwise answer float
> approximate answer."
> guess squared = self
> ifTrue: [ ^ guess ]].
>
> "In this case, maybe it failed because we are such a big integer that
> the Float method becomes
> inexact, even if we are a whole square number. So, try the slower but
> more general method"
> selfAsFloat >= Float maxExactInteger asFloat squared
> ifTrue: [
> guess _ self sqrtFloor.
> guess * guess = self ifTrue: [
> ^guess ]].
>
> "We need an approximate result"
> ^floatResult! !
>
>
> !LargePositiveInteger methodsFor: 'mathematical functions' stamp: 'jmv
> 10/14/2011 07:56'!
> mightBeASquare
> "In base 16, a square number can end only with 0,1,4 or 9 and
> - in case 0, only 0,1,4,9 can precede it,
> - in case 4, only even numbers can precede it.
> See http://en.wikipedia.org/wiki/Square_number
> So, in hex, the last byte must be one of:
> 00
> 10
> 40
> 90
> x1
> e4
> x9
> where x is any hex digit and e is any even digit
> "
> | lsb |
> lsb := self digitAt: 1.
> ^((lsb bitAnd: 7) = 1 "any|1 or
> any|9"
> or: [(lsb bitAnd: 31) = 4 "even|4"
> or: [(lsb bitAnd: 127) = 16 "10 or 90"
> or: [(lsb bitAnd: 191) = 0]]]) "00 or 40"! !
>
> !LargePositiveInteger methodsFor: 'mathematical functions' stamp: 'jmv
> 10/13/2011 22:11'!
> sqrt
> "If we know for sure no exact solution exists, then just answer the
> cheap float approximation without wasting time."
> self mightBeASquare ifFalse: [
> ^self asFloat sqrt ].
>
> "If some exact solution might exist, call potentially expensive
> super"
> ^super sqrt! !
>
>
> !LargeNegativeInteger methodsFor: 'mathematical functions' stamp: 'jmv
> 10/13/2011 21:40'!
> sqrt
> "Answer the square root of the receiver."
> ^ DomainError signal: 'sqrt undefined for number less than zero.'! !
>
>
> !SmallInteger methodsFor: 'mathematical functions' stamp: 'jmv 10/13/2011
> 21:41'!
> sqrt
> self negative ifTrue: [
> ^ DomainError signal: 'sqrt undefined for number less than
> zero.' ].
> ^super sqrt! !
>
>
> !SmallInteger reorganize!
> ('arithmetic' * + - / // \\ gcd: quo:)
> ('bit manipulation' bitAnd: bitOr: bitShift: bitXor: byteReversed
> hashMultiply highBit highBitOfMagnitude lowBit)
> ('testing' even isLarge odd)
> ('comparing' < <= = > >= hash identityHash ~=)
> ('copying' clone shallowCopy)
> ('converting' as31BitSmallInt asFloat)
> ('printing' decimalDigitLength destinationBuffer: numberOfDigitsInBase:
> printOn:base: printOn:base:length:padded: printOn:base:nDigits: printString
> printStringBase: printStringBase:nDigits: threeDigitName)
> ('system primitives' digitAt: digitAt:put: digitLength instVarAt:
> nextInstance nextObject)
> ('private' fromString:radix: highBitOfPositiveReceiver)
> ('mathematical functions' sqrt)
> !
>
>
> !LargeNegativeInteger reorganize!
> ('arithmetic' abs negated)
> ('bit manipulation' bitAt: highBit)
> ('converting' asFloat normalize)
> ('testing' negative positive sign strictlyPositive)
> ('printing' printOn:base:)
> ('mathematical functions' sqrt)
> !
>
>
> !LargePositiveInteger reorganize!
> ('arithmetic' * + - / // \\ \\\ abs negated quo:)
> ('bit manipulation' bitAt: bitReverse: hashMultiply highBit
> highBitOfMagnitude)
> ('testing' isLarge isPrime negative positive sign strictlyPositive)
> ('comparing' < <= > >= hash)
> ('converting' as31BitSmallInt asFloat normalize withAtLeastNDigits:)
> ('system primitives' digitAt: digitAt:put: digitLength
> replaceFrom:to:with:startingAt:)
> ('printing' printOn:base: printOn:base:nDigits: printStringBase:)
> ('mathematical functions' mightBeASquare sqrt)
> !
>
> IntegerTest removeSelector: #testExactRaisedToErrorConditions!
>
>
>
>
More information about the Squeak-dev
mailing list
|