如何在 Go 中获得 5000 的阶乘

Question

我想在 Go 中计算 5000 的阶乘，但结果为 0，因为结果大于 uint64。但是，我能够在 Node.js 中使用const BigNumber = require('big-number').Go 中有等效项吗？我所做的是：func RecursiveFactorial(number int) big.Int {    if number >= 1 {        return big.Int{(number) * RecursiveFactorial(number-1)    } else {        return 1    }}

Answer 1

在 Go 中，使用math/big包。

例如，

// OEIS: A000142: Factorial numbers: n! = 1*2*3*4*...*n.

// https://oeis.org/A000045

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() {

    fmt.Println(factorial(big.NewInt(5000)))

}

游乐场： https: //play.golang.org/p/53TmmygltkR

Answer 2

func factorial(n int64) *big.Int {

    fac := new(big.Int)

    fac.MulRange(1, n)

    return fac

}

来自 math/big 的 z.MulRange(a, b) 计算从所有 int64 a 到 int64 b 的乘积。它使用拆分和递归算法（分而治之）。它比学校阶乘算法快得多。计算 1 000 000！很快 = ~ 8.26393168833e+5565708

Answer 3

你需要使用math/big包。您可以实现计算recursively或iteratively. 在大多数情况下迭代会更快并且产生更少的垃圾。在我的机器上，迭代 impl 的运行速度提高了 3.1 倍，分配的垃圾减少了 2.9 倍。

BenchmarkIterAndRecursive/recursive-6               3000       3891062 ns/op    17181056 B/op      15003 allocs/op

BenchmarkIterAndRecursive/iterative-6              10000       1237597 ns/op      656089 B/op       5172 allocs/op

package main

import (

    "fmt"

    "log"

    "math/big"

    "testing"

)

func main() {

    fmt.Println(factorial(big.NewInt(5000)))

    fmt.Println(factorialIter(5000))

}

func TestIterWorkTheSame(t *testing.T) {

    recursive := factorial(big.NewInt(5000))

    iterative := factorialIter(5000)

    if recursive.Cmp(iterative) != 0 {

        log.Fatalf("Invalid computation, \n[%v]\n[%v]", recursive, iterative)

    }

}

func BenchmarkIterAndRecursive(b *testing.B) {

    b.Run("recursive", func(b2 *testing.B) {

        for i := 0; i < b2.N; i++ {

            factorial(big.NewInt(5000))

        }

    })

    b.Run("iterative", func(b2 *testing.B) {

        for i := 0; i < b2.N; i++ {

            factorialIter(5000)

        }

    })

}

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 factorialIter(x int) *big.Int {

    result := big.NewInt(1)

    for i := 2; i <= x; i++ {

        result.Mul(result, big.NewInt(int64(i)))

    }

    return result

}