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 welfare, the happiness, the energy and spirit of the men and women who do the daily work ... is the underlying necessity of all prosperity.... There can be nothing wholesome unless their life is wholesome; there can be no contentment unless they are contented.”
    —Woodrow Wilson (1856–1924)

    “At great periods you have always felt, deep within you, the temptation to commit suicide. You gave yourself to it; breached your own defenses. You were a child. The idea of suicide was a protest against life; by dying, you would escape this longing for death.”
    —Cesare Pavese (1908–1950)