[squeak-dev] The Trunk: Kernel-nice.841.mcz

commits at source.squeak.org commits at source.squeak.org
Thu Mar 13 01:59:38 UTC 2014


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]!



More information about the Squeak-dev mailing list