去大。整数的阶乘与递归

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.

作为一个大。使它对较大的x值有效。

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

下面是fmt.Println(factorial(r)的值0

The factorial of 7 should be 5040?

7的阶乘应该是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游乐场:http://play.golang.org/p/yNlioSdxi4。

4 个解决方案

#1

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

在您的int版本中，每个int都是不同的。但在你的大。Int版本，你实际上是在分享。Int值。所以,当你说

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.

表达式n。(n, c)实际上把0存储回n中，所以当n。Mul(n，…)被求值，你基本上是做0 * 1，结果是0。

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.

记住，大的结果。Int操作不只是返回它们的值，它们还将它们存储到接收者中。这就是为什么你会在n这样的表达式中看到重复。Mul(n, c)，例如，为什么把n作为第一个参数。因为你也可以说结果。Mul(n, c)你会得到相同的值，但是它会被存储在结果中而不是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

这里有一个稍微清理过/优化过的版本(我试图删除big.Ints的无关分配):http://play.golang.org/p/feacvk4p4p4p4o

#2

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

去包数学。big有func (*Int) MulRange(a, b int64)。当第一个参数设置为1调用时，它将返回b!

package main

import (
    "fmt"
    "math/big"
)

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

Will produce

将会产生

3628800

3628800

#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:

输出:

#4

Non-recursive version:

非递归版本:

func FactorialBig(n uint64) (r *big.Int) {
    //fmt.Println("n = ", n)
    one, bn := big.NewInt(1), new(big.Int).SetUint64(n)
    r = big.NewInt(1)
    if bn.Cmp(one) <= 0 {
        return
    }
    for i := big.NewInt(2); i.Cmp(bn) <= 0; i.Add(i, one) {
        r.Mul(r, i)
    }
    return
}

playground

操场上

#1