CODEWITHSUNDEEP
ocaml
alr
alr

Reputation: 1452

Big_int factorial exception

I've tried to implement factorial using Big_int, utop can evaluate it, but it fails in run time. Here is the code:

let factorial (num : int) =
  let n = Big_int.big_int_of_int num in
  let rec fac (n : Big_int.big_int) : Big_int.big_int =
  if n = Big_int.zero_big_int then Big_int.unit_big_int
  else Big_int.mult_big_int n (fac (Big_int.sub_big_int n Big_int.unit_big_int)) in
  fac n

How to fix this case? What is the right (and short) way of implementing factorial using Big_int?
Run this code: factorial 3;;
Error output:

Exception: (Invalid_argument "compare: abstract value").
Raised by primitive operation at file "//toplevel//", line 4, characters 5-29
Called from file "//toplevel//", line 5, characters 30-80
Called from file "//toplevel//", line 5, characters 30-80
Called from file "//toplevel//", line 5, characters 30-80
Called from file "toplevel/toploop.ml", line 180, characters 17-56

Upvotes: 0

Views: 360

Answers (1)

Anton Trunov
Anton Trunov

Reputation: 15414

The problem is in this comparison n = Big_int.zero_big_int. If you change it to using the Big_int's function for comparing big_ints -- eq_big_int, then everything should work.

Here is another example of implementing this function that uses tail-recursion:

open Big_int

let factorial (num : int) : big_int =
  let rec fac_big_int n acc =
    if n = 0 then acc
    else fac_big_int (pred n)
                     (mult_big_int (big_int_of_int n)
                                   acc)
  in
    fac_big_int num unit_big_int

A test in utop:

μ> #load "nums.cma";;
μ> #use "fact_big_int.ml";;
val factorial : int -> big_int = <fun>
μ> string_of_big_int (factorial 10);;
- : string = "3628800"
μ> string_of_big_int (factorial 30);;
- : string = "265252859812191058636308480000000"

Upvotes: 1

Related Questions