Here is another version of the same idea as Kamil Kiełczewski code but adopted to use big.js API and relies on its implementation details.
function isZero(v) {
let digits = v.c;
return digits.length === 1 && digits[0] === 0;
}
function isInteger(v) {
if (isZero(v))
return true;
return v.c.length <= v.e + 1;
}
function neg(v) {
return new Big(0).minus(v);
}
function cubeRoot(v) {
const ZERO = Big(0);
const TEN = new Big(10);
let c0 = v.cmp(ZERO);
if (c0 === 0)
return ZERO;
if (c0 < 0) {
let abs3 = cubeRoot(v.abs());
if (abs3 instanceof Big)
return neg(abs3);
else
return abs3;
}
if (!isInteger(v))
return false;
// use 10 because it should be fast given the way the value is stored inside Big
let left = TEN.pow(Math.floor(v.e / 3));
if (left.pow(3).eq(v))
return left;
let right = left.times(TEN);
while (true) {
let middle = left.plus(right).div(2);
if (!isInteger(middle)) {
middle = middle.round(0, 0); // round down
}
if (middle.eq(left))
return false;
let m3 = middle.pow(3);
let cmp = m3.cmp(v);
if (cmp === 0)
return middle;
if (cmp < 0)
left = middle;
else
right = middle;
}
}
The main idea behind this code is to use binary search but the search starts with a bit better estimate of left and right than in Kamil's code. Particularly, it relies on the fact that Big stores the value in a normalized exponential notation: as an array of decimal digits and exponent. So we can easily find such n that 10^n <= cubeRoot(value) < 10^(n+1). This trick should reduce a few iterations of the loop. Potentially using Newton-Raphson iteration instead of a simple binary search might be a bit faster but I don't think in practice you can see the difference.
Here is another version of the same idea as Kamil Kiełczewski code but adopted to use big.js API and relies on its implementation details.
function isZero(v) {
let digits = v.c;
return digits.length === 1 && digits[0] === 0;
}
function isInteger(v) {
if (isZero(v))
return true;
return v.c.length <= v.e + 1;
}
function neg(v) {
return new Big(0).minus(v);
}
function cubeRoot(v) {
const ZERO = Big(0);
const TEN = new Big(10);
let c0 = v.cmp(ZERO);
if (c0 === 0)
return ZERO;
if (c0 < 0) {
let abs3 = cubeRoot(v.abs());
if (abs3 instanceof Big)
return neg(abs3);
else
return abs3;
}
if (!isInteger(v))
return false;
// use 10 because it should be fast given the way the value is stored inside Big
let left = TEN.pow(Math.floor(v.e / 3));
if (left.pow(3).eq(v))
return left;
let right = left.times(TEN);
while (true) {
let middle = left.plus(right).div(2);
if (!isInteger(middle)) {
middle = middle.round(0, 0); // round down
}
if (middle.eq(left))
return false;
let m3 = middle.pow(3);
let cmp = m3.cmp(v);
if (cmp === 0)
return middle;
if (cmp < 0)
left = middle;
else
right = middle;
}
}
The main idea behind this code is to use binary search but the search starts with a bit better estimate of left and right than in Kamil's code. Particularly, it relies on the fact that Big stores the value in a normalized exponential notation: as an array of decimal digits and exponent. So we can easily find such n that 10^n <= cubeRoot(value) < 10^(n+1). This trick should reduce a few iterations of the loop. Potentially using Newton-Raphson iteration instead of a simple binary search might be a bit faster but I don't think in practice you can see the difference.
So lets look at some cubes in binary
2^3 = 8 = 100b (3 binary digits)
4^3 = 64 = 100 000b (6 binary digits)
8^3 = 512 = 100 000 000b (9 binary digits)
(2^n)^3 = 2^(3n) = (3n binary digits).
So for a rough first guess count the number of binary digits, d say, and divide by three, let n = d/3 this tells us if the cube root number is between 2^n and 2^(n+1). Counting digits can be linked to a primitive first approximation to the logarithm.
If you cannot access the binary digits just repeatedly divide by 8 (or a power of 8) until you get a zero result.
Now we can use Newton-Raphson to home into the solution. Wikipedia cube root helpfully gives us the iteration formula. If a is the number we want to find the root of and x_0 is our first guess using the above
x_{n+1} = ( a / x_n^2 + 2 x_n ) / 3.
This can converge really quickly. For example with a=12345678901234567890 we find that a is between 8^21 and 8^22, hence the cube root must be between 2^21 and 2^22.
Running the iteration
x_1 = 2333795, x_1^3 = 12711245751310434875
x_2 = 2311422, x_2^3 = 12349168818517523448
x_3 = 2311204, x_3^3 = 12345675040784217664
x_4 = 2311204, x_4^3 = 12345675040784217664
and we see it has converged after three iterations. Checking shows that a is between 2311204^3 and 2311205^3.
This algorithm can run with calculations using big.js. The above calculations have been done using Java's BigInt class.
Can you use something like this?
Math.pow(n, 1/root);
eg.
Math.pow(25, 1/2) == 5
The nth root of x is the same as x to the power of 1/n. You can simply use Math.pow:
var original = 1000;
var fourthRoot = Math.pow(original, 1/4);
original == Math.pow(fourthRoot, 4); // (ignoring floating-point error)
