2. [12 marks] The binary method of exponentiation computes an for any positive i

Question

2. [12 marks] The binary method of exponentiation computes an for any positive integer n using the fact that a"- (a/2)2 if n is even, and a"-a a-1 if n is odd (a) [6 marks] Give the pseudocode for a recursive algorithm computing a" where n is a positive integer, using the above idea. Do NOT use memoization. In your solution, when n is even, there should be only one (explicit) recursive call among your pseudocode for this case. For this sub-question, no explanation, justification, or analysis is required; simply give your pseudoc ode. (b) [6 marks] Find out the exact total number of multiplications performed when using your algorithm to compute an for any positive integer n. Use the substitution method, i.e., make a guess and then prove its correctness by induction. Hint: It may be helpful to consider the number of 1-digits in the base-2 expression of n. Let s2(n) be this value. You can use s2(n) as one of the additive terms in your solution

Explanation / Answer

#include <stdio.h>

int power(int a,int n)
{
if (n==1)
{
return a;
}
else if (n==0)
{
return 1;
}
else
{
if (n%2==0)
{
int b;
b=power(a,n/2);
return b*b;
}
else
{
return a*power(a,n-1);
}
}
}

int main()
{
printf("%d",power(2,5));
return 0;
}

If the value of n is in the base expression of 2 in that case the complexity will be O(log n).

Related Questions

Navigate

• Browse (All)
• Browse 2
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.