[squeak-dev] The Trunk: Kernel-nice.641.mcz
Juan Vuletich
juan at jvuletich.org
Thu Oct 20 01:10:21 UTC 2011
This is so much fun!
The attach includes yet another version of #nthRoot: and a test that
shows the kind of case it fixes: Receivers too big for Float arithmetic
but without exact answer, and a better float than infinity is possible.
Besides, a small performance tweak: don't call 'selfAsFloat nthRoot:
aPositiveInteger' if the result will be infinity, i.e. if the receiver
is infinity.
Cheers,
Juan Vuletich
commits at source.squeak.org wrote:
> Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
> http://source.squeak.org/trunk/Kernel-nice.641.mcz
>
> ==================== Summary ====================
>
> Name: Kernel-nice.641
> Author: nice
> Time: 19 October 2011, 8:44:12.297 pm
> UUID: e31730ef-2db4-42e3-aa0e-299e45c955ac
> Ancestors: Kernel-nice.640
>
> Correct #nthRootTruncated: (it did call #nthRootFloor:)
> Let #nthRoot: retry in exact arithmetic if ever Float overflows.
>
> =============== Diff against Kernel-nice.640 ===============
>
> ...
-------------- next part --------------
'From Cuis 3.3 of 2 June 2011 [latest update: #1024] on 19 October 2011 at 11:02:07 pm'!
!Integer methodsFor: 'mathematical functions' stamp: 'jmv 10/19/2011 22:39'!
nthRoot: aPositiveInteger
"Answer the nth root of the receiver.
See #nthRootAlt: for an alternative implementation."
| selfAsFloat floatResult guess delta higher lower raised |
selfAsFloat _ self asFloat.
"If we can't do Float arithmetic because we are too big, then look for an exact answer in exact arithmetic"
selfAsFloat isInfinite ifTrue: [
guess _ self nthRootTruncated: aPositiveInteger.
(guess raisedToInteger: aPositiveInteger) = self
ifTrue: [ ^ guess ].
"Nothing else can be done. No exact answer means answer must be a Float.
Answer the best we have."
^guess asFloat ].
floatResult _ selfAsFloat nthRoot: aPositiveInteger.
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 1(jmv): This algorithm is faster than #nthRootTruncated: for big n (aPositiveInteger)
but fails if self asFloat isInfinite.
Note 2(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! !
!IntegerTest methodsFor: 'tests - mathematical functions' stamp: 'jmv 10/19/2011 22:59'!
testBigReceiverInexactNthRoot
"
IntegerTest new testBigReceiverInexactNthRoot
"
"Inexact 3rd root (not a whole cube number), so a Float must be answered.
However, receiver is too big for Float arithmethic."
| bigNum result |
bigNum _ (100 factorial raisedTo: 3) + 1. "Add 1 so it is not a whole cube"
self assert: bigNum asFloat isInfinite. "Otherwise, we chose a bad sample"
result _ bigNum nthRoot: 3.
self assert: result class == Float.
self deny: result isInfinite.
self assert: result = 100 factorial asFloat. "No other float is closer. See following line"
self assert: 100 factorial asFloat = (100 factorial+1) asFloat! !
Integer removeSelector: #nthRootAlt:!
More information about the Squeak-dev
mailing list
|