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 log₂n squarings and at most log₂n 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:

“Mothers seem to be in subtle competition with teachers. There is always an underlying fear that teachers will do a better job than they have done with their child.... But mostly mothers feel that their areas of competence are very much similar to those of the teacher. In fact they feel they know their child better than anyone else and that the teacher doesn’t possess any special field of authority or expertise.”
—Sara Lawrence Lightfoot (20th century)

“A major misunderstanding of child rearing has been the idea that meeting a child’s needs is an end in itself, for the purpose of the child’s mental health. Mothers have not understood that this is but one step in social development, the goal of which is to help a child begin to consider others. As a result, they often have not considered their children but have instead allowed their children’s reality to take precedence, out of a fear of damaging them emotionally.”
—Elaine Heffner (20th century)