用二进制搜索计算平方根

Question

我试图在Rust中使用二进制搜索找到一个数字(num)的平方根。我对Rust还不熟悉，但我已经用其他语言编写了相当多的程序。我更感兴趣的是如何改进这一点，因为我不熟悉锈蚀最佳实践和简单的算法，虽然我不介意在这方面的建议*。以下是一般情况下的工作方式：

1. 把我们想找出的数字
2. 将current_guess设置为取平方根的数字的1/2
3. 虽然current_guess平方不是在指定的tolorance中，但是重复以下步骤直到它在所需的tolorance中为止：
4. 计算当前猜测平方与输入数字之间的差异。这就是我们的数字平方与目标数字相距的距离。
5. 如果我们的数字平方在收费范围内，就完成。否则，如果我们的数字是两个低的，乘以1.5使它更大。如果太高，除以二。重复直到解决为止。

当然还有密码。它是用正常的cargo run运行的。

fn main() {
    println!("The square root of 16129 is approximately {}", sqrt(16129.0, 0.01));
}

fn sqrt(num: f64, tolorance: f64) -> f64 {
    // the number we will try next
    let mut current_guess = num / 2.0;

    // how far off our current guess is
    let mut current_difference: f64;
    loop {
        current_difference = current_guess.powi(2) - num;

        if current_difference.abs() <= tolorance {
            // if our answer is within the accepted tolorance range
            return current_guess;
        } else if current_difference < tolorance {
            // if our current guess is too small
            current_guess *= 1.5;
        } else if current_difference > tolorance {
            // if our current guess is too big
            current_guess *= 0.5;
        }
    }
}

我的代码的当前输出是

   Compiling square-root v0.1.0 (C:\[redacted]\square-root)
    Finished dev [unoptimized + debuginfo] target(s) in 1.65s
     Running `target\debug\square-root.exe`
127.00000413730865

这是正确的答案。当然，我可以通过缩小公差来使它更精确。*我并没有反对把这个部分做得更好，我的目标是找到平方根更能让我感觉到锈病。所以我对改进代码的好方法更感兴趣，但我不介意对算法的批评。

Answer 1

这里不是使用二进制搜索，而是使用牛顿法的一种形式。这将有效，并且是浮点数的适当算法，但与二进制搜索不同，它没有利用您正在搜索的数字空间的排序性质。

以下是维基百科对二元搜索的描述：

function binary_search(A, n, T) is
    L := 0
    R := n − 1
    while L ≤ R do
        m := floor((L + R) / 2)
        if A[m] < T then
            L := m + 1
        else if A[m] > T then
            R := m − 1
        else:
            return m
    return unsuccessful

你选择一个“枢轴”，通常在中间。查看所搜索的数字是否大于支点，然后向右重复该过程，如果较小，则在左侧重复该过程。在你的例子中，你会与枢轴的正方形进行比较。

Answer 2

fn sqrt(num: f64, tolorance: f64) -> f64 {

它拼写为tolerance

如果num是负的呢？您可能应该panic抛出错误或诸如此类的。

    // the number we will try next
    let mut current_guess = num / 2.0;

    // how far off our current guess is
    let mut current_difference: f64;
    loop {
        current_difference = current_guess.powi(2) - num;

没有理由在循环之外声明当前的差异。相反，只需在这里说let current_difference。

        if current_difference.abs() <= tolorance {
            // if our answer is within the accepted tolorance range
            return current_guess;
        } else if current_difference < tolorance {

我建议在这里检查这个数字是负数还是正数，而不是与容忍相比较。

            // if our current guess is too small
            current_guess *= 1.5;
        } else if current_difference > tolorance {
            // if our current guess is too big
            current_guess *= 0.5;
        }

乘以1.5或.5对我来说是陌生的。这个算法是否会收敛对我来说并不明显。

    }
}

Answer 3

不熟悉生锈，但有一些改进。在编写代码时，我们通常选择愉快的场景，在企业应用程序的情况下，用户可能会输入在我们的愉快场景中不存在的参数，例如计算负数的平方根。因此，您需要添加对给定参数的验证，并在需要时抛出错误。

当乘以1.5和.5时，还可以将该数字保存为常量，因为我们不希望代码中有硬编码的数字。当然，在大规模应用程序中也是如此。