Is there a simple algorithm for exponentiating large numbers to large powers?I've been thinking about this for some days, a multiplication is a lot of sums, so: 75 × 75 = 75 + 75 + 75 + 75 + 75 + 75 + 75 + 75 + ⋯ ⏞ 75 times But then, there is a simple algorithm that enable us to multiply without having to sum all those numbers. In the same way, exponentiation is repeated multiplication - but I wasn't taugth about such algorithm for exponentiation. I've been thinking in representing the number with a polynomial, for example: 1038 = 10 3 + 3 ⋅ 10 1 + 8 ⋅ 10 0 Then: 1038 1038 = ( 10 3 + 3 ⋅ 10 1 + 8 ⋅ 10 0 ) 1038 But from here (considering what I currently know) I'd have to multiply it 1038 times. The mentioned multiplication would be: ( 10 3 + 3 ⋅ 10 1 + 8 ⋅ 10 0 ) 1038 = ( 10 3 + 3 ⋅ 10 1 + 8 ⋅ 10 0 ) ⋅ ( 10 3 + 3 ⋅ 10 1 + 8 ⋅ 10 0 ) ⋅ … ⏞ 1038 times The first idea I had: There might be some connection with the binomial theorem, but I don't see how it fits. The second idea would be to find a way to write: ( 10 3 + 3 ⋅ 10 1 + 8 ⋅ 10 0 ) 1038 In which the red exponents are multiplied in some way by 1038. There might be some connection with logarithms here, but I don't see it. And it could be the case that these techniques won't yield the results I'm looking for, so: Is there a simple algorithm for large numbers elevated to large exponents?

Question

Is there a simple algorithm for exponentiating large numbers to large powers?I&#039;ve been thinking about this for some days, a multiplication is a lot of sums, so:  75  ×  75  =                              75          +          75          +          75          +          75          +          75          +          75          +          75          +          75          +          ⋯                ⏞                    75 times      But then, there is a simple algorithm that enable us to multiply without having to sum all those numbers. In the same way, exponentiation is repeated multiplication - but I wasn&#039;t taugth about such algorithm for exponentiation. I&#039;ve been thinking in representing the number with a polynomial, for example:  1038  =      10    3    +  3  ⋅      10    1    +  8  ⋅      10    0  Then:      1038          1038        =  (      10    3    +  3  ⋅      10    1    +  8  ⋅      10    0        )          1038      But from here (considering what I currently know) I&#039;d have to multiply it   1038 times. The mentioned multiplication would be:  (      10    3    +  3  ⋅      10    1    +  8  ⋅      10    0        )          1038        =                              (                      10            3                    +          3          ⋅                      10            1                    +          8          ⋅                      10            0                    )          ⋅          (                      10            3                    +          3          ⋅                      10            1                    +          8          ⋅                      10            0                    )          ⋅          …                ⏞                    1038 times      The first idea I had: There might be some connection with the binomial theorem, but I don&#039;t see how it fits. The second idea would be to find a way to write:  (      10          3        +  3  ⋅      10          1        +  8  ⋅      10          0            )          1038      In which the red exponents are multiplied in some way by   1038. There might be some connection with logarithms here, but I don&#039;t see it. And it could be the case that these techniques won&#039;t yield the results I&#039;m looking for, so: Is there a simple algorithm for large numbers elevated to large exponents?

apopihvj · Accepted Answer

This is probably not a complete answer but still worth knowing. In general, to compute       a    n  , you do not need to multiply it   n  −  1 times. You can get away with at-most       O    (      log    2    ⁡  (  n  )  ) multiplications as shown below.Write   1038 in binary as       2          10        +      2    3    +      2    2    +  2. Now to compute       a          1038      , it is now sufficient to compute only       a    2  ,       a    4  ,       a    8   and       a          1024      First computing       a    2   as   a  ⋅  a, which involves one multiplication.Next compute       a    4   as       a    2    ⋅      a    2  , which involves one multiplication.Next compute       a    8   as       a    4    ⋅      a    4  , which involves one multiplication.and all the way upto       a          1024      So far, it has involved   10 multiplications. Finally, put together       a    2    ⋅      a    4    ⋅      a    8    ⋅      a          1024      , which involves   4 multiplications. Hence, we only need a total of   14 multiplications.

klasyvea · Accepted Answer

You can use the binomial theorem as follows  (  a  +  b  +  c      )    n    =  (  (  a  +  b  )  +  c      )    n    =  ∑                              (                            n        i                              )                      (  a  +  b      )    i        c          n      −      i        =      ∑    i    n                                (                            n        i                              )                          c          n      −      i            ∑    j    i                                (                            i        j                              )                          a    j        b          i      −      j      In practice however, repeated squaring is the way to go.

Is there a simple algorithm for exponentiating large numbers to large powers?

Answered question

Answer & Explanation

New Questions in Algebra II