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
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
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.Int
s): http://play.golang.org/p/feacvk4P4O
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
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With