Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Go big.Int factorial with recursion

Tags:

go

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

like image 292
Greg Avatar asked Jun 30 '12 00:06

Greg


3 Answers

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

like image 136
user1567085 Avatar answered Nov 15 '22 12:11

user1567085


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

like image 43
Lily Ballard Avatar answered Nov 15 '22 13:11

Lily Ballard


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
like image 33
peterSO Avatar answered Nov 15 '22 13:11

peterSO