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)

    “I have no patience with this dreadful idea that whatever you have in you has to come out, that you can’t suppress true talent. People can be destroyed; they can be bent, distorted, and completely crippled.”
    —Katherine Anne Porter (1890–1980)