재귀 - 출력 예기치 않은 결과

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를 들어, 임의의 큰 번호를 제공 일부 라이브러리로 전환해야합니다.

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 
# 

당신은 통지 여기

는 동일 알고리즘의 예, 즉 (Zarith 라이브러리를 사용하여) 임의의 정밀도를 참조하여 페린 숫자를 계산 그 숫자는 실제로 매우 크고, 32 비트 또는 64 비트에도 적합하지 않습니다. 당신이 zarith 라이브러리를 설치하고 추가 종속성을 추가하지 않으려면

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

는, 당신은 OCaml의 임의의 정밀도 숫자 Big_int 모듈을 내장 사용할 수 있습니다 : 사실, 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;;