How can I do a combinatory number function in OCaml

Question

So the thing is i want to do a combinatory number function in OCaml and I have the following code:

let rec fact: int -> int = fun num ->
  let rec help: int -> int -> int = fun n acc ->
    if n>0 then help (n-1) (acc * n)
    else acc 
  in 
  help num 1;;

And then the comb funtion:

let comb (m,n) =
  fact m / fact (m-n) / fact n;;

I thought that the problem of the strange results was the recursion but after implementing tail recursion in fact function I'm still getting the same results, for example de comb (66, 2) Exception: division_by_zero or fact 22 = huge negative number, whats the problem here?

Answer 1

You are working with values too large to fit into an OCaml int. Just for one example, fact 66 is 544344939077443064003729240247842752644293064388798874532860126869671081148416000000000000000

This is too large to fit even into a 64-bit integer.

If you want to work with numbers this large in OCaml, you should use the Zarith module.

Another option is to rewrite your function to avoid such large intermediate values. Here's a version of comb that can calculate comb 66 2:

let comb m n =
    let rec icomb num den m n =
        if n <= 0 then num / den
        else icomb (num * m) (den * n) (m - 1) (n - 1)
    in
    icomb 1 1 m n

# comb 66 2;;
- : int = 2145