Google Groups no longer supports new Usenet posts or subscriptions. Historical content remains viewable.

Dismiss

BIGNUM BAKEOFF contest results

24 views

Skip to first unread message

David Moews

unread,

Mar 8, 2002, 7:06:11 PM3/8/02

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 <suck...@ihug.co.nz>.

Entries received and accepted
------- -------- --- --------

Entrant Program name

Scott Carnahan <carn...@Math.Berkeley.EDU> {carnahan.c}
Tak-Shing Chan <T.T....@city.ac.uk> {chan.c}
Tak-Shing Chan <T.T....@city.ac.uk> {chan-2.c}
Tak-Shing Chan <T.T....@city.ac.uk> {chan-3.c}
Morris Dovey <mrd...@iedu.com> {dovey.c}
Elchonon Edelson <ede...@pobox.com> {edelson.c}
Chuck F <cbfal...@worldnet.att.net> {f.c}
Russell Harper <rharp...@rogers.com> {harper.c}
Ioannis <jg...@ath.forthnet.gr> {ioannis.c}
Ralph Loader <suck...@ihug.co.nz> {loader.c}
Heiner Marxen <Heiner...@DrB.Insel.DE> {marxen.c}
pete <pfil...@mindspring.com> {pete.c}
pete <pfil...@mindspring.com> {pete-2.c}
pete <pfil...@mindspring.com> {pete-3.c}
pete <pfil...@mindspring.com> {pete-4.c}
pete <pfil...@mindspring.com> {pete-5.c}
pete <pfil...@mindspring.com> {pete-6.c}
pete <pfil...@mindspring.com> {pete-7.c}
pete <pfil...@mindspring.com> {pete-8.c}
pete <pfil...@mindspring.com> {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))))

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

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 <stdlib.h>

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;i<n;i++){
if(!x[i]){m++;n--;}
y[i]=i>1?b(k-1,x[m+i]):(i?(n-1?x[m+i]-1:0):x[m+i]);
}
for(i=0;i<n;i++)y[n+i]=i?a(k,n,y):*y-1;
i=a(k,n,y+n);
free(y);
return i;
}
}

int b(int k, int n){
int *v,i;
v=malloc(n);
for(i=0;i<n;i++)v[i]=n;
i=k?a(k,n,v):n;
free(v);
return i;
}

int d(int l,int m,int n){
return l?(m?d(l-1,d(l,m-1,n),d(l,m-1,n)):d(l-1,d(l,l-1,n),d(l,l-1,n))):(m?d(0,m-1,d(0,m,n-1)):b(n,n));
}

int main(){
return d(d(d(9999,9,9),9,9),9,9);
}

# chan.c #

int A(int y, int z) { return !y?z+1:!z?A(y-1,1):A(y-1,A(y,z-1)); }

#define _(A, B) int B(int y, int z) { return !y?A(z+1,z+1):!z?\
B(y-1,1):B(y-1,B(y,z-1)); }

_(A,B)_(B,C)_(C,D)_(D,E)_(E,F)_(F,G)_(G,H)_(H,I)_(I,J)_(J,K)_(K,L)
_(L,M)_(M,N)_(N,O)_(O,P)_(P,Q)_(Q,R)_(R,S)_(S,T)_(T,U)_(U,V)_(V,W)
_(W,X)_(X,Y)_(Y,Z)_(Z,a)_(a,b)_(b,c)_(c,d)_(d,e)_(e,f)_(f,g)_(g,h)
_(h,i)_(i,j)_(j,k)_(k,l)_(l,m)_(m,n)_(n,o)_(o,p)_(p,q)_(q,r)_(r,s)
_(s,t)_(t,u)_(u,v)_(v,w)_(w,x)

int main(void) { return x(99999, 99999); }

# chan-2.c #

int A(int x, int y, int z)
{ return !x?y+z:!z?y:A(x-1,y,A(x,y,z-1)); }

#define B(x, y) A(y, y, y)

#define _(F, G) int G(int x, int y) \
{ return !x?G(F(0,y),F(0,y)):x==1?F(0,y):G(x-1,F(0,y)); }

_(B,C)_(C,D)_(D,E)_(E,F)_(F,G)_(G,H)_(H,I)_(I,J)_(J,K)_(K,L)
_(L,M)_(M,N)_(N,O)_(O,P)_(P,Q)_(Q,R)_(R,S)_(S,T)_(T,U)_(U,V)
_(V,W)_(W,X)_(X,Y)_(Y,Z)_(Z,a)_(a,b)_(b,c)_(c,d)_(d,e)_(e,f)
_(f,g)_(g,h)_(h,i)_(i,j)_(j,k)_(k,l)_(l,m)_(m,n)_(n,o)_(o,p)
_(p,q)_(q,r)_(r,s)_(s,t)_(t,u)_(u,v)_(v,w)

int main(void)
{ return w(0, 999999999999999999999999999999999999999); }

# chan-3.c #

int A(int x, int y, int z)
{ return !x?y+z:!z?y:A(x-1,y,A(x,y,z-1)); }

int B(int z)
{ return A(z,z,z); }

int C(int t, int u, int v, int w, int x, int y, int z)
{ return !t?B(z):
!u?B(C(t,C(t-1,0,0,0,0,0,B(z)),v,w,x,y,B(z))):u==1?B(z):
!v?B(C(t,u,C(t,u-1,0,0,0,0,B(z)),w,x,y,B(z))):v==1?B(z):
!w?B(C(t,u,v,C(t,u,v-1,0,0,0,B(z)),x,y,B(z))):w==1?B(z):
!x?B(C(t,u,v,w,C(t,u,v,w-1,0,0,B(z)),y,B(z))):x==1?B(z):
!y?B(C(t,u,v,w,x,C(t,u,v,w,x-1,0,B(z)),B(z))):y==1?B(z):
B(C(t,u,v,w,x,y-1,B(C(t,u,v,w,x-1,0,B(z))))); }

int main(void)
{ return C(9999, 0, 0, 0, 0, 0, 9999); }

# dovey.c #

int main(void)
{ return ~0u >> 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 ))))))))))))))))