From: dseaman@seaman.cc.purdue.edu (Dave Seaman)
Subject: Re: Ackermann's function
Date: 21 Nov 2001 09:51:34 -0500
Newsgroups: comp.soft-sys.math.maple
Summary: Computer code for Ackermann functions

In article <3bfb5ac3.406754@news.cis.dfn.de>,
Thomas Richard <t.richard@scientific.de> wrote:
>Michael Bader <mail@michaelbader.de> wrote:

>> [...]
>> It's not that I would like to actually compute the numbers. I was just
>> trying to produce some examples of recursion (using "option remember" f.e.) 
>> for a programming course.

>I ran your original procedure in Maple V Release 5.1 (slightly adapted)
>overnight on Linux with 768MB RAM and kernelopts(stacklimit=500000);
>ackermann(4,1) returned 65533.
>As Richard Kreckel suggested, Maple is fine for the analysis of such
>algorithms, not so much  for the actual number crunching.

It's not likely that any language will help much with the number
crunching if you don't at least program in a few short cuts.  That can
help with the moderate levels, but it's only postponing the time when the
recursion stack will exceed the capacity of the machine.

Here is some code that I wrote to compute the Ackermann function and its
cousin, the Ackermann generalized exponential.  The code happens to be in
Common Lisp, but the comments should enable you to translate into any
language you like.

;;;-*- Mode: Lisp; Package: (ACKERMANN) -*-

(defpackage :ackermann
  (:use :cl)
  (:export ackermann generalized-expt))

(in-package :ackermann)

#|
***********************************************************************

Definition of Ackermann's function:

	f(0,y)     = y + 1
	f(x+1,0)   = f(x,1)
	f(x+1,y+1) = f(x,f(x+1,y))

Definition of Ackermann's generalized exponential:

	(informally:)

	g(0,x,y) = y + x
	g(1,x,y) = y * x
	g(2,x,y) = y^x
	g(3,x,y) = y^^x = y^y^...^y (x times)
	(etc.)

	(formally:)

	g(0,0,y)     = y
	g(0,x+1,y)   = g(0,x,y) + 1
	g(1,0,y)     = 0
	g(z+2,0,y)   = 1
	g(z+1,x+1,y) = g(z,g(z+1,x,y),y)

Relation of Ackermann's function to Ackermann's generalized exponential:

	f(1,y) = -3 + 2 + (y+3)		= y + 2
	f(2,y) = -3 + 2 * (y+3)		= 2*y + 3
	f(3,y) = -3 + 2 ^ (y+3)	
	f(4,y) = -3 + 2 ^^ (y+3)
	(etc.)

And in general:

	f(x+1,y) = -3 + g(x,y+3,2)

***********************************************************************
|#

(defun generalized-expt (z x y)
  "Find result of applying z-th iterated operation to x and y."
  (cond
   ((zerop z) (+ y x))
   ((eql z 1) (* y x))
   ((eql z 2) (expt y x))
   ((zerop x) 1)
   (t (generalized-expt (1- z) (generalized-expt z (1- x) y) y))))

(defun ackermann (x y)
  "Evaluate Ackermann's function using generalized exponential."
  (if (zerop x) (1+ y)
      (- (generalized-expt (1- x) (+ y 3) 2) 3)))

#|
;;; A few sample calls
(generalized-expt 1 0 3)
(generalized-expt 2 0 3)
(ackermann 3 2)
(ackermann 3 5)
(ackermann 4 0)
(ackermann 4 1)
|#

-- 
Dave Seaman			dseaman@purdue.edu
Amnesty International calls for new trial for Mumia Abu-Jamal
<http://www.amnestyusa.org/abolish/reports/mumia/>