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)

    “We must conclude that it is not only a particular political ideology that has failed, but the idea that men and women could ever define themselves in terms that exclude their spiritual needs.”
    —Salman Rushdie (b. 1948)