recursion in Ocaml - output unexpected result

Question

let n = read_int();;


let ftp = Hashtbl.create 1;;

let rec perrin n = 
   match n with
      0 -> 3
     |1 -> 0
     |2 -> 2
     |_ -> if Hashtbl.mem ftp n 
             then Hashtbl.find ftp n
             else
                begin 
                    Hashtbl.add ftp n (perrin (n-2) + perrin (n-3));
                    Hashtbl.find ftp  n
                 end;;


print_int (perrin n);;
print_newline ();;

The function works for small numbers. but for big numbers begins to return negative numbers in the result. Anyone know how to solve this? example:

perrin 6443;;

output: returns an unexpected result

ivg · Accepted Answer · 2016-10-26 21:33:41Z

3

In short, this is because of integer overflow. The perrin number 6443 is so big that it doesn't fit into the standard OCaml representation. You can switch to int64 type, but you will hit the maximum very soon. If you would like to compute perrin numbers of arbitrary length, then you should switch to some library that provide arbitrary large numbers, for example Zarith.

Here is the example of the same algorithm, that computes perrin numbers using arbitrary precision numbers (using Zarith library):

 let ftp = Hashtbl.create 1

  let (+) = Z.add

  let rec perrin n =
    match n with
    | 0 -> Z.of_int 3
    | 1 -> Z.of_int 0
    | 2 -> Z.of_int 2
    |_ -> if Hashtbl.mem ftp n
      then Hashtbl.find ftp n
      else
        begin
          Hashtbl.add ftp n (perrin (n-2) + perrin (n-3));
          Hashtbl.find ftp  n
        end

And here are the results:

# #install_printer Z.pp_print;;
# perrin 6443;;
- : Z.t =
6937727487481534145345362428447384488478299624972546803624695551910667531554047522814387413304226129434527926499509496229770899828053746244703038130158033495659756925642507460705324476565619563726313143585381473818236243926914534542432440183345586679670347146768666345957457035004600496858722149019370892348066080092386227405747647480490430105430719428536606680584617305233160609609912020683184996768739606851007812320606992975981778299643926692143069608878875765580902743031572791438636355138605019665803104979890697923714757674707178907100143056837109943637042907642787339851137110850937972239227931113199614637067827389939915715964263895232644082473556841869600234790536494644702234455771939854947229042244627157330814752633389708917381476591438570001576028511405244641287078061574227
#

You may notice that the number is indeed very large, and have no chances to fit into 32 or even 64 bits. In fact, it needs 2614 bits:

# Z.numbits (perrin 6443);;
- : int = 2614

If you don't want to install zarith library and to add extra dependencies, then you can use OCaml builtin Big_int module for arbitrary precision numbers. Here is the implementation based on the Big_int module:

  open Big_int

  let ftp = Hashtbl.create 1

  let (+) = add_big_int

  let rec perrin n =
    match n with
    | 0 -> big_int_of_int 3
    | 1 -> big_int_of_int 0
    | 2 -> big_int_of_int 2
    |_ -> if Hashtbl.mem ftp n
      then Hashtbl.find ftp n
      else
        begin
          Hashtbl.add ftp n (perrin (n-2) + perrin (n-3));
          Hashtbl.find ftp  n
        end;;

edited Oct 26, 2016 at 21:33

answered Oct 26, 2016 at 21:06

ivg

35.4k2 gold badges43 silver badges73 bronze badges

Sign up to request clarification or add additional context in comments.

4 Comments

ivg Over a year ago

You don't need to implement it, it is already implemented, see the link in the post. You need to install it (e.g., opam install zarith or sudo apt-get install libzarith-ocaml-dev), then you can load it in the toplevel with #use "topfind";; #require "zarith";;. To compile with it use ocamlbuild and pass -pkg zarith option.

ivg Over a year ago

actually, you can use builtin big_int module, instead of zarith if you don't want to mess with the installation. I've updated with an example that uses big_int. It should work out of box without extra work.

Manuel Jose Over a year ago

why return. error Unbound module Z in line 3 . I need install library Zarith on the mac osx?

ivg Over a year ago

Yep, if you want to use zarith library, you need to install it, and then to load it. Details vary with OS and OS configuration. Use the second example from the posting. It will work without any extra hassle :)

Collectives™ on Stack Overflow

recursion in Ocaml - output unexpected result

1 Answer 1

4 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

4 Comments

Your Answer

Sign up or log in

Post as a guest

Related