Arithmetic, algebra, number theory, sequence and series, analysis, ...

Oliver1978
 Posts: 165
 Joined: Sat Nov 22, 2014 9:13 pm
 Location: Erfurt, Germany
Post
by Oliver1978 » Mon Aug 10, 2015 3:49 pm
I've found this nth root algorithm in Richard P. Brent's book "Modern Computer Arithmetic". The power function was inserted by me to get the algorithm to work with bigints if necessary. D's internal ^^ operator for powers only works with purely numerical values.
Anyway, I've tried the algorithm an it returns 6 for nthRoot(243, 3) and 9 for nthRoot(729,3). Both results are of course wrong.
Code: Select all
T nthRoot(T)(T m, T n)
{
T power(T)(in T x, in T y)
{
T res = 1;
T b = x, e = y;
while (e > 0)
{
if (e & 1) res *= b;
b *= b;
e >>= 1;
}
return res;
}
if ((m < 1)  (n < 0)) return cast(T)0;
if ((m == 1)  (n == 0)) return cast(T)1;
if (n == 1) return m;
T u = m;
T s, t;
do
{
s = u;
t = (n  1) * s + (m / power(s, (n  1)));
u = t / n;
}
while (u < s);
return s;
}
Can anybody help me out?
49.157.5694.1125

DJohn
 Posts: 49
 Joined: Sat Oct 11, 2008 11:24 am
Post
by DJohn » Mon Aug 10, 2015 6:32 pm
What's the problem? The floor of the cube root of 243 is 6, and the floor of the cube root of 729 is 9. Both results are correct.

Oliver1978
 Posts: 165
 Joined: Sat Nov 22, 2014 9:13 pm
 Location: Erfurt, Germany
Post
by Oliver1978 » Mon Aug 10, 2015 6:42 pm
This is embarassing
I've rechecked my numbers and found that I'd actually messed up base and exponent. Just because 3^5 ist 243, the cube root of 243 is not 5.
Thanks for pointing this out, DJohn!
49.157.5694.1125