如何在 Golang 中使用 big.Int 进行加法/乘法？

Question

我正在尝试编写一个返回斐波那契数列的第 n 个数字的函数。从返回 int 到 big.Int 时，我遇到了麻烦。这是普通版本，它只是使用矩阵求幂来找到斐波那契数列的第 n 个数。它工作得很好并返回我想要的值：func normalFib(n int) int {    if n == 0 || n == 1 {        return n    }    n -= 2    a, b, c := 1, 1, 0    x, y := 1, 1    var evenNum [3]int    var oddNum [2]int    for n > 0 {        if n%2 == 0 {            temp := []int{a*a + b*b, a*b + b*c, b*b + c*c}            a, b, c = temp[0], temp[1], temp[2]            copy(evenNum[:], temp)            n /= 2        } else {            temp := []int{x*a + y*b, x*b + y*c}            x, y = temp[0], temp[1]            copy(oddNum[:], temp)            n--        }    }    return oddNum[0]}func main() {    fmt.Println(normalFib(10)) // Outputs 55}上述函数的中间值如下所示：The value of N is currently: 8 The values of a, b, c: 2 1 1   The value of N is currently: 4 The values of a, b, c: 5 3 2   The value of N is currently: 2 The values of a, b, c: 34 21 13The value of N is currently: 1 The values of x, y: 55 34      // x is correct!这是 big.Int 版本。由于 big.Add() 和 big.Mul() 函数的工作方式，我尝试使用它创建三个结果变量 d、e 和 f，它们将为临时数组中的每个值临时存储这些函数的结果。将 a、b、c 的值设置为切片的值（如果是奇数，则设置为 x、y）将临时切片复制到其各自的数组（evenNum 或oddNum）。

Answer 1

正如类型名称所暗示的那样， a*big.Int是一个指针，并且根据文档big.Int.Add：

将集合 z 添加到总和 x+y 并返回 z。

“回报z”很重要，因为这意味着当你这样做时：

temp := []*big.Int{

    d.Add(e.Mul(a, a), f.Mul(b, b)),

    d.Add(e.Mul(a, b), f.Mul(b, c)),

    d.Add(e.Mul(b, b), f.Mul(c, c))

}

切片的所有三个元素最终都是指向相同的指针big.Int，即指向d. Add您的三个调用中的每一个都可能会更改d，但它们都在更改（并返回指向）相同的单个对象，这不是您想要的。

为了避免这种行为，您需要为每个不同的结果创建一个新的、不同的对象，例如：

temp := []*big.Int{

    big.NewInt(0).Add(big.NewInt(0).Mul(a, a), big.NewInt(0).Mul(b, b)),

    big.NewInt(0).Add(big.NewInt(0).Mul(a, b), big.NewInt(0).Mul(b, c)),

    big.NewInt(0).Add(big.NewInt(0).Mul(b, b), big.NewInt(0).Mul(c, c)),

 }

如果你想最小化分配，你应该能够做到：

x, y := big.NewInt(0), big.NewInt(0)

temp := []*big.Int{

    big.NewInt(0).Add(x.Mul(a, a), y.Mul(b, b)),

    big.NewInt(0).Add(x.Mul(a, b), y.Mul(b, c)),

    big.NewInt(0).Add(x.Mul(b, b), y.Mul(c, c)),

}

因为Adds它们是按顺序完成的并且指向和的指针x没有y保留，所以你重用它们的副本这一事实不会引起问题。但是对于切片的三个元素，您需要不同的对象。