b) Efficient Power. Consider the power(x,n) function, with ? any number, and n a

Question

b) Efficient Power. Consider the power(x,n) function, with ? any number, and n a non-negative integer, that computes Since we love recursion we may consider this trivial implementation of power: def power_linear(x, n): return 1 return x * power-linear(x, n-1) The problem with this function is that it has a runtime proportional to n; we say its runtime complexity is linear in n and we write that as O(n). E.g. if n-31, this function does 31 multiplications, in 31 recursive calls. We quickly realize that we can make power work a lot faster by using a smarter divide-and-conquer approach. For example, if n = 28, we can compute power(, 28) as follows: To do for part b): * Write a new version of the power function that uses this second approach (in file p1.py). Write the contract for the function in its docstring: what it does and the preconditions. * Write a function called test_power that uses the testif module/function to test the power function for the base case and some other cases. Compare with ** the operator.

Explanation / Answer

def power(x, n): if n == 0: return 1 else: p = power(x, n//2) if n % 2 == 0: return p*p else: return p*p*x def test_power(): print(power(2, 5) == 2 ** 5) print(power(3, 10) == 3 ** 10) print(power(5, 2) == 5 ** 2) print(power(7, 9) == 7 ** 9) test_power()

Related Questions

Navigate

• Browse (All)
• Browse B
• Subjects

---

---

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