Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!rochester!pt.cs.cmu.edu!sei!sei.cmu.edu!firth
From: firth@sei.cmu.edu (Robert Firth)
Newsgroups: comp.lang.c,comp.sys.m68k
Subject: Re: Ackermann's function is wrong in Moto Benchmark Report
Message-ID: <1383@aw.sei.cmu.edu>
Date: Wed, 20-May-87 16:41:23 EDT
Article-I.D.: aw.1383
Posted: Wed May 20 16:41:23 1987
Date-Received: Sat, 6-Jun-87 12:06:47 EDT
References: <16731@amdcad.AMD.COM>
Sender: netnews@sei.cmu.edu
Reply-To: firth@bd.sei.cmu.edu.UUCP (PUT YOUR NAME HERE)
Organization: Carnegie-Mellon University, SEI, Pgh, Pa
Lines: 48
Xref: mnetor comp.lang.c:2326 comp.sys.m68k:503

In article <16731@amdcad.AMD.COM> tim@amdcad.AMD.COM (Tim Olson) writes:
>
>In the "Apples to Oranges" MC68020 Benchmark Report Motorola put out in
>1986, the C code for Ackermann's function was shown as:

...

>A(x,y)
>int x,y;
>{
>	if (x==0) return (++y);
>	if (y==0) return (A(--x,1));
>	return (A(--x,A(x,--y)));
>}
>
>The last line is incorrect.  Depending upon evaluation order, the inner
>call to the A() function could use the undecremented value for x
>(correct) or the decremented value of x (incorrect).  The last line
>should be written:
>
>	return (A(x-1,A(x,--y)));


Actually, the whole thing is wrong.  A literal translation of Brian
Wichmann's original code into C gives

	A(m,n)
	int m,n;
	{
	    return m==0 ? n+1 : n==0 ? A(m-1,1) : A(m-1,A(m,n-1));
	}

The body is a conditional expression, and it does not modify its
parameters.  See any of

[B A Wichmann : Ackermann's Function... BIT vol 16 p 103]

[B A Wichmann : How to Call Procedures... Software Practice & Experience
		vol 7 p 317]

[B A Wichmann : Latest Results... NPL Report DITC 3/82 ISSN 0143-7348]

The original is in Algol-60, and has exactly the form I have shown, except
of course there is an assignment to the function name instead of the
keyword "return".

There seems to be no reason for the changes Motorola have made; it
certainly adds to the confusion!