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.
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.
- 4 The posted question does not appear to include any attempt at all to solve the problem. StackOverflow expects you to try to solve your own problem first, as your attempts help us to better understand what you want. Please edit the question to show what you've tried, so as to illustrate a specific roadblock you're running into a minimal reproducible example. For more information, please see How to Ask and take the tour. – CertainPerformance Commented Dec 21, 2018 at 3:06
- 5 With your reputation you surely must know that this is a vastly too broad question. – Pointy Commented Dec 21, 2018 at 3:06
- 2 you can create an array with a list of perfect cube number and just looping on it? – Jean-philippe Emond Commented Dec 21, 2018 at 3:12
- 2 Mathematics might be a better place for this question. Once you know the mathematical formula, translating it to JavaScript should be trivial. – Barmar Commented Dec 21, 2018 at 3:19
- 2 Related math.se question: math.stackexchange./questions/263087/… – Barmar Commented Dec 21, 2018 at 3:24
6 Answers
Reset to default 3Here 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.
You can use JS build-in BigInt. I assume input is positive integer. For while loops I provide time plexity approximation where n is number of input decimal digits. This version of answer was inspired by Salix alba answer and wiki "cube root":
Binary search O(n log2(10)/3) <= O(1.11*n) (for n=1000 I get 1110 iterations - test here, - for
l=0andr=aO(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 stringNewton-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 - 1I 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 stringHalley 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
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 0For 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 pare 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 e up with given the limitations of your problem.
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
发布者：admin，转转请注明出处：http://www.yc00.com/questions/1745151204a4613877.html
评论列表（0条）