Go big.Int factorial with recursion

Question

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

Answer 1

Go package math.big has func (*Int) MulRange(a, b int64). When called with the first parameter set to 1, it will return b!:

package main

import (
    "fmt"
    "math/big"
)

func main() {
    x := new(big.Int)
    x.MulRange(1, 10)
    fmt.Println(x)
}

Will produce

3628800

Answer 2

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

Answer 3

For example,

package main

import (
    "fmt"
    "math/big"
)

func factorial(x *big.Int) *big.Int {
    n := big.NewInt(1)
    if x.Cmp(big.NewInt(0)) == 0 {
        return n
    }
    return n.Mul(x, factorial(n.Sub(x, n)))
}

func main() {
    r := big.NewInt(7)
    fmt.Println(factorial(r))
}

Output:

5040