Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-nice.841.mcz ==================== Summary ==================== Name: Kernel-nice.841 Author: nice Time: 13 March 2014, 2:58:18.732 am UUID: e651c760-2924-469e-874b-deafb85737a0 Ancestors: Kernel-nice.840 Provide a somehow slower, but correct version of Integer>>#nthRoot: w.r.t. exactness =============== Diff against Kernel-nice.840 =============== Item was changed: ----- Method: Integer>>nthRoot: (in category 'mathematical functions') ----- nthRoot: aPositiveInteger "Answer the nth root of the receiver. + Answer an Integer if root is exactly this Integer, else answer the Float nearest the exact root." - See #nthRootAlt: for an alternative implementation." + | guess p | - | selfAsFloat floatResult guess delta higher lower raised | - selfAsFloat := self asFloat. + guess := self nthRootRounded: aPositiveInteger. + (guess raisedTo: aPositiveInteger) = self - "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 ]. + p := Float precision - guess highBitOfMagnitude. + p < 0 ifTrue: [ ^ guess asFloat ]. - "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 ]]]. + guess := self << (p * aPositiveInteger) nthRootRounded: aPositiveInteger. + ^(guess / (1 << p)) asFloat! - "We need an approximate result" - ^floatResult! Item was added: + ----- Method: Integer>>nthRootRounded: (in category 'mathematical functions') ----- + nthRootRounded: aPositiveInteger + "Answer the integer nearest the nth root of the receiver." + | guess | + self = 0 ifTrue: [^0]. + self negative + ifTrue: + [aPositiveInteger even ifTrue: [ ArithmeticError signal: 'Negative numbers don''t have even roots.' ]. + ^(self negated nthRootRounded: aPositiveInteger) negated]. + guess := self nthRootTruncated: aPositiveInteger. + ^self * 2 > ((guess + 1 raisedTo: aPositiveInteger) + (guess raisedTo: aPositiveInteger)) + ifTrue: [guess + 1] + ifFalse: [guess]! |
Free forum by Nabble | Edit this page |