30 days of code in Go: Day 21 - Extra Long Factorials

One of the big limitations of simple number data types is the maximum number they can hold. A 64 bit unsigned long can hold up to the number $2^{64}-1$. This is a pretty huge number, but if you try to compute the factorial of a number like $25!$, it is not enough. The good news is that there are software libraries that allow us to surpass this limitation. The bad is that the computations take longer. Depending on how critical something is, we may wish to avoid costly computations like these. Anyway, that’s the challenge I solved today using the package Big. My solution is given below.

package main

import (
  "fmt"
  "math/big"
)

/*tail-recursive factorial function*/
func factorial(
  n *big.Int,
  accumulate *big.Int,
  one *big.Int) *big.Int {
  // cmp returns -1 if n < 1
  // returns 0 if n == 1
  // so here I check n <= 1
  if n.Cmp(one) < 0 || n.Cmp(one) == 0 {
    return accumulate
  }
  accumulate.Mul(accumulate, n)
  n.Sub(n, one)
  return factorial(n, accumulate, one)
}

func main() {

  var n int64
  fmt.Scanf("%d\n", &n)
  N := big.NewInt(n)

  accumulate := big.NewInt(1)
  var one big.Int
  one.SetInt64(1)

  result := factorial(N, accumulate, &one)

  fmt.Printf("%d\n", result)
}

As you may have seen, I have to call methods instead of using the normal mathematical operations available. This was the most annoying part basically. The factorial I wrote is tail-recursive. This means it doesn’t take as much memory as the naive solution that let the function calls stack.

Thanks for reading!