Is there an algorithm, short cut, or trick to raising an integer to a large integer power other than by multiplying by itself over and over?
I'm asking for a pencil/paper calculation, not a computer program.
L. E. Gant
The simplest is using logarithms.
Using log to the base 10
n^m = 10^(log(n^m)) = 10^(m*log(n))
so:
look up log(n)
multiply by m
use antilog (...) to get n^m
or, use a calculator -- your computer software most likely includes a calculator.
or:
the power is either odd or even
if even, then it's of the form 2k
if odd, then it has the form 2k+1
so n^m
= n^(2k) or n^(2k+1)
= (n^k)^2 or (n^k)^2 * n
You can apply the same technique at every level down to n^1
Using 2 as n...
2^10 = 2^(2*5) = 4^5
4^5 = 4^(2*2 + 1) = 16^2 * 16 etc.
number of iterations is far less than you'd expect.
Demiurge42
One of the easiest methods is to square the base then keep squaring your result until you get a power that's greater than what you are looking for.
2^23 for example.
Instead of multiplying 22 times, calculate the following
2^1 = 2
2^2 = 4
2^4 = 4^2 = 16
2^8 = 16^2 = 256
2^16 = 256^2 = 65,536
The next square would be 2^32 which is bigger than what you are trying to find.
23 = 16 + 4 + 2 + 1 so now you can use the previous results and the properties of exponents to get:
2^23 = (2^16)(2^4)(2^2)(2^1) = (65,536)(16)(4)(2) = 8,388,608
Ian H
A better question is why would you want to use logs when a calculator would give you results like 2^123 = 10633823966279326983230456482242756608
in just a few seconds?
az_lender
It would help to have either a slide rule or a table of logarithms. Years ago, when we had no calculators, I did like to use a one-page table of logarithms.
Even if you know only a FEW common logarithms in your head, they can be helpful. For instance, I know log(2) = 0.301, log(3) = 0.477, log 7 = 0.845.
From that I can deduce that log(5) = 0.699 and log(6) = 0.778.
Now let's say I want to raise 65 to the 65th power. Using the facts just stated, I can see that log(6.5) is probably around 0.81 and so log(65) is around 1.81. Another approach would be to note that 64 = 2^6 and therefore log(65) will be be a little over 6*log(2) = 1.806. Anyhow, if log(65) = 1.81, then
log(65 ^ 65) = 65*log(65) = (enter pencil and paper) = 117.65, which is
log(10^117) + 0.65. And 0.65 might be near log(5), refer to paragraph above.
So I know that 65 to the 65th power is a 118-digit number and that the first digit might be a 4 or 5.
It turns out this isn't a great estimate. 65^65 is indeed a 118-digit number, but the first two digits are 6.9.
HOWEVER, if I had had a log table in hand, I'd have looked up log(6.5) and found that it's 0.813, so log(65) = 1.813, and 65*log(65) = (pencil and paper) = 117.845, so I'd have said 65^65 is a 118-digit number whose first digit is 7. And that would've been a very good estimate !
If this is hard to follow, get hold of an OLD algebra book and read up on common logarithms.
billrussell42
no, that is about it, unless you can use log tables.
with log tables, 5^7, for example..
log 5^7 = 7 log 5 = 4.89279
now use anti-log table to get 78125
or a good sliderule