/*

  Ackermann function in Picat.

  From Rosetta code:
  http://rosettacode.org/wiki/Ackermann_function
  """
  The Ackermann function is a classic recursive example in computer science. 
  It is a function that grows very quickly (in its value and in the size of 
  its call tree). It is defined as follows:

      A(m, n) = n+1 if m = 0
                A(m-1, 1) if m > 0 and n = 0
                A(m-1, A(m, n-1)) if m > 0 and n > 0

  Its arguments are never negative and it always terminates. Write a function 
  which returns the value of A(m,n). Arbitrary precision is preferred (since 
  the function grows so quickly), but not required. 
  """

  Model created by Hakan Kjellerstrand, hakank@gmail.com
  See also my Picat page: http://www.hakank.org/picat/

*/

main => go.

go =>
    Ack3_4 = a(3,4),
    writeln(ack3_4=Ack3_4),
    nl,    
    foreach(M in 0..3, N in 0..8) 
        printf("a(%d,%d): %d\n", M,N, a(M,N))
    end,
    nl,
    foreach(N in 0..1) 
        printf("a(4,%d): %d\n", N, a(4,N))
    end,
    nl.

/*

CPU time 0.0 seconds.

[3,0,5]

CPU time 0.0 seconds.

[3,1,13]

CPU time 0.0 seconds.

[3,2,29]

CPU time 0.0 seconds.

[3,3,61]

CPU time 0.0 seconds.

[3,4,125]

CPU time 0.0 seconds.

[3,5,253]

CPU time 0.001 seconds.

[3,6,509]

CPU time 0.0 seconds.

[3,7,1021]

CPU time 0.0 seconds.

[3,8,2045]

CPU time 0.0 seconds.

[3,9,4093]

CPU time 0.0 seconds.

[3,10,8189]

CPU time 0.015 seconds.

[3,11,16381]

CPU time 0.015 seconds.

[3,12,32765]

CPU time 0.043 seconds.

[3,13,65533]

CPU time 0.101 seconds.

[3,14,131069]

CPU time 0.147 seconds.

[3,15,262141]

CPU time 0.55 seconds.

[3,16,524285]

CPU time 1.805 seconds.

[3,17,1048573]

CPU time 6.262 seconds.

[3,18,2097149]

CPU time 16.083 seconds.

[3,19,4194301]

CPU time 36.185 seconds.

[3,20,8388605]

*/
go2 =>
    M = 3,
    foreach(N in 0..20)
        time(A = a(M,N)),
        println([M,N,A])
    end,
    nl.

/*

  [m = 0,[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17]]
  [m = 1,[2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18]]
  [m = 2,[3,5,7,9,11,13,15,17,19,21,23,25,27,29,31,33,35]]
  [m = 3,[5,13,29,61,125,253,509,1021,2045,4093,8189,16381,32765,65533,131069,262141,524285]]

  a2(4,1): 65533

  a2(3,10000): 15960504935046067079..454194438340773675005
  digits = 3012

  CPU time 0.02 seconds.

  a2(4,2): 20035299304068464649..445587895905719156733
  digits = 19729

  CPU time 0.815 seconds.



*/
go3 =>
    foreach(M in 0..3)
        println([m=M,[a(M,N) : N in 0..16]])
    end,
    nl,
    printf("a2(4,1): %d\n", a2(4,1)),
    nl,
    time(check_larger(3,10000)),
    nl,
    time(check_larger(4,2)),
    nl.

check_larger(M,N) => 
    printf("a2(%d,%d): ", M,N),
    A = a2(M,N).to_string,
    Len = A.len,
    if Len < 50 then
      println(A)
    else 
      println(A[1..20] ++ ".." ++ A[Len-20..Len])
    end,
    println(digits=Len).

table
a(M, N) = N+1,              M==0           => true.
a(M, N) = a(M-1,1),         (M > 0,  N==0) => true.
a(M, N) = a(M-1,a(M, N-1)), (M > 0, N > 0) => true.

% Faster version (based on Python example)
table
a2(0,N) = N + 1.
a2(1,N) = N + 2.
a2(2,N) = 2*N + 3.
a2(3,N) = 8*(2**N - 1) + 5.
a2(M,N) = cond(N == 0,a2(M-1, 1), a2(M-1, a2(M, N-1))).