As the question , i dont understand why we need some algorithm like exponential by squaring or modular exponentiation for calculating the power of a number.
For example, i have a repeated multiplication algorithm like this :
def expt_mul(a, n):
r = 1
for i in xrange(n):
r *= a
return r
a multiplied by itself n times , so the complexitiy is O(n), why it's not efficient?
Some algorithms require raising numbers to very large powers. Algorithms from cryptography in particular come to mind, such as the Diffie-Hellman key exchange.
While your algorithm might be fine for most everyday tasks, when you're dealing with exponents that are very large, it becomes unfeasible to use, so exponentiation by squaring is used instead.
why we need some algorithm like exponential by squaring or modular exponentiation for calculating the power of a number.
Note that exponentiation by squaring does not achieve the same thing as modular exponentiation. The first is an efficient algorithm to raise an entity to a certain integer power, while the latter is a method to compute an expression of the form (a^b) modulo c, where the algorithm used for exponentiation is not particularly relevant.