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

commits at source.squeak.org commits at source.squeak.org
Sat May 4 21:50:29 UTC 2019

Nicolas Cellier uploaded a new version of Kernel to project The Trunk:

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

Name: Kernel-nice.1225
Author: nice
Time: 4 May 2019, 11:50:07.297369 pm
UUID: 02906432-5829-436e-92de-4f1fd552397c
Ancestors: Kernel-nice.1224

Fix nthRootRounded:

How does it work?
To have short notation, say we have the truncated nth root x of y such that:

x^n <= y
(x+1)^n > y

The true root r is somewhere in between

r^n = y
x <= r < x+1

But is r closer to x or x+1?
Let's just check the mid point (x+0.5)^n

(x+0.5)^n < y ==> (x+0.5 < r) we must answer x+1
(x+0.5)^n > y ==> (r < x+0.5) we must answer x
(x+0.5)^n = y is impossible, the left member of inequality is an irreducible Fraction (odd numerator, even denominator), the right member is an Integer.

We eliminate the Fraction denominator to stick with Integer arithmetic and test:

(x*2+1)^n < (y << n)

It seems like ancient code was testing

(x^n + (x+1)^n)/2 < y

Gasp, did I write this?

=============== Diff against Kernel-nice.1224 ===============

Item was changed:
  ----- 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
  			[aPositiveInteger even ifTrue: [ ArithmeticError signal: 'Negative numbers don''t have even roots.' ].
  			^(self negated nthRootRounded: aPositiveInteger) negated].
  	guess := self nthRootTruncated: aPositiveInteger.
+ 	^(2 * guess + 1 raisedToInteger: aPositiveInteger) < (self bitShift: aPositiveInteger)
- 	^self * 2 > ((guess + 1 raisedTo: aPositiveInteger) + (guess raisedTo: aPositiveInteger))
  		ifTrue: [guess + 1]
  		ifFalse: [guess]!

More information about the Squeak-dev mailing list