How to get a factorial of 5000 in Go

Question

I would like to calculate a factorial of 5000 in Go but got 0 as a result because the result is bigger than a uint64. However, I was able to do it in Node.js by using

const BigNumber = require('big-number').

Is there an equivalent in Go?

What I did was:

func RecursiveFactorial(number int) big.Int {
    if number >= 1 {
        return big.Int{(number) * RecursiveFactorial(number-1)
    } else {
        return 1
    }
}

Just so you know, using recursion for calculating factorials is a waste of stack. A simple `for` loop is enough. If you want to practice recursion, there are better examples. — Sergio Tulentsev, Mar 01 '19 at 21:47
@antonof BTW, no need to use the `big-number` package in Node.js, it has built-in `BigInt` support now: `const RecursiveFactorial = n => n >= 1n? n * RecursiveFactorial(n - 1n) : 1n;` — P Varga, Mar 01 '19 at 22:12

peterSO · Answer 1 · 2019-03-01T21:49:57.807

In Go, use the math/big package.

For example,

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

Playground: https://play.golang.org/p/53TmmygltkR

score 2 · Answer 2 · answered Feb 20 '20 at 23:59

func factorial(n int64) *big.Int {
    fac := new(big.Int)
    fac.MulRange(1, n)
    return fac
}

z.MulRange(a, b) from math/big computes the product from all int64 a to int64 b. It uses a split and recursiv algorithm (divide and conqueer). It's far more faster than school factorial algorithms. Compute 1 000 000! quickly = ~ 8.26393168833e+5565708

Alexey Mukas · Answer 3 · 2019-03-02T06:29:44.123

You need to use math/big package. You can implement computation recursively or iteratively. Iterative in most cases will be faster and produce less garbage. On my machine iterative impl works 3.1x faster and allocates 2.9x less garbage.

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
}

How to get a factorial of 5000 in Go

3 Answers3