使用递归计算大整数的阶乘

huangapple go评论88阅读模式
英文:

Go big.Int factorial with recursion

问题

我正在尝试实现这段代码:

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

作为一个big.Int,以便使其对较大的x值有效。

下面的代码对于 fmt.Println(factorial(r)) 返回值为0。

7的阶乘应该是5040?

对我做错了什么有什么想法吗?

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
}

这段代码在Go Playground上: http://play.golang.org/p/yNlioSdxi4

英文:

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>

答案1

得分: 16

Go包math.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)
}

将产生

> 3628800

英文:

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 (
    &quot;fmt&quot;
    &quot;math/big&quot;
)

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

Will produce

> 3628800

答案2

得分: 8

在你的int版本中,每个int都是不同的。但是在你的big.Int版本中,你实际上是共享big.Int值的。所以当你说

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

表达式n.Sub(n, c)实际上将0存回到n中,所以当评估n.Mul(n, ...)时,你基本上是在做0 * 1,并且得到0作为结果。

请记住,big.Int操作的结果不仅返回它们的值,还将它们存储到接收器中。这就是为什么你在像n.Mul(n, c)这样的表达式中看到重复的原因,例如为什么它再次将n作为第一个参数。因为你也可以说result.Mul(n, c),你会得到相同的值,但它将存储在result而不是n中。

这是重写代码以避免这个问题的方式:

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
}

这是稍微清理/优化过的版本(我试图删除多余的big.Int分配):http://play.golang.org/p/feacvk4P4O

英文:

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 say result.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(&quot;n = &quot;, 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(&quot;n = &quot;, 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

答案3

得分: 1

例如,

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))
}

输出:

5040
英文:

For example,

package main

import (
	&quot;fmt&quot;
	&quot;math/big&quot;
)

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

答案4

得分: 0

func FactorialBig(n uint64) (r *big.Int) {
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
}

英文:

Non-recursive version:

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

<kbd>playground</kbd>

huangapple
  • 本文由 发表于 2012年6月30日 08:38:39
  • 转载请务必保留本文链接:https://go.coder-hub.com/11270547.html
匿名

发表评论

匿名网友

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen:

确定