牛顿法有更优雅的 Go 实现吗？

Question

我正在学习 Go 教程，想知道是否有比 Exercise: Loops and Functions 上使用牛顿法计算平方根更优雅的方法：

func Sqrt(x float64) float64 {
    count := 0
    var old_z, z float64 = 0, 1
    for ; math.Abs(z-old_z) > .001; count++ {
        old_z, z = z, z - (z*z - x) / 2*z
    }
    fmt.Printf("Ran %v iterations\n", count)
    return z
}

（规范的一部分是提供迭代次数。）这里是full program，包括package statement、imports和main。

Answer 1

首先，你的算法不正确。公式为：

您使用以下方式建模：

z - (z*z - x) / 2*z

但应该是：

z - (z*z - x)/2/z

或

z - (z*z - x)/(2*z)

（你的不正确的公式必须运行像半百万次迭代甚至接近 0.001！正确的公式使用像 4 次迭代一样接近 1e-6 在 x = 2 的情况下。)

接下来，z=1 的初始值不是随机数的最佳值（它可能适用于像 2 这样的小数字）。您可以从 z = x / 2 开始，这是一个非常简单的初始值，让您用更少的步骤更接近结果。

进一步的选项不一定使它更具可读性或更优雅，它是主观的：

您可以将结果命名为 z，因此 return 语句可以是 "bare"。如果您将当前 "exit" 条件移动到循环中，您也可以创建一个循环变量来计算迭代次数，如果满足，您将打印迭代次数并且可以简单地 return。您还可以将计算移动到 if:

的初始化部分

func Sqrt(x float64) (z float64) {
    z = x / 2
    for i, old := 1, 0.0; ; i++ {
        if old, z = z, z-(z*z-x)/2/z; math.Abs(old-z) < 1e-5 {
            fmt.Printf("Ran %v iterations\n", i)
            return
        }
    }
}

您也可以将 z = x / 2 移动到 for 的初始化部分，但是您不能命名结果（否则会创建 z 的本地变体将隐藏命名的 return 值):

func Sqrt(x float64) float64 {
    for i, z, old := 1, x/2, 0.0; ; i++ {
        if old, z = z, z-(z*z-x)/2/z; math.Abs(old-z) < 1e-5 {
            fmt.Printf("Ran %v iterations\n", i)
            return z
        }
    }
}

注意： 我用 1 开始我的迭代计数器，因为在我的例子中 "exit" 条件在 for 内而不是for.

的条件

Answer 2

package main

import (
    "fmt"
    "math"
)

func Sqrt(x float64) float64 {
    z := 1.0
    // First guess
    z -= (z*z - x) / (2*z)
    // Iterate until change is very small
    for zNew, delta := z, z; delta > 0.00000001; z = zNew {
        zNew -= (zNew * zNew - x) / (2 * zNew)
        delta = z - zNew
    }
    return z
}

func main() {
    fmt.Println(Sqrt(2))
    fmt.Println(math.Sqrt(2))
}

牛顿法有更优雅的 Go 实现吗？

Is there a more elegant Go implementation of Newton's method?

go

newtons-method