comment changer la profondeur maximale de récursivité dans Julia?

Question

J'étais curieux de savoir comment rapide et précis, l'algorithme du code Rosseta (https://rosettacode.org/wiki/Ackermann_function) pour (4,2) paramètres, pourrait être. Mais j'ai 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 

EDIT: Oscar Smith est juste qu'essayer ACK3 (4,2) est irréaliste. Ceci est la version traduite à partir de Rosseta de C++:

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

Julia elle-même n'a pas de limite interne à la taille de la pile, mais votre système d'exploitation le fait. Les limites exactes ici (et comment les changer) dépendront du système. Sur mon Mac (et je suppose que les systèmes POSIX-y), je peux vérifier et modifier la taille de la pile de programmes qui s'appellent ma coquille avec 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) 

Je crois que le nombre exact d'appels récursifs qui sera L'ajustement sur votre pile dépend à la fois de votre système et de la complexité de la fonction elle-même (c'est-à-dire combien chaque appel récursif doit stocker sur la pile). C'est le strict minimum. Je n'ai aucune idée de la taille de la pile nécessaire pour calculer la fonction Ackermann.

Notez que j'ai doublé la taille de la pile et il a plus que doublé le nombre d'appels récursifs - cela est dû à une surcharge constante:

julia> log2(523918) 
18.998981503278365 

julia> 2^19 - 523918 
370 

julia> log2(1048206) 
19.99949084151746 

julia> 2^20 - 1048206 
370 

Answer 2

Juste FYI, même si vous changez la profondeur de récursivité max, vous ne serez pas la bonne réponse que Julia utilise les entiers 64 bits, débordement donc entier avec faire des choses fonctionnent pas . Pour obtenir la bonne réponse, vous devrez utiliser des gros caractères pour avoir de l'espoir. Le problème suivant est que vous ne voulez probablement pas mémoriser, car presque tous les calculs ne sont pas répétés, et vous allez calculer la fonction plus de 10^19729 entrées différentes, que vous ne voulez vraiment pas stocker.