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:

    “Every age develops its own peculiar forms of pathology, which express in exaggerated form its underlying character structure.”
    —Christopher Lasch (b. 1932)

    “True, there are architects so called in this country, and I have heard of one at least possessed with the idea of making architectural ornaments have a core of truth, a necessity, and hence a beauty, as if it were a revelation to him. All very well perhaps from his point of view, but only a little better than the common dilettantism.”
    —Henry David Thoreau (1817–1862)