[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