Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #19906

Re: Tetration (print 100^100^100^100^100^100^100^100^100^100^100^100^100^100)

Show all headers | View raw

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.

Back to comp.lang.c | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

Tetration (print 100^100^100^100^100^100^100^100^100^100^100^100^100^100) jononanon@googlemail.com - 2012-04-25 08:22 -0700
  Re: Tetration (print 100^100^100^100^100^100^100^100^100^100^100^100^100^100) jononanon@googlemail.com - 2012-04-25 08:56 -0700
    Re: Tetration (print 100^100^100^100^100^100^100^100^100^100^100^100^100^100) jononanon@googlemail.com - 2012-04-25 13:13 -0700
      Re: Tetration (print 100^100^100^100^100^100^100^100^100^100^100^100^100^100) jononanon@googlemail.com - 2012-04-25 13:49 -0700
  Re: Tetration (print 100^100^100^100^100^100^100^100^100^100^100^100^100^100) jononanon@googlemail.com - 2012-04-25 08:47 -0700

csiph-web