11

Could it be at all possible to calculate, say, $2^{250000}$, which would obviously have to be written in standard notation? It seems impossible without running a program on a supercomputer to work it out.

Simply Beautiful Art
  • 74,685
Mathime
  • 367
  • 7
    You don't need a supercomputer, a not too ancient desktop or laptop can deal with that easily. If you want to do that by hand, it will take a while - especially the checking for calculation errors. – Daniel Fischer Mar 07 '16 at 16:23
  • 11
    On any Unix computer, try echo '2^250000' |bc. My 3-year-old laptop ran it in 0.64 seconds. This isn't an "absurdly high" power at all. – Nate Eldredge Mar 07 '16 at 16:27
  • 5
    On my phone computing $2^{2500000}$ takes a little less than 2 seconds. – Omar Antolín-Camarena Mar 07 '16 at 17:32
  • 2
    Python running on my laptop takes under 0.1s (average of multiple runs using the timeit module) to run str(2**250000), which calculates the base-10 representation. 2**250000 on its own takes 20 nanoseconds, but that's a bit of a cheat since it's computing in base 2 and possibly takes a "shortcut". – Steve Jessop Mar 07 '16 at 17:43
  • 20
    @SteveJessop I can determine the binary expansion of 2**250000 in under a second, too, even without a computer. – Federico Poloni Mar 07 '16 at 18:39
  • 1
    @SteveJessop Actually that time would be incorrect. Python pre-computes those values during peephole optimization when producing the initial bytecode(which I believe timeit reuses for all runs) so you simply timed the time taken to convert to string. Try a=2; b=250000; str(a**b) to avoid those optimizations. – Bakuriu Mar 07 '16 at 19:37
  • I was going to post the full decimal expansion in an answer, but unfortunately one is not allowed to post more than 30000 characters... –  Mar 07 '16 at 19:57
  • I believe it is possible to a) find how many digits there are and b) find what the last $n$th digit is, using modular arithmetic. If that is how you wish to go about finding such a solution. – Simply Beautiful Art Mar 07 '16 at 20:52
  • If you go on googology and find Graham's number, they show you how to manually find digits of an 'absurdly large number'. – Simply Beautiful Art Mar 07 '16 at 20:55
  • Curiously, the order in which the base-$10$ digits appear in this number, $3,1,5,4,9,6,2,8,7,0$, is remarkably similar to the order in which the base-$10$ digits appear in the decimal expansion of $\pi$: $3,1,4,5,9,2,6,8,7,0$. – Steve Kass Mar 07 '16 at 21:27
  • I would be surprised if any sane environment actually calculates this instead of just filling the number in binary representation at the right spot into memory. – PlasmaHH Mar 07 '16 at 21:38
  • 1
    Think about it this way. That number in binary takes about 25 kilobytes. The machine I'm typing this on has eight million kilobytes of RAM. Your number is a very small number compared to the sorts of numbers we can represent in memory if we want to. We just seldom want to. – Eric Lippert Mar 08 '16 at 05:31
  • @Bakuriu: nice, thank you. That slows the str down to 106 msec from 96, and the base-2 version from 20 nanoseconds to 1msec (I don't know why the differences in time aren't equal, so there might be even more going on). Anyway, Python and the humans are all agreed that it's much easier in base 2 than base 10 ;-) – Steve Jessop Mar 08 '16 at 10:01

6 Answers6

26

The basic idea is the following: If $k \in \mathbf N$ is even, say $k = 2m$ we have $$ 2^k = 2^m \cdot 2^m $$ if $k = 2m +1$ is odd, then $$ 2^k = 2^{2m} \cdot 2 $$ That is, we need two routines, one for squaring a number and one for doubling a number (in standard notation). This is doable on almost every computer. Now we start with 2, doing the steps \begin{align*} 2 &\leadsto 2^2 \text{ squaring}\\ &\leadsto 2^3 \text{ doubling}\\ &\leadsto 2^6 \text{ squaring}\\ &\leadsto 2^7 \text{ doubling}\\ &\leadsto 2^{14} \text{ squaring}\\ &\leadsto 2^{15} \text{ doubling}\\ &\leadsto 2^{30} \text{ squaring}\\ &\leadsto 2^{60} \text{ squaring}\\ &\leadsto 2^{61} \text{ doubling}\\ &\leadsto 2^{122} \text{ squaring}\\ &\leadsto 2^{244} \text{ squaring}\\ &\leadsto 2^{488} \text{ squaring}\\ &\leadsto 2^{976} \text{ squaring}\\ &\leadsto 2^{1952} \text{ squaring}\\ &\leadsto 2^{1953} \text{ doubling}\\ &\leadsto 2^{3906} \text{ squaring}\\ &\leadsto 2^{7812} \text{ squaring}\\ &\leadsto 2^{15624} \text{ squaring}\\ &\leadsto 2^{15625} \text{ doubling}\\ &\leadsto 2^{31250} \text{ squaring}\\ &\leadsto 2^{62500} \text{ squaring}\\ &\leadsto 2^{125000} \text{ squaring}\\ &\leadsto 2^{250000} \text{ squaring}\\ \end{align*} That is, this can be done in "not so many" multiplications.

martini
  • 84,101
  • 2
    You better do these calculations in a base 10 representation, otherwise it can be done somewhat easier ;) – Carsten S Mar 07 '16 at 19:02
  • 8
    What's so beautiful about this is I can look at your answer and tell you the binary representation of 250000 from this! – corsiKa Mar 07 '16 at 19:02
  • 2
    Fun fact: finding the optimal way of squaring & multiplying to obtain the answer is an NP-complete problem (I believe I've read this in TAOCP). However even the naive scheme usually only performs very very few multiplications or squarings more than the optimum so... – Bakuriu Mar 07 '16 at 19:41
  • 1
    The discussion to which @Bakuriu refers appears in Knuth Art of Computer Programming section 4.6.3, “Evaluation of Powers”, pp. 463–481. However, I do not see any discussion of the NP-completeness of the problem. – MJD Mar 08 '16 at 04:53
  • when you do this algorithm, do you start with the power that you want to end up with, then halve or subtract, or start from 1 (or 0) then add and double? – costrom Mar 25 '16 at 19:08
  • You start from 1 ... usually – martini Mar 25 '16 at 19:37
21

When I was young ( not so many years ago) there was not home computers and I was trained to do such kind of calculations using the ''logarithm table'', a little book from which it was possible to find the logarithms (in base $10$) of numbers.

This was the way to make calculations before computers! And it also works today!

So for your calculation we can do:

$$ \log_{10}\left(2^{250000} \right)=250000 \times \log_{10} 2 $$

From my tables I found $\log_{10} 2=0.3010299$ (clearly the problem is the precision that is limited by the number of digits in the tables, but for this purpose $7$ digits seems sufficient).

So, with a simple multiplication we have:

$$ 2^{250000} \approx 10^{75257.475}=\left(10^{10000}\right)^{7.5257475} $$ Or, as suggested by @mathmandan (thanks!): $$ 2^{250000} \approx 10^{75257.475}=10^{75257}\times 10^{0.475} $$ and my ''magic tables'' say that $10^{0.475}\approx 2.9853826$.

Emilio Novati
  • 62,675
  • Yep. Nice anecdote with logarithm-tables too. I actually found such a book in a library once. – mathreadler Mar 07 '16 at 17:15
  • 1
    Um, $75257.475\not=10000+7.525475$.... – Barry Cipra Mar 07 '16 at 17:25
  • Whaw! What a stupid mistake! – Emilio Novati Mar 07 '16 at 17:37
  • 1
    Or if you'd like, $(10^{75257}) * (10^{0.475})$. So roughly $3 * 10^{75257}$, which would be a $3$ followed by $75257$ zeros. – mathmandan Mar 07 '16 at 17:54
  • 2
    Calculators were not in use when I was learning trigonometry and precalculus (1973-74), at least they were sufficiently rare that no one at my school had a calculator and I had never seen one, so all our classroom calculations were by hand, using square root tables and logarithm tables at the back of our high school textbooks. Actually, we only needed logarithm tables for trigonometry (solving triangles), as none of the other stuff required any extensive calculations. We also frequently used linear interpolation to get more accurate values. On tests we were told whether we had to interpolate. – Dave L. Renfro Mar 07 '16 at 22:19
  • 1
    @mathreadler:, Yep, still have mine downstairs also, right beside my two ivory slide rules and Ritchie;s First Steps in Latin. – Pieter Geerkens Mar 08 '16 at 03:35
  • You may need your log tables several times if you can only take logarithms of numbers in $[1,10)$ and antilogarithms of numbers in $[0,1)$. Going down two levels: $\log_{10}\left(\log_{10}\left(2^{250000} \right)\right)=\log_{10}\left(250000 \times \log_{10} (2)\right)=\log_{10}(2.5)+5+\log_{10}(10 \times \log_{10}(2))-1$ which gives about $4.87655$. Using antilogithms once gives about $ 7.52575 \times 10^4$ i.e. about $75257.5$ and a second time gives about $3 \times 10^{75257}$. My grandfather used six-digit log tables but they are less common now – Henry Jun 10 '17 at 16:13
8

You can get pretty good approximations, but the actual calculation is difficult. For instance $$2^{250000} = (2^{10})^{25000} = (1024)^{25000} \approx (10^3)^{25000} \approx 10^{75000}$$ Which you can write out pretty easily. This is a fairly decent estimate (Wolfram gives $10^{75257.49891599528}$) You could also write the number in binary if that suits you, which is a $1$ followed by $250000$ $0$'s.

J. Bush
  • 1,049
  • Using that $\log_{10}2 \approx 0.30103$, we get $2^{250000} \approx 10^{75257.5}$. Using a better approximation for $\log_{10}2$ gives what WA gave. – lhf Mar 07 '16 at 22:14
4

As big numbers go, 2^250000 is actually small. A simple program in Ruby calculates it in a few tenths of a second:

puts 2**250000

Run it with ruby -e in a command prompt, if you have Ruby. Takes more time to display the result than to calculate it.

For really big numbers, please see

jose_castro_arnaud
  • 184
  • 2
    As big numbers go, any given number is small. – Asaf Karagila Mar 07 '16 at 22:00
  • 1
    @AsafKaragila: Is A(g64,g64) small? A = Acermann function, g64 = Graham's number. – Joshua Mar 07 '16 at 22:48
  • 1
    @Joshua: The XKCD number is only large compared to finitely many integers, but it is small compared to infinitely many. As the old saying goes, most numbers are larger. – Asaf Karagila Mar 07 '16 at 22:50
  • Graham's number will be considered by nearly everyone as "large", although much much much larger numbers have been defined and named. And the numbers shown is Saibian's page are definitely large. Just because there are infinite many numbers, and infinite numbers are larger then every given number, I do not see any reason to consider every number to be "small". – Peter Mar 19 '17 at 16:28
  • @AsafKaragila On the contrary, one might argue that almost any given number is large. – Simply Beautiful Art Jun 18 '17 at 22:56
  • And... if you ever want to include said Ruby program which happens to make said number... https://repl.it/IqzW – Simply Beautiful Art Jun 18 '17 at 22:58
  • @SimplyBeautifulArt: And I reckon that any number that can be physically represented within human lifespan is small, since there are only finitely many of these. – Asaf Karagila Jun 19 '17 at 00:34
3

Yes. Logarithm and multiplication. Use the log law $$\log(a^b) = b\log(a)$$and your exponentiation becomes $$\exp(b\log(a))$$

mathreadler
  • 25,824
0

It's possible and easy. I've put the result at http://pastebin.com/CcT5yWVS.

Exponentiation by squaring is useful for this.

Meni Rosenfeld
  • 4,013