Ocamlの再帰 - 予期しない結果を出力する

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();; 

この関数は、小数に対して機能します。大きい数字の場合は結果に負の数が返されます。誰でもこれを解決する方法を知っていますか？ 例：

perrin 6443;; 

出力：要するに、予期しない結果

Answer 1

を返し、これは、整数オーバーフローです。ペリン番号6443は大きすぎるので標準のOCaml表現には適合しません。 int64型に切り替えることができますが、すぐに最大値に達するでしょう。任意の長さのペリン数を計算する場合は、任意の大きな数値を提供するライブラリ（例えば、Zarith）に切り替える必要があります。ここで

は（Zarithライブラリを使用して）の任意精度数値を使用してペラン数字を計算し、同じアルゴリズムの例である：

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

あなたが気づくことがあります。

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 

そして、ここでは結果がありますその数は確かに非常に大きく、32ビットまたは64ビットに適合する機会はありません。あなたは、あなたがOCamlは、任意の精度の数値のためのBig_intモジュールを組み込み使用することができ、zarithライブラリをインストールすると、余分な依存関係を追加したくない場合は

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

：実際には、2614ビットを必要とします。 Big_intモジュールに基づく実装は次のとおりです。

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;;