Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

closed as unclear what you're asking by Alex M., tired, Lovsovs, Daniel W. Farlow, Jonas Mar 8 at 8:04

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question.If this question can be reworded to fit the rules in the help center, please edit the question.

6  
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 7 at 16:23
10  
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 7 at 16:27
5  
On my phone computing $2^{2500000}$ takes a little less than 2 seconds. – Omar Antolín-Camarena Mar 7 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 7 at 17:43
19  
@SteveJessop I can determine the binary expansion of 2**250000 in under a second, too, even without a computer. – Federico Poloni Mar 7 at 18:39
up vote 25 down vote accepted

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.

share|cite|improve this answer
2  
You better do these calculations in a base 10 representation, otherwise it can be done somewhat easier ;) – Carsten S Mar 7 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 7 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 7 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 8 at 4: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 at 19:08

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$.

share|cite|improve this answer
    
Yep. Nice anecdote with logarithm-tables too. I actually found such a book in a library once. – mathreadler Mar 7 at 17:15
1  
Um, $75257.475\not=10000+7.525475$.... – Barry Cipra Mar 7 at 17:25
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 7 at 17:54
1  
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 7 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 8 at 3:35

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.

share|cite|improve this answer
    
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 7 at 22:14

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

share|cite|improve this answer
    
You would preferably use a basis which is the one you want to write the answer in. – mathreadler Mar 7 at 17:12
4  
See Emilios answer with log tables and base 10. It has better explanations than mine. – mathreadler Mar 7 at 17:17

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

share|cite|improve this answer
2  
As big numbers go, any given number is small. – Asaf Karagila Mar 7 at 22:00
1  
@AsafKaragila: Is A(g64,g64) small? A = Acermann function, g64 = Graham's number. – Joshua Mar 7 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 7 at 22:50

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

Exponentiation by squaring is useful for this.

share|cite|improve this answer

If you could somehow compute absurdly high powers (and as has been noted by many here, 250000 is tiny it doesn't come close to being large, let alone absurdly large), then integer factorization would be a piece of cake. Sadly, there is no known way to compute absurdly large powers, so this isn't feasible as of yet. Suppose that you can evaluate the quantities $y_r$ defined recursively as:

$$y_{r+1} = 2^{y_r}$$

where $y_0 = 1$, modulo some large integer $N$. Now, computing an exponentiation modulo N allows you to reduce modulo $\phi(N)$ in the exponent, $\phi(\phi(N))$ in the exponent of the exponent etc. etc.. Since repeatedly taking the Euler totient function of a number leads to 1, this means that after a while the $y_r$ mod N become a constant as a function of r. This allows you to deduce the prime factorization of $N$.

share|cite|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.