时间戳

首页 > 解决方案 > 使用有限的数学运算符求立方根

javascript - 使用有限的数学运算符求立方根

问题描述

我需要编写一个函数来告诉我一个数字是否是一个完美的立方体。如果是我希望立方根返回 else false 如下：

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

它必须适用于非常大的数字。性能是一个很大的奖励。

但是，我使用的库意味着我只能使用以下数学函数/运算符：

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

如果仅使用上述运算符在 JS 中提供答案，我可以自己将答案转换为（big.js）语法（我正在使用的库）。这可能吗？

big.jsPS由于它保证的精度，我需要使用。

标签： javascriptmathbig.js

解决方案

所以让我们看一下二进制中的一些立方体

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).

因此，对于粗略的第一个猜测，计算二进制数字的数量，d例如，除以三，让n = d/3这告诉我们立方根数是否介于2^n和之间2^(n+1)。计数数字可以与对数的原始第一近似值相关联。

如果您无法访问二进制数字，只需重复除以 8（或 8 的幂），直到得到零结果。

现在我们可以使用 Newton-Raphson 来确定解决方案。Wikipedia 立方根为我们提供了迭代公式。如果a是我们想要找到根的数字并且x_0是我们使用上面的第一个猜测

x_{n+1} = ( a / x_n^2 + 2 x_n ) / 3.

这可以很快收敛。例如，a=12345678901234567890我们发现它a在 8^21 和 8^22 之间，因此立方根必须在 2^21 和 2^22 之间。

运行迭代

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

我们看到它在 3 次迭代后已经收敛。检查显示a介于 2311204^3 和 2311205^3 之间。

该算法可以使用 big.js 进行计算。上述计算是使用 Java 的 BigInt 类完成的。

推荐阅读