The Trunk: Kernel-nice.1043.mcz
Locked
 
|
Nicolas Cellier uploaded a new version of Kernel to project The Trunk:
http://source.squeak.org/trunk/Kernel-nice.1043.mcz ==================== Summary ==================== Name: Kernel-nice.1043 Author: nice Time: 1 October 2016, 10:19:12.37443 pm UUID: d29f9c07-edc8-4add-9b99-e889fd2be32a Ancestors: Kernel-nice.1042 Fix (10 raisedTo: 600) nthRoot: 300. It did incorrectly return 126.0 instead of 100. =============== Diff against Kernel-nice.1042 =============== Item was changed: ----- Method: Integer>>nthRootTruncated: (in category 'mathematical functions') ----- nthRootTruncated: aPositiveInteger "Answer the integer part of the nth root of the receiver." + | guess guessToTheNthMinusOne nextGuess | - | guess guessToTheNthMinusOne delta | self = 0 ifTrue: [^0]. self negative ifTrue: [aPositiveInteger even ifTrue: [ ArithmeticError signal: 'Negative numbers don''t have even roots.' ]. ^(self negated nthRootTruncated: aPositiveInteger) negated]. guess := 1 bitShift: self highBitOfMagnitude + aPositiveInteger - 1 // aPositiveInteger. [ guessToTheNthMinusOne := guess raisedTo: aPositiveInteger - 1. + nextGuess := (aPositiveInteger - 1 * guess * guessToTheNthMinusOne + self) // (guessToTheNthMinusOne * aPositiveInteger). + nextGuess = guess ] whileFalse: + [ guess := nextGuess ]. + ( guess raisedTo: aPositiveInteger) > self ifTrue: - delta := (guess * guessToTheNthMinusOne - self) // (guessToTheNthMinusOne * aPositiveInteger). - delta = 0 ] whileFalse: - [ guess := guess - delta ]. - ( (guess := guess - 1) raisedTo: aPositiveInteger) > self ifTrue: [ guess := guess - 1 ]. ^guess! |
Re: The Trunk: Kernel-nice.1043.mcz
|
|
On Sat, Oct 01, 2016 at 08:19:27PM +0000, [hidden email] wrote:
> Nicolas Cellier uploaded a new version of Kernel to project The Trunk: > http://source.squeak.org/trunk/Kernel-nice.1043.mcz > > ==================== Summary ==================== > > Name: Kernel-nice.1043 > Author: nice > Time: 1 October 2016, 10:19:12.37443 pm > UUID: d29f9c07-edc8-4add-9b99-e889fd2be32a > Ancestors: Kernel-nice.1042 > > Fix (10 raisedTo: 600) nthRoot: 300. > It did incorrectly return 126.0 instead of 100. > Can you say anything about the underlying cause of this problem? I saw it in my 64-bit image, but not in my 32-bit image. The Kernel-nice.1042 update resolved the problem in my 64-bit image, but I find that when I revert to Kernel-tfel.1040, the problem does not come back. Strange... Thanks, Dave |
Re: The Trunk: Kernel-nice.1043.mcz
|
|
2016-10-02 16:48 GMT+02:00 David T. Lewis <[hidden email]>: On Sat, Oct 01, 2016 at 08:19:27PM +0000, [hidden email] wrote: Hi Dave, I don't see why there would be any difference between 32 and 64 bits image. The problem lies in the Newton-Raphson algorithm: xn+1 = xn - (f(xn)-y)/(f'(xn)) for f(x) = x^p, the convergence is very slow when p is high because derivative is p*x^(p-1). But we did store the integer part of decrement: delta := (guess * guessToTheNthMinusOne - self) // (guessToTheNthMinusOne * aPositiveInteger). Initial guess is 128, delta=2, then 126 delta<1, so the initial algorithm was stuck. So I truncated xn+1 instead of truncating the delta and iterated until xn+1=xn. But the correction above was wrong, because we can have guess and nextGuess from each side of nth-root, and never reach an integer fix point, but rather x(n+2)=x(n+1) - 1 and x(n+1) = x(n) + 1. |
Re: The Trunk: Kernel-nice.1043.mcz
|
|
On Sun, Oct 02, 2016 at 06:06:24PM +0200, Nicolas Cellier wrote:
> 2016-10-02 16:48 GMT+02:00 David T. Lewis <[hidden email]>: > > > On Sat, Oct 01, 2016 at 08:19:27PM +0000, [hidden email] wrote: > > > Nicolas Cellier uploaded a new version of Kernel to project The Trunk: > > > http://source.squeak.org/trunk/Kernel-nice.1043.mcz > > > > > > ==================== Summary ==================== > > > > > > Name: Kernel-nice.1043 > > > Author: nice > > > Time: 1 October 2016, 10:19:12.37443 pm > > > UUID: d29f9c07-edc8-4add-9b99-e889fd2be32a > > > Ancestors: Kernel-nice.1042 > > > > > > Fix (10 raisedTo: 600) nthRoot: 300. > > > It did incorrectly return 126.0 instead of 100. > > > > > > > Can you say anything about the underlying cause of this problem? I saw it > > in my 64-bit image, but not in my 32-bit image. The Kernel-nice.1042 update > > resolved the problem in my 64-bit image, but I find that when I revert > > to Kernel-tfel.1040, the problem does not come back. Strange... > > > > Thanks, > > Dave > > > > Hi Dave, > I don't see why there would be any difference between 32 and 64 bits image. > The problem lies in the Newton-Raphson algorithm: > > xn+1 = xn - (f(xn)-y)/(f'(xn)) > > for f(x) = x^p, the convergence is very slow when p is high because > derivative is p*x^(p-1). > But we did store the integer part of decrement: > > delta := (guess * guessToTheNthMinusOne - self) // > (guessToTheNthMinusOne * aPositiveInteger). > > Initial guess is 128, delta=2, then 126 delta<1, so the initial algorithm > was stuck. > > So I truncated xn+1 instead of truncating the delta and iterated until > xn+1=xn. > > But the correction above was wrong, because we can have guess and nextGuess > from each side of nth-root, and never reach an integer fix point, but > rather x(n+2)=x(n+1) - 1 and x(n+1) = x(n) + 1. > Thank you for the explanation, I understand the issue better now. The thing that is strange to me is that when I revert Integer>>nthRootTruncated: back to the old version from 2011, the problem does not come back. Instead I now get the expected result: (10 raisedTo: 600) nthRoot: 300. ==> 100.0 I can no longer find an image on my hard drive that has this problem of answering 126 instead of the the expected 100. But I know that I did see the problem before. Dave |
«
Return to Squeak - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |