Suppose we want a method that computes the value of an integer raised to an inte
ID: 3584435 • Letter: S
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; } }