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:

    “The “female culture” has shifted more rapidly than the “male culture”; the image of the go-get ‘em woman has yet to be fully matched by the image of the let’s take-care-of-the-kids- together man. More important, over the last thirty years, men’s underlying feelings about taking responsibility at home have changed much less than women’s feelings have changed about forging some kind of identity at work.”
    —Arlie Hochschild (20th century)

    “Once, when lying in bed with no paper at hand, he began to sketch the idea for a new machine on the back of his wife’s nightgown. He asked her if she knew the figure he was drawing. “Yes,” she answered, “the figure of a fool.””
    —For the State of New Jersey, U.S. public relief program (1935-1943)