A task: The construction of the power

The simple construction of the power N – is N – 1 multiplications per cycle. A multiplication – it is expensive, trudoёmkaya operation…

The wording of this task, such:

  • write a function exponentiation X ** N, but, that was required for this minimum the number of multiplications);
  • try to control and to include in the output number which were needed for the calculation of the multiplication.

P.S. logic of such a decision is not mine, and the famous guru Charles Anthony Hoare (Charles Anthony Richard Hoare), I just wrote down his decision code:

And here are some sample performance, what should happen:

with the solution of the problem, involution, logic Hoara, Hoare, the practice of programming in C ++

Newsletter of programming:

A task: The construction of the power
Rate this article

About Olej

practical experience about software development 40 years. Teacher Global Logic international software company. IBM Developer Works Permanent author of publications. Scientific editor of the computer literature publishing house "Symbol-Plus", St. Petersburg.

2 thoughts on “A task: The construction of the power

  1. This example again shows the power of recursion as a method of calculation. Try to write this algorithm in an iterative technique (cycles) … and even better – then explain to someone how this algorithm works recorded.
    love recursion!

Leave a Reply

Your email address will not be published. Required fields are marked *