Suppose we want a method that computes the value of an integer raised to an inte

Question

Suppose we want a method that computes the value of an integer raised to an integer power. Computing xn by repeated multiplication takes n - 1 multiplications. We can do better using the following fact. Let p(x, n) = xn. p(x, n) = Use this fact to write a recursive method that computes xn. It takes 99 multiplications to compute x100 using repeated multiplication. How many multiplications does your method perform for the same computation? What is the maximum number of multiplications performed by your method expressed as a simple formula involving the exponent n?

Explanation / Answer

int pow1(int x,int n) { if(n==0){ return 1; } else{ return x * pow1(x, n-1); } } int pow2(int x,int n) { if(n==0){ return 1; } else if(n&1){ int p = pow2(x, (n-1)/2) return x * p * p; } else { int p = pow2(x, n/2) return p * p; } }

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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