find cube root using limited math operators

Question

I need to write a function which tells me if a number is a perfect cube. If it is I want the cube root returned else false as follows:

cubeRoot(1)   // 1
cubeRoot(8)   // 2
cubeRoot(9)   // false
cubeRoot(27)  // 3
cubeRoot(28)  // false

It must work for very big numbers. Performance is a great bonus.

However, the lib I am using means I can only use the following math functions/operators:

abs, round, sqrt
/ * + -
===
> >= < <=
%
^

If an answer is provided in JS using only the above operators I can convert the answer to (big.js) syntax myself (the lib I am using). Is this possible?

PS I need to use big.js due to the precision it guarantees.

Answer 1

You can use JS build-in BigInt. I assume input is positive integer. For while loops I provide time complexity approximation where n is number of input decimal digits. This version of answer was inspired by Salix alba answer and wiki "cube root":

1. Binary search O(n log2(10)/3) <= O(1.11*n) (for n=1000 I get 1110 iterations - test here, - for l=0 and r=a O(10/3 n))

   function cubicRoot(a) 
   { 
     let d = Math.floor((a.toString(2).length-1)/3); // binary digits nuber / 3
     let r = 2n ** BigInt(d+1); // right boundary approximation
     let l = 2n ** BigInt(d);   // left boundary approximation
     let x=BigInt(l); 
     let o=BigInt(0);           // old historical value
     
     while(1) {
       o = x;
       y = x * x * x;      
       y<a ? l=x : r=x;      
       if(y==a) return x;
       x = l + (r - l)/2n;      
       if(o==x) return false;
     }
   }
   
   // TEST
   
   let t = "98765432109876543210987654321098765432109876543210987";
   let B = BigInt(t) * BigInt(t) * BigInt(t);
   
   console.log('cRoot(B):   ', cubicRoot( B )     .toString());
   console.log('cRoot(B+1): ', cubicRoot( B +1n ) .toString());
   console.log('cRoot(B-1): ', cubicRoot( B -1n ) .toString());
   console.log('B=',B.toString().split('').map((x,i)=>(i%60?'':'\n')+x).join('')); // split long number to multiline string

2. Newton-Raphson scheme O(log(9n)) (for n<=1000 I get max 13 iterations test). I have problem with "stop" condition - for numbers a=b*b*b - 1 I need check two historical values for x (and if they occurre at least once then stop) - but I don't know that for some case we shoud need to check tree or more historical values to stop algorith.

   function cubicRoot(a) 
   { 
     let d = Math.floor((a.toString(2).length-1)/3); // binary digits nuber / 3
     let x = 2n ** BigInt(d);    
     let o=BigInt(0); // last history value
     let u=BigInt(0); // pre-last history value
     let i=0; // loop counter for worst scenario stop condition
     
     while(i<d*4) {
       i++;
       u = o;
       o = x;     
       y = x*x*x;            
       if(y===a) return x;
       x = ( a / (x*x) + 2n* x ) / 3n;
       if(o==x || u==x) return false; 
     }
     
     return false; // worst scenario - if for some case algorithm not finish after d*4 iterations
   }
   
   // TEST
   
   let t = "98765432109876543210987654321098765432109876543210987";
   let B = BigInt(t) * BigInt(t) * BigInt(t);
   
   console.log('cRoot(B):   ', cubicRoot( B )     .toString());
   console.log('cRoot(B+1): ', cubicRoot( B +1n ) .toString());
   console.log('cRoot(B-1): ', cubicRoot( B -1n ) .toString());
   console.log('B=',B.toString().split('').map((x,i)=>(i%60?'':'\n')+x).join('')); // split long number to multiline string

3. Halley method O(log(3n)) (for tested n<=1000 digits I get max 8 iterations - test)

   function cubicRoot(a) 
   { 
     let d = Math.floor((a.toString(2).length-1)/3); // binary digits nuber / 3
     let x = 2n ** BigInt(d);    
     let o=BigInt(0); // last history value
     let i=0; // loop counter for worst scenario stop condition
     
     while(i<d) {
       i++;
       o = x;     
       y = x*x*x;            
       if(y==a) return x;
       x = 1n + x*(y + 2n*a)/(2n*y + a);
       if(o==x) return false; 
     }
     
     return false; // worst scenario (??)
   }
   
   // TEST
   
   let t = "98765432109876543210987654321098765432109876543210987";
   let B = BigInt(t) * BigInt(t) * BigInt(t);
   
   console.log('cRoot(B):   ', cubicRoot( B )     .toString());
   console.log('cRoot(B+1): ', cubicRoot( B +1n ) .toString());
   console.log('cRoot(B-1): ', cubicRoot( B -1n ) .toString());
   console.log('B=',B.toString().split('').map((x,i)=>(i%60?'':'\n')+x).join('')); // split long number to multiline string

Answer 2

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.

Answer 3

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.

Answer 4

I found this great answer, which showed an algorithm which I have modified very slightly. Here's what you could do:

function simpleCubeRoot(x) {    
    if (x === 0) {
        return 0;
    }
    if (x < 0) {
        return -simpleCubeRoot(-x);
    }

    var r = x;
    var ex = 0;

    while (r < 0.125) { 
        r *= 8; ex--; 
    }
    while (r > 1.0) { 
        r *= 0.125; ex++; 
    }

    r = (-0.46946116 * r + 1.072302) * r + 0.3812513;

    while (ex < 0) { 
        r *= 0.5; ex++; 
    }
    while (ex > 0) { 
        r *= 2; ex--; 
    }

    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);

    if (Number.isInteger(r)) {
        return r;
    }
    return false;
}

Demonstration:

function simpleCubeRoot(x) {
    if (x === 0) {
        return 0;
    }
    if (x < 0) {
        return -simpleCubeRoot(-x);
    }

    var r = x;
    var ex = 0;

    while (r < 0.125) {
        r *= 8;
        ex--;
    }
    while (r > 1.0) {
        r *= 0.125;
        ex++;
    }

    r = (-0.46946116 * r + 1.072302) * r + 0.3812513;

    while (ex < 0) {
        r *= 0.5;
        ex++;
    }
    while (ex > 0) {
        r *= 2;
        ex--;
    }

    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);
    r = (2.0 / 3.0) * r + (1.0 / 3.0) * x / (r * r);

    if (Number.isInteger(r)) {
        return r;
    }
    return false;
}

console.log(simpleCubeRoot(27)); //Should return 3
console.log(simpleCubeRoot(0)); //Should return 0

Answer 5

For what I know, the exponent in Javascript in only accessible throught the Math library with Math.pow.

Using exponent, cubic root of x can be calculated by cubeRoot(x) = x^(1/3). In javascript using Math, this would look like var cubeRoot = Math.pow(x, 1/3).

Since your function has to return false if the result is fractional, I would make use of Math.round to compare the cubic root. Your function would look like this:

function cubeRoot(x) {
    var root = Math.pow(x, 1/3);
    if (Math.round(root) !== root) {
        return false;
    }
    return root;
}

However, since 1/3 is actcually 0.33333... with a certain floating precision, this will not work for large cubes. For instance, Math.pow(45629414826904, 1/3) might return you something like 35733.99999999998.

What I would then do is if the difference with the rounded result is very small (say smaller than 1/1000000), re-cube the number to see if this gets you back your original x:

function cubeRoot(x) {
    var root = Math.pow(x, 1/3);
    var roundedRoot = Math.round(root);
    var diff = Math.abs(root - roundedRoot);

    if (diff <= 1/1000000) {
        var reCubed = Math.pow(roundedRoot, 3);
        if (reCubed === x) {
           return roundedRoot;
        }
        return false;
    }
    if (diff !== roundedRoot) {
        return false;
    }
    return root;
}

I tested a bit on y local Nodejs and it seems like it could handle cubes as large as 8000120000600001 (or 200001^3) before failing to return false on some non-cubes. Haven't tested it extensively, but this is the best hack I can come up with given the limitations of your problem.

Answer 6

To avoid the cube root headache, you can use a relative of big.js called decimal.js-light (either on its own or alongside big.js)

big.js does not support fractional powers, but decimal.js-light does so you can get the cube root as follows:

const Big = require('big.js')
const Decimal = require('decimal.js-light')

const nthRoot = (bigNumber, intRoot) => {
  const strBigNumber = bigNumber.toFixed()
  const decimal = Decimal(strBigNumber)
  const root = decimal.pow(1 / intRoot)
  return Big(root.toFixed())
}

module.exports = nthRoot

And use as follows:

nthRoot(Big(8), 3)          // 1.9999999999999998613
nthRoot(Big(8), 3).round()  // 2