如何在 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 13

The value of N is currently: 1 

The values of x, y: 55 34      // x is correct!

这是 big.Int 版本。由于 big.Add() 和 big.Mul() 函数的工作方式，我尝试使用它

1. 创建三个结果变量 d、e 和 f，它们将为临时数组中的每个值临时存储这些函数的结果。

2. 将 a、b、c 的值设置为切片的值（如果是奇数，则设置为 x、y）

3. 将临时切片复制到其各自的数组（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保留，所以你重用它们的副本这一事实不会引起问题。但是对于切片的三个元素，您需要不同的对象。