[squeakdev] The Trunk: Kernelnice.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:
http://source.squeak.org/trunk/Kernelnice.1225.mcz
==================== Summary ====================
Name: Kernelnice.1225
Author: nice
Time: 4 May 2019, 11:50:07.297369 pm
UUID: 029064325829436e92de4f1fd552397c
Ancestors: Kernelnice.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 Kernelnice.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
ifTrue:
[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 Squeakdev
mailing list
