有没有更优雅的Go语言实现牛顿法的方法?

huangapple go评论80阅读模式
英文:

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

问题

我正在进行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
}

(规范的一部分是提供迭代次数。)这是完整的程序,包括包声明、导入和主函数。

英文:

I'm doing the Go tutorials and am wondering whether there is a more elegant way to compute a square root using Newton's method on Exercise: Loops and Functions than this:

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
}

(Part of the specification is to provide the number of iterations.) Here is the full program, including package statement, imports, and main.

答案1

得分: 12

首先,你的算法是不正确的。正确的公式应该是:

有没有更优雅的Go语言实现牛顿法的方法?

你的模型中使用的是:

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

但是正确的应该是:

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

或者

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

(你错误的公式需要运行大约五十万次迭代才能接近0.001!而正确的公式在x = 2的情况下只需要四次迭代就能接近1e-6。)

其次,对于一个随机数来说,初始值z=1并不是最好的选择(对于像2这样的小数可能效果不错)。你可以使用z = x / 2作为一个非常简单的初始值,这样可以更快地接近结果。

以下是一些不一定会使代码更易读或更优雅的进一步选项,这是主观的:

你可以将结果命名为z,这样返回语句可以是“裸”的。此外,你可以创建一个循环变量来计算迭代次数,如果将当前的“退出”条件移到循环中,当满足条件时,打印迭代次数并直接返回。你还可以将计算部分移到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("运行了 %v 次迭代\n", i)
			return
		}
	}
}

你还可以将z = x / 2移到for的初始化部分,但这样你就不能有命名的返回值(否则会创建一个局部的z变量,会遮盖命名的返回值):

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("运行了 %v 次迭代\n", i)
			return z
		}
	}
}

**注意:**我将迭代计数器从1开始,因为我的“退出”条件在for循环内部,而不是for的条件部分。

英文:

First, you algorithm is not correct. The formula is:

有没有更优雅的Go语言实现牛顿法的方法?

You modelled this with:

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

But it should be:

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

Or

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

(Your incorrect formula had to run like half a million iterations even to just get as close as 0.001! The correct formula uses like 4 iterations to get as close as 1e-6 in case of x = 2.)

Next, initial value of z=1 is not the best for a random number (it might work well for a small number like 2). You can kick off with z = x / 2 which is a very simple initial value and takes you closer to the result with fewer steps.

Further options which do not necessarily make it more readable or elegant, it's subjective:

You can name the result to z so the return statement can be "bare". Also you can create a loop variable to count the iterations if you move the current "exit" condition into the loop which if met you print the iterations count and can simply return. You can also move the calculation to the initialization part of the 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
		}
	}
}

You can also move the z = x / 2 to the initialization part of the for but then you can't have named result (else a local variant of z would be created which would shadow the named return value):

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
		}
	}
}

Note: I started my iteration counter with 1 because the "exit" condition in my case is inside the for and is not the condition of for.

答案2

得分: 0

包 main

import (
"fmt"
"math"
)

func Sqrt(x float64) float64 {
z := 1.0
// 第一次猜测
z -= (zz - x) / (2z)
// 迭代直到变化非常小
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))
}

英文:
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))
}

huangapple
  • 本文由 发表于 2015年4月16日 13:48:13
  • 转载请务必保留本文链接:https://go.coder-hub.com/29666295.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定