Skip to content

Instantly share code, notes, and snippets.

@costajob
Last active September 20, 2022 21:15
Show Gist options
  • Save costajob/e3e08ddd130ee16324fb6988355bf3e1 to your computer and use it in GitHub Desktop.
Save costajob/e3e08ddd130ee16324fb6988355bf3e1 to your computer and use it in GitHub Desktop.
Factorial implementation using Big numbers in Ruby, GO and Crystal
require "big_int"
def fact(n)
return 1 if n == 0
n * fact(n - 1)
end
n = BigInt.new(ARGV[0])
puts fact(n)
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
}
def fact(n)
return 1 if n == 0
n * fact(n - 1)
end
puts fact(ARGV[0].to_i)
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)
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)
}
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)
@costajob
Copy link
Author

costajob commented Jul 20, 2016

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

@sanatgersappa
Copy link

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)

}

@costajob
Copy link
Author

costajob commented Jul 20, 2016

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

@costajob
Copy link
Author

costajob commented Jul 20, 2016

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

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment