How to add/multiply using big.Int in Golang?

user_14545572 0
Viewed 2845

I am trying to write a function that returns the nth number of the Fibonacci Sequence. I am running into trouble when going from returning an int to a big.Int.

Here is the normal version, which just uses matrix exponentiation to find the nth number of the Fibonacci sequence. It works just fine and returns the value I want:

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 intermediate values of the above function look like this:

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!

This is the big.Int version. Because of the way the big.Add() and big.Mul() functions work, I've tried working with it by

  1. creating three result variables d, e, and f that will temporarily store the result of those functions for each value in the temporary array.
  2. setting the values of a, b, c to the values of the slice (or x, y if it is an odd number)
  3. copying the temporary slice to its respective array (evenNum or oddNum).

Despite what I've tried, it will still only output multiples of two, which is not what I want:

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
}

The intermediate values for the bigFib function look like this:

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

If anyone can show me what is going wrong, it would be greatly appreciated.

go
1 Answers

As the type name suggests, a *big.Int is a pointer, and per the documentation for big.Int.Add:

Add sets z to the sum x+y and returns z.

The "returns z" is important, because it means that when you do this:

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

all three elements of your slice end up being pointers to the same big.Int, i.e. to d. Each of your three Add calls may change d, but they're all changing (and returning a pointer to) the same, single object, which is not what you want.

To avoid this behavior, you need to create a new, distinct object for each distinct result, something like:

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

If you want to minimize allocations, you should be able to do:

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

since the Adds are done in order and the pointers to x and y are not retained, so the fact you're reusing copies of them doesn't cause a problem. But for the three elements of your slice, you need distinct objects.

user_23998790
Related