From: ags@seaman.cc.purdue.edu (Dave Seaman) Subject: Re: Ackermann function Date: 7 Jul 1999 10:51:59 -0500 Newsgroups: comp.programming,sci.math In article <01bec80f$25112da0$98764e0c@default>, Steven Sivek wrote: >Actually, you can do much better (provided you have some convienient method >of storing big enough numbers); if the code is truly optimized for speed, >you'll store the already-calculated values of ackermann(a, b) in a >two-dimensional array and base further results on what you've already >solved until you have a nice handy reference table floating around in the >computer's memory. Fibonacci(100) would take years to calculate >recursively; that's why optimal code would store the previous results so >they can be checked quickly (doing so with the Fibonacci example would >reduce execution time from years to milliseconds). Here is an implementation in Common Lisp. It defines the Ackermann function in terms of the Ackermann generalized exponential. I was able to compute (ackermann 4 2) fairly quickly; it has 19,729 digits. I would not recommend trying to compute (ackermann 4 3). #| *********************************************************************** 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))) -- Dave Seaman dseaman@purdue.edu Pennsylvania Supreme Court Denies Fair Trial for Mumia Abu-Jamal ============================================================================== From: dlrenfro@gateway.net (Dave L. Renfro) Subject: Re: Progression of operators? Date: 2 Sep 1999 08:55:11 -0400 Newsgroups: sci.math bobg0 [sci.math Wed, 01 Sep 1999 16:18:32 GMT] wrote (in part) >Ok, you've piqued my curiosity. >But I can't find "Ackermann heirarchy" on the web and can't get >to a library for a while. I'm in a hurry now (I'll post more on these issues this afternoon), but here's a website on Ackermann's function: Some related websites ... ============================================================================== From: "Dann Corbit" Subject: Re: WORLD'S LARGEST NUMBER Date: Wed, 22 Dec 1999 13:04:36 -0800 Newsgroups: sci.math /* ** Computability is another problem. You will need extended precision and ** Err... Lot's of patience... to calculate large values. */ #include #include #include long double Ackermann(long double m, long double n) { if (m == 0) return (++n); else { if (n == 0) return Ackermann(m - 1, 1); else return Ackermann(m - 1, Ackermann(m, n - 1)); } assert(0); } int main(void) { printf("Ackermann(1,1) = %.0Lf\n", Ackermann(1, 1)); printf("Ackermann(2,1) = %.0Lf\n", Ackermann(2, 1)); printf("Ackermann(1,2) = %.0Lf\n", Ackermann(1, 2)); printf("Ackermann(2,2) = %.0Lf\n", Ackermann(2, 2)); printf("Ackermann(3,1) = %.0Lf\n", Ackermann(3, 1)); printf("Ackermann(2,3) = %.0Lf\n", Ackermann(2, 3)); printf("Ackermann(3,3) = %.0Lf\n", Ackermann(3, 3)); puts("Better get some coffee and hope your machine has a large stack..."); printf("Ackermann(4,2) = %.0Lf\n", Ackermann(4, 2)); /* How brave are you? printf("Ackermann(10,10) = %.0Lf\n", Ackermann(10,10)); */ printf("Ackermann(1,1) = %.0Lf\n", Ackermann(1, 1)); return 0; } /* ** You'll be sorry. */ -- C-FAQ: http://www.eskimo.com/~scs/C-faq/top.html "The C-FAQ Book" ISBN 0-201-84519-9 C.A.P. Newsgroup http://www.dejanews.com/~c_a_p C.A.P. FAQ: ftp://38.168.214.175/pub/Chess%20Analysis%20Project%20FAQ.htm ============================================================================== From: Nicolas Bray Subject: Re: WORLD'S LARGEST NUMBER Date: Thu, 23 Dec 1999 19:37:24 -0800 Newsgroups: sci.math To: OX2X On 22 Dec 1999, OX2X wrote: > Are you telling me that Ackermann(100) > is greater than say > 100^(100^(100^(100...^100))) > for say 100 iterations of exponentiation? > > I am very interested in this Ackermann > function. Could you walk me thru step by > step in a calculation of say Ackermann(3) > using letters X,Y, Z etc. to denote large > numbers if the actual calculated numbers > get " to large to write " ? Ackermann(3) is[get ready for it] 16. Wow, impressive, huh? Ackermann(4) is 2^2^2^2...^2 (65,536 times)...ahem. As you can see, Ackermann grows very quickly. My reference on this subject(Ramsey Theory by Graham, Rothschild and Spencer) seems to disagree with the language other people are using so I'm not exactly sure what the standard terminology is, but here we go. The Ackermann *hierarchy* is a sequence of functions {f_i(x)} defined inductively by f_i(1)=2 and f_{i+1}(x+1)=f_i(f_{i+1}(x)) and f_1(x)=2x. Now the Ackermann *function* is a function of one variable defined by Ackermann(n)=f_n(n). Thus Ackermann(3)=f_3(3)=f_2(f_3(2)) =f_2(f_2(f_3(1)))=f_2(f_2(2))=f_2(f_1(f_2(1))=f_2(f_1(2))=f_2(4) =f_1(f_2(3))=f_1(f_1(f_2(2)))=f_1(f_1(f_1(f_2(1))))=f_1(f_1(f_1(2)))= f_1(f_1(4))=f_1(8)=16. Very tedious. I'm surprised I even bothered to write it down. On the subject of "efficient generation of large numbers", Ackermann(4) is so large that it has no useful physical interpretation. In fact, it's so large that the number of digits of Ackermann(4) doesn't have a useful physical interpretation. In fact, it's so large that "the number of digits of" x 10,000 of Ackermann(4) doesn't have a useful physical interpretation.