[comp.lang.c] Ackermann's function is wrong in Moto Benchmark Report

tim@amdcad.UUCP (05/20/87)

In the "Apples to Oranges" MC68020 Benchmark Report Motorola put out in
1986, the C code for Ackermann's function was shown as:

/* Ackerman's function (in C) */

main()
{
	A(3,6);
}

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)));


Could someone from Motorola verify that the time to run the correct
version of the benchmark is the same as the time listed for the
incorrect version?

	-- Tim Olson
	Advanced Micro Devices

firth@sei.cmu.edu (Robert Firth) (05/20/87)

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!

toma@tekgvs.TEK.COM (Thomas Almy) (05/21/87)

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:
[ some code deleted ]

>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. [ ... ] 
>The last line should be written:
>
>	return (A(x-1,A(x,--y)));


Not only that, but using all of those decrement operations turns the
benchmark into a good compiler test (rather than a processor test).
Is the C compiler smart enough to realize that storing the incremented y
(in the first case) or decremented x or y (latter cases) is not necessary?
I wouldn't be happy unless the benchmark was:

	if (x==0) return (y+1);
	if (y==0) return (A(x-1,1));
	return(A(x-1,A(x,y-1)));

Tom Almy