Factorial implementation using Big numbers in Ruby, GO and Crystal

fact.cr

require "big_int"

def fact(n)
  return 1 if n == 0
  n * fact(n - 1)
end

n = BigInt.new(ARGV[0])
puts fact(n)

fact.go

package main

import (
	"fmt"
	"math/big"
	"os"
	"strconv"
)

var z, o = big.NewInt(0), big.NewInt(1)

func main() {
	n, _ := strconv.Atoi(os.Args[1])
	b := big.NewInt(int64(n))
	fmt.Println(fact(b))
}

func fact(n *big.Int) (f *big.Int) {
	if n.Cmp(z) == 0 {
		f = o
	} else {
		var t1, t2 big.Int
		f = t1.Mul(n, fact(t2.Sub(n, o)))
	}
	return
}

fact.rb

def fact(n)
  return 1 if n == 0
  n * fact(n - 1)
end

puts fact(ARGV[0].to_i)

mul_range.cr

require "big_int"

def mul_range(a, b)
  return 0 if a == 0
  return 1 if a > b
  return a if a == b
  return a * b if a + 1 == b
  m = (a + b) / 2
  mul_range(a, m) * mul_range(m + 1, b)
end

puts mul_range(1, ARGV[0].to_big_i)

mul_range.go

package main

import (
	"fmt"
	"math/big"
	"os"
	"strconv"
)

func main() {
	n, _ := strconv.Atoi(os.Args[1])

	fac := big.NewInt(1)
	fac.MulRange(int64(1), int64(n))

	fmt.Println(fac)
}

mul_range.rb

def mul_range(a, b)
  return 0 if a == 0
  return 1 if a > b
  return a if a == b
  return a * b if a + 1 == b
  m = (a + b) / 2
  mul_range(a, m) * mul_range(m + 1, b)
end

puts mul_range(1, ARGV[0].to_i)

Synthetic benchmarks on a MacBook Pro 15 late 2011:

Crystal:

time ./fact 70000
real    0m4.705s
ram     24.56 Mib

GO:

time ./fact 70000
real    0m10.876s
ram     57.52Mib

Ruby:

export RUBY_THREAD_VM_STACK_SIZE=7300000
time ruby fact.rb 70000
real    0m3.866s
ram     179.9Mib

package main

import (
"fmt"
"math/big"
"os"
"strconv"
)

func main() {
n, _ := strconv.Atoi(os.Args[1])

fac := big.NewInt(1)
fac.MulRange(int64(1), int64(n))

fmt.Println(fac)

}

Thanks for sharing, i do not know existence of such a func (still tweaking with GO standard lib).

The point here is each language specific decisions:

• GO has a more conservative approach for dealing with BigInt.
• Ruby simply hide the fact you are switching from Number to BigNumber.
• Crystal uses a more rubesque approach, but need to explicitly declare you are using a BigInt: in code implementation anyway this is hidden by overloaded methods that works both with Int and BigInt, thus lifting the burden from developer hands.

If you speak about efficiency: MulRange uses a more efficient algorithm (i will check more).

If you speak about conciseness here what you can do both in Ruby and Crystal:

puts (1..ARGV[0].to_i).reduce(&:*)

require "big_int"
puts (1.to_big_i..ARGV[0].to_i).product

Just for curiosity: reimplemented MulRange in Crystal and Ruby (updated gist).

Here's the benchmarks (augmented N to 300_000):

Crystal:

time ./mul_range 300000
real    0m1.271s
ram     9.91 Mib

GO:

time ./mul_range 300000
real    0m7.778s
ram     18.41Mib

Ruby:

time ruby mul_range.rb 300000
real    0m24.519s
ram     19.63Mib