Рекурсия в 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, но вы скоро достигнете максимума. Если вы хотите вычислить числа Перрина произвольной длины, вам следует переключиться на некоторую библиотеку, которая предоставляет произвольные большие числа, например 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;;