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

commits at source.squeak.org commits at source.squeak.org
Sat Oct 29 09:43:50 UTC 2011


Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-nice.645.mcz

==================== Summary ====================

Name: Kernel-nice.645
Author: nice
Time: 29 October 2011, 11:42:54.825 am
UUID: 6c7fe149-d362-481d-803f-eecbec00619c
Ancestors: Kernel-ael.643

Yet another version of #nthRoot: from Cuis
1) Receivers too big for Float arithmetic but without exact answer, and a better float than infinity is possible.
2) Besides, a small performance tweak: don't call 'selfAsFloat nthRoot: aPositiveInteger' if the result will be infinity, i.e. if the receiver is infinity.

=============== Diff against Kernel-ael.643 ===============

Item was changed:
  ----- Method: Integer>>nthRoot: (in category 'mathematical functions') -----
  nthRoot: aPositiveInteger
+ 	"Answer the nth root of the receiver.
+ 	See #nthRootAlt: for an alternative implementation."
- 	"Answer the nth root of the receiver."
  
+ 	| selfAsFloat floatResult guess delta higher lower raised |
- 	| selfAsFloat floatResult guess raised higher lower delta |
  	selfAsFloat := self asFloat.
- 	floatResult := selfAsFloat nthRoot: aPositiveInteger.
  
+ 	"If we can't do Float arithmetic because we are too big, then look for an exact answer in exact arithmetic"
+ 	selfAsFloat isInfinite ifTrue: [
- 	"If we can't do Float arithmetic, then look for an exact answer in exact arithmetic"
- 	floatResult 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 ].
- 		(guess raisedToInteger: aPositiveInteger) = self ifTrue: [^guess].
- 		^floatResult ].
  
+ 	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
- 	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!




More information about the Squeak-dev mailing list