Go big.Int factorial with recursion

I am trying to implement this bit of code:

func factorial(x int) (result int) {
  if x == 0 {
    result = 1;
  } else {
    result = x * factorial(x - 1);
  }
  return;
}

as a big.Int so as to make it effective for larger values of x.

The following is returning a value of 0 for fmt.Println(factorial(r))

The factorial of 7 should be 5040?

Any ideas on what I am doing wrong?

package main

import "fmt"
import "math/big"

func main() {
        fmt.Println("Hello, playground")

    //n := big.NewInt(40)
    r := big.NewInt(7)

    fmt.Println(factorial(r))

}

func factorial(n *big.Int) (result *big.Int) {
    //fmt.Println("n = ", n)
    b := big.NewInt(0)
    c := big.NewInt(1)

    if n.Cmp(b) == -1 {
        result = big.NewInt(1)
    }
    if n.Cmp(b) == 0 {
        result = big.NewInt(1)
    } else {
        // return n * factorial(n - 1);
        fmt.Println("n = ", n)
        result = n.Mul(n, factorial(n.Sub(n, c)))
    }
    return result
}

This code on go playground: http://play.golang.org/p/yNlioSdxi4

Edit Report

In your int version, every int is distinct. But in your big.Int version, you're actually sharing big.Int values. So when you say

result = n.Mul(n, factorial(n.Sub(n, c)))

The expression n.Sub(n, c) actually stores 0 back into n, so when n.Mul(n, ...) is evaluated, you're basically doing 0 * 1 and you get back 0 as a result.

Remember, the results of big.Int operations don't just return their value, they also store them into the receiver. This is why you see repetition in expressions like n.Mul(n, c), e.g. why it takes n again as the first parameter. Because you could also sayresult.Mul(n, c) and you'd get the same value back, but it would be stored in result instead of n.

Here is your code rewritten to avoid this problem:

func factorial(n *big.Int) (result *big.Int) {
    //fmt.Println("n = ", n)
    b := big.NewInt(0)
    c := big.NewInt(1)

    if n.Cmp(b) == -1 {
        result = big.NewInt(1)
    }
    if n.Cmp(b) == 0 {
        result = big.NewInt(1)
    } else {
        // return n * factorial(n - 1);
        fmt.Println("n = ", n)
        result = new(big.Int)
        result.Set(n)
        result.Mul(result, factorial(n.Sub(n, c)))
    }
    return
}

And here is a slightly more cleaned-up/optimized version (I tried to remove extraneous allocations of big.Ints): http://play.golang.org/p/feacvk4P4O

answered 2012-06-30T00:59:51.477

Go big.Int factorial with recursion

1 Answer

Your Answer