-3

Which is the largest power of natural number that can be evaluated by computers? For example if we take a very large power of 7: $7^{120000000000}$. Can a computer calculate this number?

parkhyeyoo
  • 177
  • 3
    https://youtu.be/eB5VXJXxnNU?t=53 – Git Gud Jun 28 '15 at 09:24
  • This is not a power of natural number it's just an infinite number of 9s. – parkhyeyoo Jun 28 '15 at 09:25
  • Oh!${{{{{}}}}}$ – Git Gud Jun 28 '15 at 09:27
  • But, in base $10$, a power of $10$ is an 1 followed by a sequence of 0s. So one could argue that the highest power of ten the following code can calculate is limited only by the time until the program is stopped or the computer or the output fails: putchar('1'); while(1) putchar('0'); – celtschk Jun 28 '15 at 09:35
  • It takes about 42GB to represent $7^{120,000,000,000}$ in computer. Since we have PC with ram of order $\sim 200$GB these days, I don't see any problem to compute such a number on a high-end PC. – achille hui Jun 28 '15 at 09:38
  • But if we take a greater power then even all computers on the earth wont be able to store its digits. – parkhyeyoo Jun 28 '15 at 09:41
  • Since there is no need to store the number in RAM, and multi-terabyte disks are common these days, you can even go much farther than that (note that to do multiplications, you only need to have a small part of the number in RAM at any point in time). – celtschk Jun 28 '15 at 09:42
  • But you need memory to store those digits. When the powers become really large there wont be enough memory to store them. – parkhyeyoo Jun 28 '15 at 09:43
  • @parkhyeyoo: Then just add another disk to increase the storage. However at some point in time we will run out of material to build disks from. However I just suggest to switch to a different representation: Just store numbers as triple (base, mantissa, exponent), and even much larger powers can be stored :-) – celtschk Jun 28 '15 at 09:44
  • You can't store $ (10000^{100000})^{100000}$ because there are less atoms in the visible universe . – parkhyeyoo Jun 28 '15 at 09:46

1 Answers1

6

That number will not be a problem. Using elementary methods, we estimate that it will have around 101 billion digits. It's easy to store 2 digits in a byte, so we can guess that the final result will occupy about 50 GB. Most computers don't have so much memory, but 50 GB is not an unusually large disk file and the intermediate results can be stored on the disk.

The calculation requires relatively few operations. If we had $x_0 = 7^{29296875}$ we could then calculate $x_1 = x_0^2, x_2 = x_1^2, \ldots$, and then $x_{12}$ would be the answer we seek.

But we can get $x_0 = 7^{29296875}$ by first calculating $y = 7^{5859375}$, then $y' = y^2, x_0 = y'\cdot y'\cdot 7$. Done in this fashion the entire calculation of $7^{120000000000}$ requires only around 45 multiplications, of which about half are easy and half are more difficult. The difficult multiplications can be done using Fourier transform methods; the schoolbook algorithm is too slow for numbers this large.

MJD
  • 65,394
  • 39
  • 298
  • 580
  • But if we take an even larger power then perhaps all computers on the planet won't be able to store its digits. – parkhyeyoo Jun 28 '15 at 09:38
  • True. For example, we can say that it is probably quite impossible to calculate $7^{10^{100}}$ since all the computers in the universe won't be able to store its digits. – MJD Jun 28 '15 at 09:42