Tetration (print 100^100^100^100^100^100^100^100^100^100^100^100^100^100)

[jononanon]

Stefan Ram asks the following:

The largest value a single bit can hold is not limited.
It just depends on the code used. For example, I can use this code:

bit
state meaning
0 the number 0
1 the number 100^100^100^100^100^100^100^100^100^100^100^100^100^100

For large numbers, see:

http://www.scottaaronson.com/writings/bignumbers.html
http://mathoverflow.net/questions/34710/succinctly-naming-big-numbers-zfc-versus-busy-beaver
http://jeremykun.wordpress.com/2012/02/08/busy-beavers-and-the-quest-for-big-numbers/
http://en.wikipedia.org/wiki/Busy_beaver
http://www.strangehorizons.com/2001/20010402/biggest_numbers.shtml
http://mrob.com/pub/math/largenum-5.html

. With C, one can use the literal »1«:

{ number c;
init( &c, 1 );
print( c ); }

will print

100^100^100^100^100^100^100^100^100^100^100^100^100^100

, given an appropriate definition for »number«, »init«, and »print«
(exercise).

 

[jononanon]

100^100^100^100^100^100^100^100^100^100^100^100^100^100 is 100^^14

See http://en.wikipedia.org/wiki/Tetration

To print this huge number, you can print a '1' and then very many '0's.

putchar('1') and then
putchar('0') numerous times.

How many '0's exactly?

Well x13 '0's, where
x13 is a number that begins with '2' and has x12 '0's.
x12 is a number that begins with '2' and has x11 '0's.
x11 is a number that begins with '2' and has x10 '0's.
x10 is a number that begins with '2' and has x09 '0's.
x09 is a number that begins with '2' and has x08 '0's.
x08 is a number that begins with '2' and has x07 '0's.
x07 is a number that begins with '2' and has x06 '0's.
x06 is a number that begins with '2' and has x05 '0's.
x05 is a number that begins with '2' and has x04 '0's.
x04 is a number that begins with '2' and has x03 '0's.
x03 is a number that begins with '2' and has x02 '0's.
x02 is a number that begins with '2' and has x01 '0's.
x01 is a number that begins with '2' and has exactly 2 '0's. -> i.e. x01 = 200


So this is a rediculously large number.

The problem is, how can one print x13 '0's ???
Which algorithm can one use?

One could think of a kind of Turing-tape.
We begin with x01, where the tape has 3 symbols: '2','0','0'

Each symbol gets a counter:
'2' has a counter with 2 states
'0' has a counter with 10 states

We start with one counter and iterate it through its states. If the specific counter overflows back to the original state, we trigger the next counter to go to the next state, etc. Similar to the kilometer-distance displays on cars.

2*10*10 = 200

While iterating through the 200 states of x01-tape, we write that many '0's onto a second tape, the x02-tape.


Then we have the x02-tape which begins with '2' and has 200 '0's.
Again each symbol of the x02-tape gets a counter (as described above).
These counters iterate and create the x03-tape.
etc. etc.

I wonder if it is possible to write a realistic program, that uses clever recursion, to write exacly x13 '0's. Obviously the requirement is: no stack-overflows and other caveats!
Somehow I don't think that anyone has written this program, so it's an open question.

 

[jononanon]

100^100^100^100^100^100^100^100^100^100^100^100^100^100 is 100^^14

See http://en.wikipedia.org/wiki/Tetration

To print this huge number, you can print a '1' and then very many '0's.

putchar('1') and then
putchar('0') numerous times.

How many '0's exactly?

Well x13 '0's, where
x13 is a number that begins with '2' and has x12 '0's.
x12 is a number that begins with '2' and has x11 '0's.
x11 is a number that begins with '2' and has x10 '0's.
x10 is a number that begins with '2' and has x09 '0's.
x09 is a number that begins with '2' and has x08 '0's.
x08 is a number that begins with '2' and has x07 '0's.
x07 is a number that begins with '2' and has x06 '0's.
x06 is a number that begins with '2' and has x05 '0's.
x05 is a number that begins with '2' and has x04 '0's.
x04 is a number that begins with '2' and has x03 '0's.
x03 is a number that begins with '2' and has x02 '0's.
x02 is a number that begins with '2' and has x01 '0's.
x01 is a number that begins with '2' and has exactly 2 '0's. -> i.e. x01 = 200


So this is a rediculously large number.

The problem is, how can one print x13 '0's ???
Which algorithm can one use?

One could think of a kind of Turing-tape.
We begin with x01, where the tape has 3 symbols: '2','0','0'

Each symbol gets a counter:
'2' has a counter with 2 states
'0' has a counter with 10 states

We start with one counter and iterate it through its states. If the specific counter overflows back to the original state, we trigger the next counter to go to the next state, etc. Similar to the kilometer-distance displays on cars.

2*10*10 = 200

While iterating through the 200 states of x01-tape, we write that many '0's onto a second tape, the x02-tape.


Then we have the x02-tape which begins with '2' and has 200 '0's.
Again each symbol of the x02-tape gets a counter (as described above).
These counters iterate and create the x03-tape.
etc. etc.

I wonder if it is possible to write a realistic program, that uses clever recursion, to write exacly x13 '0's. Obviously the requirement is: no stack-overflows and other caveats!
Somehow I don't think that anyone has written this program, so it's an open question.

 

[jononanon]

An interesting question is: how can one generate large numbers of loops efficiently.

Here we need a huge vast near endless number of loops.
If read a bit about the Busy Beaver numbers, and was pondering:

what if we want to create a really "Busy" C program, that performs an incredibly large number of loops.
HOW DO YOU GENERATE MANY LOOP, WITH LITTLE CODE?

Here's my take:

//note: this is NOT the solution to printing 100^^14, or looping x13 times.


#include <stdio.h>

typedef unsigned u_t;

u_t count;

u_t marker;
void it(u_t n, u_t n2, u_t n3)
{
if (n3 > 0) {
it(n, n2, n3-1); it(n, n2, n3-1);
} else if (n2 > 0) {
it(n, n2-1, marker); it(n, n2-1, marker);
} else if (n > 0) {
it(n-1, marker, marker); it(n-1, marker, marker);
} else
count++;
}


int main(void)
{
u_t i;
for (i = 0; i < 6; ++i) {
it(marker = i, i, i);
printf("%2u %u\n", i, count);
count = 0;
}
return 0;
}



One can of course generalize the number of arguments, by using an array and dynamic memory:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef unsigned u_t;

u_t count;


void *create_copy(u_t num, const u_t *p)
{
void *tmp = malloc(num*sizeof(u_t));
if (tmp == NULL) {
fprintf(stderr, "Error: Out of memory\n");
exit(EXIT_FAILURE);
}
memcpy(tmp, p, num*sizeof(p[0]));
return tmp;
}

u_t marker;

void dec(u_t num, u_t *copy, u_t offset)
{
u_t *lim = copy+num;
copy += offset;
(*copy)--;
while ((++copy) < lim)
*copy = marker;
}


void print_current(u_t num, const u_t *p)
{
const u_t *lim = p+num;
while (p < lim) {
printf("%u ", *p);
++p;
}
putchar('\n');
}

void it(u_t num, u_t *p)
{
u_t *p2 = p+num;
u_t *copy;
u_t n;
//print_current(num, p);
while (p2 > p) {
n = *(--p2);
if (n > 0) {
copy = create_copy(num, p);
dec(num, copy, p2-p);
it(num, copy); it(num, copy);
free(copy);
return;
}
}
count++;
}


int main(void)
{
u_t i;
for (i = 0; i < 3; ++i) {
marker = i;
it(3, (u_t []){i, i, i});
printf("%2u %u\n", i, count);
count = 0;
}
return EXIT_SUCCESS;
}


Can you come up with some code that creates even more loops, than running say:
it(5, (u_t []){(u_t)-1, (u_t)-1, (u_t)-1, (u_t)-1, (u_t)-1};
??

Here one will create insanely many loops, but I think the stack will suffer!!


So:
HOW DO YOU GENERATE MANY LOOP, WITH LITTLE CODE AND WITHOUT "ABUSING" THE STACK?

How can one create insanely many loops, without abusing the stack? (Is there an elegant way, that perhaps does not use recursion?)

 

[Stefan Ram]

[uppercase letters]

Instead of nested loops

for( int i = 5; i < 7; ++i )for( int j = 3; j < 6; ++j )printf( "%d %d\n", i, j );

, one can always use non-nested loops:

int l = 1; int i = 5; int j = 3; while( l )
if( i < 7 )if( j < 6 )printf( "%d %d\n", i, j++ ); else ++i, j = 3; else l = 0;

, which do not use much more stack.

To print 100^^14: »printf( "100^^14" )«.

 

[jononanon]

Instead of nested loops

for( int i = 5; i < 7; ++i )for( int j = 3; j < 6; ++j )printf( "%d %d\n", i, j );

, one can always use non-nested loops:

int l = 1; int i = 5; int j = 3; while( l )
if( i < 7 )if( j < 6 )printf( "%d %d\n", i, j++ ); else ++i, j = 3; else l = 0;

, which do not use much more stack.

Do you even know what stack is?? I ask, because I don't think stack is an issue with either of the above snippets. (But it is an issue during recursion).

By the way: I do not like you're non-nested loops above. It is completely inefficient and redundand to check (i < 7) the whole time.
The for loops are better and faster.

To print 100^^14: printf( "100^^14" )

My hero.