Exponentiation By Squaring - Underlying Idea

Underlying Idea

Using the following observation, one can create a recursive algorithm that computes xn for an integer n using squaring and multiplication:

x^n= \begin{cases} 1, & \mbox{if } n = 0 \\ \frac{1}{x^{-n}}, & \mbox{if } n < 0 \\ x \cdot \left( x^{\frac{n - 1}{2}} \right)^2, & \mbox{if } n \mbox{ is odd} \\ \left( x^{\frac{n}{2}} \right)^2, & \mbox{if } n \mbox{ is even} \end{cases}

A brief analysis shows that such an algorithm uses log2n squarings and at most log2n multiplications. For n > about 4 this is computationally more efficient than naïvely multiplying the base with itself repeatedly.

Read more about this topic:  Exponentiation By Squaring

Famous quotes containing the words underlying and/or idea:

    “If the worker and his boss enjoy the same television program and visit the same resort places, if the typist is as attractively made up as the daughter of her employer, if the Negro owns a Cadillac, if they all read the same newspaper, then this assimilation indicates not the disappearance of classes, but the extent to which the needs and satisfactions that serve the preservation of the Establishment are shared by the underlying population.”
    —Herbert Marcuse (1898–1979)

    “See, in the Navy, during the war, I got used to the idea that something might happen to me, I might not make it. Well, I also got used to the idea that my wife and children were safe at home, they’d be all right no matter what. But what I didn’t reckon with was that in this, this kind of a monstrous war, something might happen to them, and not to me. Well it did, and I can’t, I can’t cope with it.”
    —John Paxton (1911–1985)