初始猜测的优化是否会使巴比伦法快速求平方根？

Question

Babylonian aka Heron 的方法似乎是寻找数字 n 的平方根的更快算法之一。它收敛的速度取决于您最初猜测的距离。

现在随着数字 n 的增加，它的根 x 随着它的百分比减小。
根(10):10 - 31%
10:100 - 10%
根(100) : 100 - 3%
根(1000) : 1000 - 1%
所以基本上是将数字中的每个数字除以 3 左右。然后将其用作您的初始猜测。比如 -

 public static double root(double n ) {
      //If number is 0 or negative return the number
            if(n<=0)
                return n ;
     //call to a method to find number of digits
            int num = numDigits(n)  ;
            double guess =  n ;
    //Divide by 0.3 for every digit from second digit onwards
            for (int i = 0 ; i < num-1 ; ++i )
                guess = guess * 0.3;
    //Repeat until it converges to within margin of error
            while (!(n-(guess*guess) <= 0.000001 && n-(guess*guess) >= 0 )) {
                double divide = n/guess ;
                guess = Math.abs(0.5*(divide+guess)) ;

            }

            return Math.abs(guess)  ;
        }

这是否有助于优化算法。这是 O(n) 吗？

Answer 1

是的。更好的方法是利用浮点表示法，将二进制指数大约除以二，因为对浮点位的运算非常快。参见 Optimized low-accuracy approximation to `rootn(x, n)`。

Answer 2

我认为算法的复杂性与提供的输入无关。（复杂度是该算法的一般特征，我们不能说算法 x 对于输入 I1 的复杂度为 O1，对于输入 I2 的复杂度为 O2）。因此，无论您提供什么初始值，都不应该提高复杂性。它可能会提高特定情况下的迭代次数，但这是另一回事。将迭代次数减少一半仍然意味着相同的复杂性。请记住 n, 2*n, n/3 都符合 O(n) class .

现在，关于实际的复杂性，我在维基百科 (https://en.wikipedia.org/wiki/Methods_of_computing_square_roots#Babylonian_method) 上读到

This is a quadratically convergent algorithm, which means that the number of correct digits of the approximation roughly doubles with each iteration.

这意味着您需要与期望的精度小数位数一样多的迭代。这是不变的。如果你需要 10 个精确的小数，10 是一个常数，完全独立于 n。

但是在维基百科的例子中，他们从一开始就选择了一个与正确答案数量级相同的候选答案（600 比 354）。但是，如果您的初始猜测太错误（数量级），您将需要一些额外的迭代来将 down/add 削减到必要的数字。这会增加复杂性。假设正确答案是 10000 ，而你的初始猜测是 10。差异是 4 个数量级，我认为在这种情况下，达到正确数量级所需的复杂性与你猜测的位数和正确答案的位数。由于位数近似为 log(n)，在这种情况下，额外的复杂度为 log(corect_answer) -log(initial_guess)，作为绝对值。

为避免这种情况，请选择一个位数正确的号码，通常是初始号码位数的一半。我最好的选择是选择数字的前半部分作为候选（从 123456 中保留 123，从 1234567 中选择 123 或 1234）。在 java 中，您可以使用字节操作将 number/string/whatever 的前半部分保留在内存中。因此，您将不需要迭代，只需一个具有恒定复杂性的字节操作。

Answer 3

对于n ≥ 4, sqrt(n) = 2 sqrt(n / 4).对于 n < 1，sqrt(n) = 1/2 sqrt(n × 4)。因此，您始终可以乘以或除以 4 以在范围 [1, 4].

上标准化 n

完成后，将 sqrt(4) = 2 作为 Heron 算法的起点，因为这是几何平均数，每次迭代都会产生最大可能的改进，然后展开循环以执行所需的次数所需精度的迭代次数。

最后，乘以或除以你一开始去掉的所有2的因数。请注意，对于二进制计算机来说，乘以和除以 2 或 4 既简单又快速。

我在 my blog 讨论这个算法。

初始猜测的优化是否会使巴比伦法快速求平方根？

Does optimization of the initial guess make the Babylonian method of finding square roots fast?

java

algorithm

square-root