Golang实现大数的n次方根计算

Golang实现大数的n次方根计算 我在Go的大数包文档中找不到计算n次方根的方法，所以决定自己使用牛顿法来实现。我在这个链接找到了一个解决方案，并开始用Go实现。但我的代码只在底数为2时工作正常。对于其他底数，结果与正确值相差甚远。

有人能指出我哪里错了吗？

以下是我的代码：

package main

import (
	"fmt"
	"math/big"
	"math/rand"
)

// PowFloat return x^n
func PowFloat(x *big.Float, n int64) *big.Float {
	result := new(big.Float).SetInt64(1)
	for i := 0; i < int(n); i++ {
		result.Mul(result, x)
	}
	return result
}

// GetNthRoothFloat get nth root of a using newton's method
func GetNthRoothFloat(a *big.Float, n int64) *big.Float {
	N := new(big.Float).SetInt64(n)
	xPre := new(big.Float).SetInt64(int64(rand.Intn(10) + 1))
	eps := new(big.Float).SetFloat64(0.00000000001)
	delX := new(big.Float).SetInt64(2147483647)
	xK := new(big.Float).SetInt64(0)

	for delX.Cmp(eps) > 0 {
		t1 := new(big.Float).Sub(N, new(big.Float).SetFloat64(1.0)) // t1 = n-1
		t1 = t1.Mul(t1, xPre)                                       // t1 = (N-1) * xPre
		t2 := new(big.Float).Quo(a, PowFloat(xPre, n-1))            // t2 = a/( xPre^(n-1) )
		t3 := new(big.Float).Add(t1, t2)                            // t3 = t1 + t2
		xK.Quo(t3, N)
		delX = new(big.Float).Sub(xK, xPre)
		delX.Abs(delX)
		xPre = xK.Copy(xK)
	}
	return xK
}

func main() {
	t := new(big.Float).SetInt64(64)
	fmt.Println(GetNthRoothFloat(t, 3))
}

更多关于Golang实现大数的n次方根计算的实战教程也可以访问 https://www.itying.com/category-94-b0.html

2 回复

公式为

x(K + 1) = (1 / N) * ((N - 1) * x(K) + A / x(K) ^ (N - 1))

我认为你实现得没问题。

不过，我对你的初始近似值持怀疑态度。尝试使用更接近正确值的数值。

你可以使用 math.Pow 函数以 float64 类型来计算初始近似值。

每次迭代时打印该值应该能提供一些线索。

更多关于Golang实现大数的n次方根计算的实战系列教程也可以访问 https://www.itying.com/category-94-b0.html


你的牛顿法实现存在两个关键问题：1）初始猜测值范围太小 2）迭代公式有误。以下是修正后的实现：

package main

import (
    "fmt"
    "math/big"
    "math/rand"
)

// PowFloat 计算 x^n
func PowFloat(x *big.Float, n int64) *big.Float {
    result := new(big.Float).SetFloat64(1.0)
    for i := int64(0); i < n; i++ {
        result.Mul(result, x)
    }
    return result
}

// GetNthRootFloat 使用牛顿法计算n次方根
func GetNthRootFloat(a *big.Float, n int64) *big.Float {
    if a.Cmp(new(big.Float).SetFloat64(0.0)) == 0 {
        return new(big.Float).SetFloat64(0.0)
    }

    // 更好的初始猜测：使用a的1/n次方作为近似
    guess := new(big.Float).SetFloat64(1.0)
    if a.Cmp(guess) > 0 {
        // 当a>1时，初始值设为a/2
        guess.Quo(a, new(big.Float).SetFloat64(2.0))
    } else {
        // 当0<a<1时，初始值设为a*2
        guess.Mul(a, new(big.Float).SetFloat64(2.0))
    }

    eps := new(big.Float).SetFloat64(1e-15)
    nFloat := new(big.Float).SetInt64(n)
    nMinus1 := new(big.Float).SetInt64(n - 1)

    for {
        // 牛顿迭代公式: x_{k+1} = (1/n)*((n-1)*x_k + a/(x_k^(n-1)))
        xn1 := PowFloat(guess, n-1)
        
        term1 := new(big.Float).Mul(nMinus1, guess)
        term2 := new(big.Float).Quo(a, xn1)
        
        nextGuess := new(big.Float).Add(term1, term2)
        nextGuess.Quo(nextGuess, nFloat)

        // 检查收敛
        diff := new(big.Float).Sub(nextGuess, guess)
        diff.Abs(diff)
        if diff.Cmp(eps) < 0 {
            return nextGuess
        }
        
        guess = nextGuess
    }
}

func main() {
    // 测试用例
    tests := []struct {
        value float64
        n     int64
    }{
        {64, 3},    // 立方根
        {27, 3},    // 3
        {256, 4},   // 4
        {1024, 10}, // 约2
        {2, 2},     // 平方根
    }

    for _, test := range tests {
        a := new(big.Float).SetFloat64(test.value)
        result := GetNthRootFloat(a, test.n)
        fmt.Printf("%v的%v次方根 = %v\n", test.value, test.n, result)
        
        // 验证结果
        powered := PowFloat(result, test.n)
        fmt.Printf("验证: %v^%v = %v\n\n", result, test.n, powered)
    }
}

主要修正点：

  1. 初始猜测优化：原代码使用随机数1-10作为初始值，对于大数或小数效果不佳。修正后根据a的大小动态调整初始猜测。

  2. 正确的牛顿迭代公式：原代码的迭代公式有误。正确的牛顿法求n次方根公式为：

    x_{k+1} = (1/n) * ((n-1)*x_k + a/(x_k^(n-1)))

  3. 收敛条件改进：使用更精确的收敛判断，避免无限循环。

  4. 边界处理：添加了对a=0的特殊情况处理。

这个实现可以正确计算任意正数的n次方根。对于负数，需要额外处理奇偶次方根的情况。

回到顶部