рекурсия в 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

Короче говоря, это происходит из-за целого переполнения. Perrin число 6443 настолько велико, что оно не вписывается в стандартное представление OCaml. Вы можете переключиться на тип int64, но вы достигнете максимума очень скоро. Если вы хотите вычислить числа perrin произвольной длины, вам следует переключиться на некоторую библиотеку, которая предоставляет произвольные большие числа, например Zarith.

Вот пример того же алгоритма, который вычисляет Перрин числа, используя числа произвольной точности (с использованием библиотеки Zarith):

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 

И вот результаты:

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

Вы можете заметить что число действительно очень велико и не имеет шансов вписаться в 32 или даже 64 бит. На самом деле, он должен 2614 биты:

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

Если вы не хотите устанавливать zarith библиотеки и добавить дополнительную зависимость, то вы можете использовать OCaml встроенным Big_int модуля для произвольных точности чисел. Вот реализация на основе модуля 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;;