如何在 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）。

尽管我已经尝试过，它仍然只会输出二的倍数，这不是我想要的：

func bigFib(n int) *big.Int {
    if n == 0 || n == 1 {
        return big.NewInt(int64(n))
    }

    n -= 2
    a, b, c := big.NewInt(1), big.NewInt(1), big.NewInt(0)
    x, y := big.NewInt(1), big.NewInt(0)

    var evenNum [3]*big.Int
    var oddNum [2]*big.Int

    for n > 0 {
        if n%2 == 0 {
            // Result variables
            d, e, f := big.NewInt(0), big.NewInt(0), big.NewInt(0)
            // Temporary slice to hold the result of the matrix addition.
            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))}
            // Setting a, b, c to the values of the slice.
            a, b, c = temp[0], temp[1], temp[2]
            // Copying the temp slice to the evenNum array.
            copy(evenNum[:], temp)
            n /= 2
        } else {
            // Result variables
            d, e, f := big.NewInt(0), big.NewInt(0), big.NewInt(0)
            // Temprorary slice to hold the result of the matrix addition.
            temp := []*big.Int{
                d.Add(e.Mul(x, a), f.Mul(y, b)),
                d.Add(e.Mul(x, b), f.Mul(y, c))}
            // Set x, y to the values of the slice.
            x, y = temp[0], temp[1]
            // Copying the temp slice to the oddNum array.
            copy(oddNum[:], temp)
            n--
        }
    }
    return oddNum[0]
}
func main() {
    fmt.Println(bigFib(10)) // Outputs 8
}

bigFib 函数的中间值如下所示：

The value of N is currently: 8
Value of d, e, f: 1 1 0       
Value of a, b, c: 1 1 1       

The value of N is currently: 4
Value of d, e, f: 2 1 1       
Value of a, b, c: 2 2 2       

The value of N is currently: 2
Value of d, e, f: 8 4 4       
Value of a, b, c: 8 8 8       

The value of N is currently: 1
Value of d, e, f:  8 8 0      
Value of x, y: 8 8

如果有人能告诉我出了什么问题，我将不胜感激。

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指针不会被保留，所以您重用它们的副本这一事实不会引起问题。但对于切片的三个元素，您需要不同的对象。xy