pete-7.c is the largest of the nine entries an anonymous "Pete" submitted to Bignum Bakeoff.[1] It placed third in the competition, behind marxen.c and loader.c.
pete-7.c uses a linear array notation defined by the following rules:
- \(f_x(0, 0, \ldots, 0, 0) = x\)
- \(f_x(a_1, a_2, a_3, \ldots, a_{n - 1}, a_n + 1) = f_y(a_1, a_2, a_3, \ldots, a_{n - 1}, 0)\) where \(y = f_x(a_1, a_2, a_3, \ldots, a_{n - 1}, a_n)^2\)
- \(f_x(a_1, a_2, a_3, \ldots, a_n + 1, 0, 0, \ldots, 0, 0) = f_x(a_1, a_2, a_3, \ldots, a_n, x, x, \ldots, x, x)\)
Define the sequence \(n_0 = 99\) and \(n_{i + 1} = 9 \cdot 2^{n_i}\), letting \(N = n_{16}\). The output value is then \(f_N(N, 0, 0, \ldots, 0, 0)^2\) with \(N - 1\) copies of 0.
David Moews, the judge, estimated that pete-7.c is between \(f_{\omega^\omega}(2\uparrow\uparrow 35)\) and \(f_{\omega^\omega}(2 \uparrow\uparrow 36)\) in the fast-growing hierarchy.
Code[]
#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);
}
Sources[]
See also[]
Large numbers in computers
Main article: Numbers in computer arithmetic
127 · 128 · 256 · 32767 · 32768 · 65536 · 2147483647 · 4294967296 · 9007199254740991 · 9223372036854775807 · FRACTRAN catalogue numbersBignum Bakeoff contestants: pete-3.c · pete-9.c · pete-8.c · harper.c · ioannis.c · chan-2.c · chan-3.c · pete-4.c · chan.c · pete-5.c · pete-6.c · pete-7.c · marxen.c · loader.c
Channel systems: lossy channel system · priority channel system
Concepts: Recursion