Julia에서 최대 재귀 깊이를 변경하는 방법은 무엇입니까?

Question

나는 (4,2) 매개 변수에 대해 Rosseta 코드 (https://rosettacode.org/wiki/Ackermann_function)에서 얼마나 빠르고 정확한 알고리즘인지 궁금했습니다. 하지만 StackOverflowError가 있습니다.

julia> using Memoize 
@memoize ack3(m, n) = 
m == 0 ? n + 1 : 
n == 0 ? ack3(m-1, 1) : 
ack3(m-1, ack3(m, n-1)) 

# WARNING! Next line has to calculate and print number with 19729 digits! 
julia> ack3(4,2) # -> StackOverflowError 
# has to be -> 2003529930406846464979072351560255750447825475569751419265016973710894059556311 
# ... 
# 4717124577965048175856395072895337539755822087777506072339445587895905719156733 

편집 : 오스카 스미스는 ack3 (4,2)를 시도하는 것은 비현실적이다 권리입니다. 줄리아는 64 개 비트 정수 작동하지 메이크업 물건 너무 정수 오버 플로우를 사용하기 때문에

module Ackermann 
    function ackermann(m::UInt, n::UInt) 
    function ack(m::UInt, n::BigInt) 
     if m == 0 
     return n + 1 
     elseif m == 1 
     return n + 2 
     elseif m == 2  
     return 3 + 2 * n; 
     elseif m == 3 
     return 5 + 8 * (BigInt(2)^n - 1) 
     else 
     if n == 0 
      return ack(m - 1, BigInt(1)) 
     else 
      return ack(m - 1, ack(m, n - 1)) 
     end 
     end 
    end 

    return ack(m, BigInt(n)) 
    end 
end 

julia> import Ackermann;Ackermann.ackermann(UInt(1),UInt(1));@time(a4_2 = Ackermann.ackermann(UInt(4),UInt(2)));t = "$a4_2"; println("len = $(length(t)) first_digits=$(t[1:20]) last digits=$(t[end-20:end])") 
    0.000041 seconds (57 allocations: 33.344 KiB) 
len = 19729 first_digits=20035299304068464649 last digits=445587895905719156733 

Answer 1

줄리아 자체에는 스택 크기에 대한 내부 제한이 없지만 운영 체제는 내부 제한을 가지고 있습니다. 정확한 한계 (및 변경 방법)는 시스템에 따라 다릅니다. 내 맥 (내가 다른 POSIX-Y 시스템을 가정)에, 나는 확인하고 ulimit 내 쉘에 의해 호출되는 프로그램의 스택 크기를 변경할 수 있습니다

$ ulimit -s 
8192 

$ julia -q 
julia> f(x) = x > 0 ? f(x-1) : 0 # a simpler recursive function 
f (generic function with 1 method) 

julia> f(523918) 
0 

julia> f(523919) 
ERROR: StackOverflowError: 
Stacktrace: 
[1] f(::Int64) at ./REPL[1]:1 (repeats 80000 times) 

$ ulimit -s 16384 

$ julia -q 
julia> f(x) = x > 0 ? f(x-1) : 0 
f (generic function with 1 method) 

julia> f(1048206) 
0 

julia> f(1048207) 
ERROR: StackOverflowError: 
Stacktrace: 
[1] f(::Int64) at ./REPL[1]:1 (repeats 80000 times) 

내가 재귀 호출의 정확한 수 그 것이다 생각을 스택에 적합한 지 여부는 시스템과 함수 자체의 복잡성 (즉, 각 재귀 호출이 스택에 저장해야하는 양)에 따라 다릅니다. 이것은 최소한입니다. 그 Ackermann 함수를 계산하기 위해 스택 제한을 얼마나 크게해야할지 모르겠습니다. 내가 스택의 크기를 두 배로하고보다 더 많은 재귀 호출의 수를 두 배로

주 -이 때문에 일정한 오버 헤드입니다 : 답변

julia> log2(523918) 
18.998981503278365 

julia> 2^19 - 523918 
370 

julia> log2(1048206) 
19.99949084151746 

julia> 2^20 - 1048206 
370 

Answer 2

그냥 참고로, 당신은 최대 재귀 수준을 변경하는 경우에도, 당신이 바로 그 답을 얻을 수 없습니다 :이 버전은 Rosseta의 C++에서 번역 . 올바른 대답을 얻으려면, 큰 희망을 가지고 사용해야합니다. 다음 문제는 거의 모든 계산이 반복되지 않으므로 메모를하지 않으려한다는 것입니다. 실제로 저장하지 않으려는 10^19729 가지 이상의 입력을 계산하게됩니다.