BIGNUM BAKEOFF contest recap ------ ------- ------- ----- The aim of this contest was to write a C program of 512 characters or less (excluding whitespace) that returned as large a number as possible from main(), assuming C to have integral types that can hold arbitrarily large integers. The winner is Ralph Loader . Entries received and accepted ------- -------- --- -------- Entrant Program name Scott Carnahan {carnahan.c} Tak-Shing Chan {chan.c} Tak-Shing Chan {chan-2.c} Tak-Shing Chan {chan-3.c} Morris Dovey {dovey.c} Elchonon Edelson {edelson.c} Chuck F {f.c} Russell Harper {harper.c} Ioannis {ioannis.c} Ralph Loader {loader.c} Heiner Marxen {marxen.c} pete {pete.c} pete {pete-2.c} pete {pete-3.c} pete {pete-4.c} pete {pete-5.c} pete {pete-6.c} pete {pete-7.c} pete {pete-8.c} pete {pete-9.c} (A string in curly braces, e.g. {foo}, refers to another part of this article, labeled # foo #.) Entries in order of quality ------- -- ----- -- ------- The notation used to denote large numbers is explained below. Program name Lower bound Upper bound on absolute value on absolute value of return value of return value {carnahan.c} does not terminate {pete.c} does not terminate {pete-2.c} does not terminate {dovey.c} 1 1 {edelson.c} 1 1 {f.c} 1 1 {pete-3.c} 9 * 2**1566 9 * 2**1566 {pete-9.c} E(386201107) E(386201108) {pete-8.c} E(386201107) E(386201108) {harper.c} E(2**(2**(10**8+2))) E(2**(2**(10**8+3))) {ioannis.c} F[1,0]@@115(9) F[1,0]@@116(9) {chan-2.c} F[1,47](5*10**38-1) F[1,48](10**39+95) {chan-3.c} F[2,0](4999) F[2,4](199999) {pete-4.c} F[32,10**5](9) F[32,10**5](11) {chan.c} F[50,0](99998) F[50,0](100001) {pete-5.c} F[omega**11]@@16(999) F[omega**11]@@16(1031) {pete-6.c} F[omega**23](9*(2**9999)) F[omega**23](9*(2**9999)+2) {pete-7.c} F[omega**omega](E(35)) F[omega**omega](E(36)) {marxen.c} big big ( >> F[omega**omega](E(500)) ) {loader.c} very big very big Philosophical remarks ------------- ------- Never forget that it is a waste of energy to do the same thing twice, and that if you know precisely what is to be done, you need not do it at all. --- E. E. ``Doc'' Smith (1930) ...the optimal solution avoids all pattern. --- Douglas Hofstadter (1983) Many entries had program text that amplified one fast-growing function into a faster-growing function, and then repeated this text many times. This is a mistake as you can always automate this repetition and then do it a million times (say) under programmatic control. Once you have done this the next step is to parametrize this repetition and use the number of repetitions as an argument to your function, which you can then iterate again, etc. This leads us to the fast-growing hierarchy (defined below), and indeed many entries fell into the lower levels of this hierarchy. During discussions on the Net, some posters opined that it would be difficult or impossible to compare the sizes of numbers various programs output. This turned out not to be the case. Notation for big numbers -------- --- --- ------- I will write x**y for x raised to the power of y. For functions f and g of one argument, let f@g be the composition of f and g (i.e., (f@g)(x)=f(g(x))), and let f@@m be f iterated m times (i.e., (f@@0)(x) = x, f@@(m+1) = f@@m @ f.) Let E(x) be a tower of 2s of height x (i.e., E(0)=1, E(x+1)=2**E(x).) The first few values of E are E(0)=1, E(1)=2, E(2)=4, E(3)=16, E(4)=65536. For a function with many arguments, e.g., a four-argument function X, if I wish to consider a function with a smaller number of arguments derived from it by fixing some arguments, I'll write this as a function application with question marks for the unfixed arguments, e.g., X(a,?,b,?) for the two-argument function obtained by fixing the first argument of X to a and the third to b. Define a function F taking a sequence of nonnegative integers b1, ..., bm and a nonnegative integer x to a nonnegative integer F[b1, ..., bm](x) recursively by setting F[0, ..., 0](x) := x+1; F[b1, ..., bm+1](x) := (F[b1, ..., bm]@@x)(x) (i.e., the result of iterating F[b1, ..., bm] x times on x); F[b1, ..., bk+1, 0, 0, ..., 0](x) := F[b1, ..., bk, x, 0, ..., 0](x). ^ ^ (m-k zeroes) (m-k-1 zeroes) This recursive definition works because each F[b1, ..., bm] is defined in terms of the F[c1, ..., cm]'s, where the sequence c1, ..., cm is lexicographically less than b1, ..., bm. Instead of F[b1,...,bm], I will also occasionally write F[omega**(m-1)*b1 + omega**(m-2)*b2 + ... + bm]. You can think of omega as a meaningless symbol, although mathematicians will recognize it as the least infinite ordinal. After doing this, write F[omega**omega](x) := F[omega**x](x). F is a variant of the so-called `fast-growing hierarchy'. A heuristic for comparing values of F is as follows: if x is not too small and not too large, which of F[c1,...,cm](x) and F[d1,...,dn](x) is bigger can be determined by padding c1, ..., cm and d1, ..., dn on the left with zeroes to make them the same length; the bigger value of F will then correspond to the lexicographically bigger sequence. At the bottom of the hierarchy we have F[1](x) = 2*x; F[2](x) = x * 2**x; E(x) <= F[3](x) <= E(2*x) (if x > 0); and F[1,0](x) grows about as fast as the Ackermann function. Entries which did not terminate ------- ----- --- --- --------- {carnahan.c} is an attempt to write a recursive fast-growing function d(l,m,n) and then call it to produce a big number. However, d(l,m,n) does not terminate for any l>0 and m>=0. This is because d(l,m,n) calls d(l,m-1,n), which calls d(l,m-2,n), and so on. Eventually d(l,0,n) is called, but d(l,0,n) calls d(l,l-1,n), resulting in an infinite sequence of calls. {pete.c} and {pete-2.c} are both attempts to loop until the biggest integer is found. This cannot succeed as there is no biggest integer. Entries which output -1 ------- ----- ------ -- These entries, {dovey.c}, {edelson.c}, and {f.c} all attempt to generate a largest possible integer by using unsigned types. This also cannot succeed and these entries all return -1. Analysis of remaining smaller entries -------- -- --------- ------- ------- The first few remaining programs implement functions no bigger than F[2] or F[3]. {pete-3.c} takes 9 and shifts it left 163 times by 9 and then once by 99. The result is 9 * 2**1566, or about 2.3 * 10**472. {pete-8.c} and {pete-9.c} were meant to be further refinements of {pete-7.c}, but owing to a bug the main function in these programs, f(), does nothing except return X*X, where X is a preprocessor constant. X is defined in both these programs by preprocessor abuse. Let z(x) := 9 * (2**x). Then X is (z@@(16*(17**6)))(x), where x=999 in {pete-8.c} and x=99 in {pete-9.c}. Both 99 and 999 are between E(3) and E(4), and since neither the multiplication by 9 in z(x) nor the final squaring of X make much of a difference, both {pete-8.c} and {pete-9.c} output numbers between E(16*(17**6)+3) and E(16*(17**6)+4), i.e., between E(386201107) and E(386201108). Of course, {pete-8.c}'s number is bigger than {pete-9.c}'s. {harper.c} can be rewritten as follows (using x ** y): int f(int x, int y, int level) { int i, value; if (level == 0) return (x ** (2 ** x)); else { value = x; for (i = y - 1; i >= 0; i--) value *= f(value,i,level-1) * f(value,i,level); return (value); } } int main() { int a = 9*(2 ** 99999999); return f(a,a,11); } The value this program prints can be estimated as follows. Let g(x,b) be the largest value f(x,b,level) can take for any nonnegative value of level. What is g(x,b) as a function of x? If b=0, it is x ** (2 ** x), which I will call q(x). Now estimate g(x,b) by saying that it is about (q@@N(b))(x), for some N(b). Start with N(0) = 1. During one call to g(x,b), `value' starts at x, and is increased y times, once by calling f with y = b-1, once by calling f with y = b-2, ..., and once with y = 0. This gives the recurrence N(b) = N(b-1) + N(b-2) + ... + N(1) + N(0) (b>0) which has the solution N(b) = 2 ** (b-1). Therefore f(a,a,11) is approximately equal to (q@@(2**(a-1)))(a), and since q(x) is (very roughly) 2 ** (2 ** x) and a is roughly 2 ** (10 ** 8), g(a, a), which should be close to f(a, a, 11), is around E(2 ** (2 ** (10 ** 8))). After some more work this analysis can be made rigorous and proves that the value this program returns is between E(2 ** (2 ** (10**8 + 2))) and E(2 ** (2 ** (10**8 + 3))). The remaining programs implement functions with rates of growth comparable to or bigger than the Ackermann function, i.e., comparable to or bigger than F[1,0](x). {ioannis.c} defines (in effect) the following functions: a(1,m,n) := m+n a(k,m,1) := m (k > 1) a(k,m,n) := a(k-1,m,a(k,m,n-1)) (k > 1, n > 1) d(n) := a(n,n,n) and then returns (d@@116)(9). d(n) is an Ackermann function which grows about as fast as F[1,0](n); in fact, the returned value can be shown to be between (F[1,0]@@115)(9) and (F[1,0]@@116)(9). {chan-2.c} uses the following definitions: B(0,y,z) := y+z, B(x+1,y,0) := y, B(x+1,y,z+1) := B(x,y,B(x+1,y,z)); n(0,x,y) := B(y,y,y), n(w+1,0,y) := n(w+1,n(w,0,y),n(w,0,y)), n(w+1,1,y) := n(w,0,y), n(w+1,x+2,y) := n(w+1,x+1,n(w,0,y)). and returns n(47,0,10**39-1). You can prove that F[1,k+1](y+2*k+2) >= n(k,0,y) >= F[1,k](max(1, floor((y-1)/2)))) so F[1,48](10**39+95) >= n(47,0,10**39-1) >= F[1,47](5*10**38-1). {chan-3.c} uses the following definitions: B(0,y,z) := y+z, B(x+1,y,0) := y, B(x+1,y,z+1) := B(x,y,B(x+1,y,z)); D(z) := B(z,z,z); G[i,0](z) := D(z), (z > 0) G[i,j+1](z) := D(G[i,j](D(H[4,i](D(z))))); (z > 0) H[l,0](z) := D(z), (z > 0) H[4,i+1](z) := D(G[i,H[4,i](D(z))-1](D(z))), (z > 0) H[l,i+1](z) := D(H[l+1,H[l,i](D(z))-1](D(z))) (z > 0, l < 4) and returns H[0,9999](9999). (In the code, B(x,y,z) is called A(x,y,z), D(z) is called B(z), and G[i,j](z) and H[l,i](z) code for the values of C(t,u,v,w,x,y,z) in the following way: t u v w x y C(t,u,v,w,x,y,z) ----- ----- ----- ----- ----- ----- ---------------- i>=0 0 H[0,i](z) >=1 i+1>=1 0 H[1,i](z) >=1 >=2 i+1>=1 0 H[2,i](z) >=1 >=2 >=2 i+1>=1 0 H[3,i](z) >=1 >=2 >=2 >=2 i+1>=1 0 H[4,i](z) >=1 >=2 >=2 >=2 i+2>=2 j+1>=1 G[i,j](z) Observe that D(z) = B(z,z,z) >= z. Therefore, if C(t,u,v,w,x,y,z) is called with z > 0, z remains positive during all recursive calls to C, and it follows that all returned values from these calls to C are also positive. This proves the correspondence.) You can prove that H[l,i](z) >= F[2,0](floor((z-1)/2)) (0 <= l <= 3, i >= 1, z >= 6), H[l,i](z) <= F[2,4-l](z+(19-l)*(i+1)). Therefore, F[2,4](199999) >= H[0,9999](9999) >= F[2,0](4999). {pete-4.c} uses the following set of recursive definitions (generated by preprocessor abuse): f(0,x) := x * (2**x), g(m+1,0,x) := f(m,x), g(m+1,n+1,x) := f(m,(g(m+1,n,?)@@x)(x)), h(m,x) := g(m,x,x) (m > 0), f(m,x) := (h(m,?)@@x)(x) (m > 0). {pete-4.c} outputs g(33,99999,9). The definition of g(m,n,x) is very similar to that of F[m,n](x), and it is easy to prove that F[n+2](x) <= g(1,n,x) <= F[n+2](x+2) (x > 0), F[m,n+1](x) <= g(m+1,n,x) <= F[m,n+1](x+2) (m > 0, x > 0). so F[32,10**5](9) <= g(33,99999,9) <= F[32,10**5](11). {chan.c} defines (via preprocessor abuse) the following function: p(0,0,z) := z+1, p(x+1,0,z) := p(x,z+1,z+1), p(x,y+1,0) := p(x,y,1), p(x,y+1,z+1) := p(x,y,p(x,y+1,z)) and outputs p(49,99999,99999), which can be shown to be between F[50,0](99998) and F[50,0](100001). {pete-5.c}, {pete-6.c} and {pete-7.c} use the same set of definitions, which is easiest to write in terms of two functions q[b1,...,bm](x) and r[b1,...,bm](x) of a sequence of nonnegative integers b1, ..., bm and a nonnegative integer x: q[b1,...,bm](x) := (r[b1,...,bm](x))**2, r[0 ,...,0](x) := x, r[b1,...,b(m-1),bm+1])(x) := r[b1,...,b(m-1),0]((q[b1,..,bm]@@x)(x)), r[b1,...,bk+1,0,...,0](x) := r[b1,...,bk,x,...,x](x). ^ ^ (0 < m-k zeroes) (0 < m-k repetitions of x) As for the fast-growing hierarchy F, I will also write q[omega**(m-1)*b1 + omega**(m-2)*b2 + ... + bm] for q[b1,...,bm], and r[omega**(m-1)*b1 + omega**(m-2)*b2 + ... + bm] for r[b1,...,bm]. In each of the three programs, these two functions are implemented as one function which both returns a value and resets a global variable. In {pete-5.c}, for example, if the function A(b1,...,b11) is called after the global variable C has been set to x, it will return the value q[b1,...,b11](x) and reset C to r[b1,...,b11](x). {pete-6.c} is similar, except that the global variable is called B and A, which is defined by preprocessor abuse, takes 23 arguments. In {pete-7.c}, the global variable is still called B, but the function is called f and takes an array with members b1, ..., bm as its argument. The value returned by {pete-5.c} is somewhat ambiguous as it depends on the order of evaluation of the arguments of A. This is `unspecified' behavior according to the C standard, but this is OK as I did not prohibit unspecified behavior. To analyze {pete-5.c} I will assume that the arguments of A are always evaluated from right to left. In this case {pete-5.c} returns s(16), where s(n) and t(n) are mutually recursive functions defined as follows: s(0) := 999, t(0) := 999, s(n+1) := q[s(n),999,999,999,999,999,999,999,999,999,999](t(n)), t(n+1) := r[s(n),999,999,999,999,999,999,999,999,999,999](t(n)). {pete-6.c} returns q[a,a,...,a](a), where a := 9*(2**9999) and the sequence of a's has length 23, and {pete-7.c} returns q[omega**(b-1)*b](b), where b := (z@@32)(99) for the function z(x):= 9 * 2**x. As with {pete-4.c}, the functions defined in these programs are very similar to the fast-growing hierarchy and F[b1,...,bm](x) <= r[b1,...,bm](x) <= q[b1,...,bm](x) <= F[b1,...,bm](x+2) providing that x >= 2 and b1, ..., b(m-1) are not all zero. You can use this to (eventually) prove that the value {pete-5.c} outputs is between F[omega**11]@@16(999) and F[omega**11]@@16(1031), and that the value {pete-6.c} outputs is between F[omega**23](9*(2**9999)) and F[omega**23](9*(2**9999)+2). Finally, the value {pete-7.c} outputs will be between F[omega**omega](b) and F[omega**omega](b+2). Now 99 is between E(3) and E(4), and approximating z(x) by 2**x, we find that b = (z@@32)(99) and b+2 are both between E(35) and E(36). Therefore, the number output by {pete-7.c} is between F[omega**omega](E(35)) and F[omega**omega](E(36)). Remarks on larger entries ------- -- ------ ------- The first of the big entries is {marxen.c}. This program makes use of Goodstein sequences (for a definition of these see {Takeuti}, pp. 128 ff.) These sequences are used to define a function not provably recursive in Peano Arithmetic. This gives a number very much bigger than the preceding entries. For the mathematicians: we can extend our F hierarchy by defining F[alpha] for all ordinals alpha < epsilon_0 * 2; if we were then to place {marxen.c}'s main function in this hierarchy, it would probably fall somewhere around F[epsilon_0 + omega*2]. At any rate the value printed out is larger than the lower bound (F[omega**omega](E(500))) given above and it is certainly under F[epsilon_0 + omega**3](1000000). The final and winning entry, {loader.c}, diagonalizes over the Huet-Coquand `calculus of constructions'. This is a highly polymorphic lambda calculus such that every well-formed term in the calculus is strongly normalizing; or, to put it another way, a relatively powerful programming language which has the property that every well-formed program in the language terminates. The program's main function is called D. (D's return value depends on a global variable, so it is in fact not a pure function, but this will not be important.) D works approximately as follows: given an argument x, it iterates over all bit strings with binary value less than or equal to x, and, if such a bit string codes for a well-formed program (`term' in lambda-calculus language), it runs the program (`strongly normalizes the term' in lambda-calculus language.) The return value of D is then obtained by packaging together the return values of all these programs. The program's return value is D@@5(99). It is possible to simulate the computation of D(99) and prove that D(99) >= E(30419). Also, it is easy to prove that D(z) >= z and that D(z) is increasing with z. Therefore, the value output by the program is at least D(E(30419)). However, in {FLO}, Fortune et al. explain how to code F[omega**k] and F[epsilon_0] in the second-order typed lambda calculus. The second-order typed lambda calculus is a subset of the calculus of constructions, and the methods in {FLO} can easily be used to code, say, F[epsilon_0 + omega**3](1000000) in a relatively short program, which can be expressed by a bit string of length well under E(30419). {loader.c} is therefore the winner. Bibliography ------------ # FLO # Steven Fortune, Daniel Leivant, and Michael O'Donnell, The expressiveness of simple and second-order type structures, Journal of the Association for Computing Machinery, vol. 30, number 1 (January 1983), pp. 151--185. # Takeuti # PROOF THEORY, Gaisi Takeuti, 2nd ed. (1987), North-Holland. PROGRAMS AS ENTERED -------- -- ------- # carnahan.c # #include int a(int k,int n,int *x) { int *y,i,m=0; y = malloc(2*n); if(n==1)return *x+9; else{ for(i=0;i1?b(k-1,x[m+i]):(i?(n-1?x[m+i]-1:0):x[m+i]); } for(i=0;i> 1; } # edelson.c # int main(void) { return (unsigned int) -1; } # f.c # unsigned int u;int main(void){return --u;} # harper.c # #define I int #define w while #define r return I l(I x){I y=x;w(y--)x*=x;r x;} I k(I x,I y){w(y--)x*=k(x,y)*l(x);r x;} I j(I x,I y){w(y--)x*=j(x,y)*k(x,y);r x;} I i(I x,I y){w(y--)x*=i(x,y)*j(x,y);r x;} I h(I x,I y){w(y--)x*=h(x,y)*i(x,y);r x;} I g(I x,I y){w(y--)x*=g(x,y)*h(x,y);r x;} I f(I x,I y){w(y--)x*=f(x,y)*g(x,y);r x;} I e(I x,I y){w(y--)x*=e(x,y)*f(x,y);r x;} I d(I x,I y){w(y--)x*=d(x,y)*e(x,y);r x;} I c(I x,I y){w(y--)x*=c(x,y)*d(x,y);r x;} I b(I x,I y){w(y--)x*=b(x,y)*c(x,y);r x;} I a(I x,I y){w(y--)x*=a(x,y)*b(x,y);r x;} I main(void){r a(9<<99999999,9<<99999999);} # ioannis.c # int a(int k,int m,int n) {if (k==1) return(m+n); else {if (n==1) return m; else return a(k-1,m,a(k,m,n-1));}} #define d(n) a(n,n,n) int main(void) {return d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d( d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d( d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d( d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d(d( d(d(d(d(d(d(d(d(9))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))))))))))))))))))))))))))))))))))))))) )))))))))))))))))))));} # loader.c # #define R { return #define P P ( #define L L ( #define T S (v, y, c, #define C ), #define X x) #define F );} int r, a; P y, X R y - ~y << x; } Z (X R r = x % 2 ? 0 : 1 + Z (x / 2 F L X R x / 2 >> Z (x F #define U = S(4,13,-4, T t) { int f = L t C x = r; R f - 2 ? f > 2 ? f - v ? t - (f > v) * c : y : P f, P T L X C S (v+2, t U y C c, Z (X ))) : A (T L X C T Z (X ) F } A (y, X R L y) - 1 ? 5 << P y, X : S (4, x, 4, Z (r) F #define B (x /= 2) % 2 && ( D (X { int f, d, c = 0, t = 7, u = 14; while (x && D (x - 1 C B 1)) d = L L D (X ) C f = L r C x = L r C c - r || ( L u) || L r) - f || B u = S (4, d, 4, r C t = A (t, d) C f / 2 & B c = P d, c C t U t C u U u) ) C c && B t = P ~u & 2 | B u = 1 << P L c C u) C P L c C t) C c = r C u / 2 & B c = P t, c C u U t C t = 9 ); R a = P P t, P u, P x, c)) C a F } main () R D (D (D (D (D (99)))) F # marxen.c # typedef int J; J P(J x,J y) { return x+y ? x%2 + y%2*2 + P(x/2,y/2)*4 : 0 ;} J H(J z) { return z ? z%2 + 2*H(z/4) : 0 ;} J I(J f,J e,J r){ return f ? P(P(f,e),r) : r ;} J M(J x,J e) { return x ? I(x%2, M(e,0), M(x/2, e+1)) : 0 ;} J D(J,J); J E(J f,J e,J r,J b) { return e ? E(1, D(e,b), I(b-1, D(e,b), I(f-1,e,r)), b) : I(f-1,e,r) ; } J D(J x,J b) { return x ? E( H(H(x)), H(H(x)/2), H(x/2), b) : 0 ;} J F(J x,J b) { return x ? F(D(x,b+1),b+1) : b ;} J G(J x) { return F(M(x,9), 9) ;} J f(J n,J x) { return n ? f(n-1, G(x ? f(n,x-1) : n)) : G(x) ;} J g(J x) { return f(x,x) ;} J h(J n,J x) { return n ? h(n-1, g(x ? h(n,x-1) : n)) : g(x) ;} J main(void) { return h(g(9),9) ;} # pete.c # int main(void) { int intmax = 1; do{ intmax <<= 1; }while(intmax < intmax << 1); intmax += intmax - 1; return intmax; } # pete-2.c # int main(void) { int intmin = 0x4000; while(intmin < intmin << 1) intmin <<= 1; return intmin << 1; } # pete-3.c # int main() { return 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 9 << 99; } # pete-4.c # #define F(Q,R,P) Q(int x){int i=x;while(i--)x=R(x,x);return x;}\ P(int L,int x){int i=x;if(L--)while(i--)x=P(L,x);return Q(x);} #define Y(A,z,B,C,D,E,G,H,I,J,K,M,N,O,S,T,U,V,W)\ F(A,z,B)F(C,B,D)F(E,D,G)F(H,G,I)F(J,I,K)F(M,K,N)F(O,N,S)F(T,S,U)F(V,U,W) Z(int L,int x) { int i = x; if(L--) while(i--) x = Z(L,x); return x << x; } Y(a,Z,b,c,d,e,g,h,X,j,k,m,n,o,s,t,u,v,w) Y(Aa,w,Ba,Ca,Da,Ea,Ga,Ha,Ia,Ja,Ka,Ma,Na,Oa,Sa,Ta,Ua,Va,Wa) Y(Ab,Wa,Bb,Cb,Db,Eb,Gb,Hb,Ib,Jb,Kb,V,U,W,T,S,O,N,M) F(A,M,B) F(C,B,D) F(E,D,G) F(H,G,I) F(J,I,K) int main() { return K(99999,9); } # pete-5.c # int C = 999; A(int S,int R,int P,int O,int N,int M,int L,int K,int J,int F,int E) { int D = C; if(E--) while(D--) C = A(S,R,P,O,N,M,L,K,J,F,E); return F-- ? A(S,R,P,O,N,M,L,K,J,F,C) : J-- ? A(S,R,P,O,N,M,L,K,J,C,C) : K-- ? A(S,R,P,O,N,M,L,K,C,C,C) : L-- ? A(S,R,P,O,N,M,L,C,C,C,C) : M-- ? A(S,R,P,O,N,M,C,C,C,C,C) : N-- ? A(S,R,P,O,N,C,C,C,C,C,C) : O-- ? A(S,R,P,O,C,C,C,C,C,C,C) : P-- ? A(S,R,P,C,C,C,C,C,C,C,C) : R-- ? A(S,R,C,C,C,C,C,C,C,C,C) : S-- ? A(S,C,C,C,C,C,C,C,C,C,C) : C * C; } #define Q ,C,C,C,C,C,C,C,C,C,C) main() {return A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(A(C Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q;} # pete-6.c # #define M E H,h,g,f #define L E G,p,o,n #define K E w,v #define J ,B,B #define I J J #define H G,p,o,n,m,l,k,j,i #define G w,v,u,t,s,r,q #define F I I #define E --?A( #define D ,B): #define C ,int int B = 9 << 9999; A(int w C v C u C t C s C r C q C p C o C n C m C l C k C j C i C h C g C f C e C d C c C b C a) { int y = B; if(a--) while(y--) B = A(H,h,g,f,e,d,c,b,a); return b M,e,d,c,b D c M,e,d,c,B D d M,e,d J D e M,e J,B D f M I D g E H,h,g I,B D h E H,h I J D i E H I J,B D j L,m,l,k,j F D k L,m,l,k F,B D l L,m,l F J D m L,m F J,B D n L F I D o E G,p,o F I,B D p E G,p F I J D q E G F I J,B D r K,u,t,s,r F F D s K,u,t,s F F,B D t K,u,t F F J D u K,u F F J,B D v K F F I D w E w F F I,B D B * B; } main(){return A(B I F F J);} # pete-7.c # #define F (9<<(9<<(9<<(9<< #define D F F F F #define E )))))))))))))))) #define N D D 99 E E int B = N; f(int *a) { int C = B, b[N], n = N; while(n--) b[n] = a[n]; n = N - 1; if(b[n]--) while(C--) B = f(b); while(n-- && !(b[n + 1] = B, b[n]--)) ; return n == -1 ? B * B : f(b); } main() { int a[N] = {N}; return f(a); } # pete-8.c # #define Z (9<<(9<< #define Y Z Z Z Z Z Z Z Z #define W )))))))))))))))) #define Q Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y #define O W W W W W W W W W W W W W W W W W #define P Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q #define M O O O O O O O O O O O O O O O O O #define L P P P P P P P P P P P P P P P P P #define K M M M M M M M M M M M M M M M M M #define H L L L L L L L L L L L L L L L L L #define J K K K K K K K K K K K K K K K K K #define A H H H H H H H H H H H H H H H H H #define D J J J J J J J J J J J J J J J J J #define X A A A A A A A A A A A A A A A A A 999 D D D D D D D D D D D D D D D D D int B = X; f(int* a) { int C = B, b[X], n = X; while(n--) b[n] = a[n]; if(b[n = X - 1]--) while(C--) B = f(b); while(n && !(b[n] = B, b[--n]--)) ; return n ? f(b) : B * B; } main() { int a[X] = {X}; return f(a); } # pete-9.c # #define Z (9<<(9<< #define Y Z Z Z Z Z Z Z Z #define W )))))))))))))))) #define Q Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y Y #define O W W W W W W W W W W W W W W W W W #define P Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q Q #define M O O O O O O O O O O O O O O O O O #define L P P P P P P P P P P P P P P P P P #define K M M M M M M M M M M M M M M M M M #define H L L L L L L L L L L L L L L L L L #define J K K K K K K K K K K K K K K K K K #define A H H H H H H H H H H H H H H H H H #define D J J J J J J J J J J J J J J J J J #define X A A A A A A A A A A A A A A A A A 99\ D D D D D D D D D D D D D D D D D int B = X; f(int* a) { int C = B, b[X], n = X; while(n--) b[n] = a[n]; if(b[n = X - 1]--) while(C--) B = f(b); while(n && !(b[n] = B, b[--n]--)) ; return n ? f(b) : B * B; } main() { int a[X] = {X}; return f(a); } -- David Moews dmoews@xraysgi.ims.uconn.edu