REBOL [
	Title:  "Ackermann function benchmark"
	Author: "Ladislav Mecir"
	Type: 	'benchmark
	Purpose: {
		The Ackermann function, or Ackermann-Peter function, is a simple example of 
		a recursive function that is not primitive recursive. It takes two natural 
		numbers as arguments and yields another natural number...One surprising aspect 
		of the Ackermann function is that the only arithmetic operations it ever uses 
		are addition and subtraction of 1. Its properties come solely from the power 
		of unlimited recursion. This also implies that its running time is at least 
		proportional to its output, and so is also extremely huge. In actuality, for 
		most cases the running time is far larger than the output; see below.
			-- Wikipedia
	}
]

ack: func [m n] [
    either zero? :m [:n + 1] [
        either zero? :n [ack (:m - 1) 1] [
            ack (:m - 1) ack :m (:n - 1)
        ]
    ]
]

ack2: function [m n] [b] [
    b: make block! 0
    until [
        either zero? :m [
            n: :n + 1
            either empty? :b [
                :true
            ] [
                m: last :b
                remove back tail :b
                :false
            ]
        ] [
            either zero? :n [
                m: :m - 1
                n: 1
            ] [
                n: :n - 1
                insert tail :b :m - 1
            ]
            :false
        ]
    ]
    :n
]

ack-rc: rebcode [m n /local result] [
	eq.i m 0
    either [
    	set result n
		add.i result 1
	] [
		eq.i n 0
        either [
        	sub.i m 1
			apply result ack-rc [m 1]
		] [
			sub.i n 1
			apply result ack-rc [m n]
			sub.i m 1
            apply result ack-rc [m result]
        ]
    ]
    return result
]

ack-braf: rebcode [m n /local result] [
	eq.i m 0
	braf 8
	set result n
	add.i result 1
	return result
	eq.i n 0
	braf 9
	sub.i m 1
	apply result ack-braf [m 1]
	return result
	sub.i n 1
	apply result ack-braf [m n]
	sub.i m 1
    apply result ack-braf [m result]
    return result
]


ack2-rc: rebcode [m n /local b test lb tb bl] [
    do b [make block! 0]
    until [
    	eq.i m 0
        either [
        	add.i n 1
        	tail? b
            either [
                set test true
            ] [
            	length? lb b
            	pick m b lb
            	set tb b
            	tail tb
            	back tb
                remove tb 1
                set test false
            ]
        ] [
        	eq.i n 0
            either [
            	sub.i m 1
                set n 1
            ] [
            	sub.i n 1
            	;set lb m
            	;sub lb 1
            	;set tb b
            	;tail tb
            	;insert tb lb
            	do lb [insert tail :b :m - 1]
            ]
            set test false
        ]
        sett test
    ]
    return n
]

;then: now/precise a: ack 3 7 print [a difference now/precise then]