Question

How does the number of multiplications used by the algorithm in Exercise 26 compare to the number of multiplications used by Algorithm 2 to evaluate ${\mathbf{a}}^{\mathbf{n}}$a?

Short answer

There are multiplications in exercise 2, and O(log n) multiplications in exercise 26.

Step-by-step solution

Describe the algorithm 2

The Algorithm 2 is a Recursive Algorithm for Computing .${\mathbf{a}}^{\mathbf{n}}$

procedure power (a : nonzero real number, n : nonnegative integer)

if n = 0 then return 1

else n = 0 then a. power (a, n - 1)

$\mathbf{\{}\mathbf{output}\mathbf{}\mathbf{is}\mathbf{}{\mathbf{a}}^{\mathbf{n}}\mathbf{\}}$

Compare the number of multiplications used by the algorithm in Exercise 26 and multiplications used by Algorithm 2

As per Algorithm 2, there will be n multiplications by , one for each factor of in the product$a^n$ .

As per algorithm in Exercise 26, there will be O(log n) multiplications as it computes squares. Apart from squaring, sometimes a multiplication by is needed, which will add at most another O(log n) multiplications. Thus, in totality O (log n) multiplications are used.

Hence, there are multiplications in exercise 2, O(log n) and multiplications in exercise 26.