#27: Function Exponentiation

Tagged as challenge

Written on 2018-01-30

Part 1

Given any $f:X\to X$ and any non-negative integer $n$, define the function

​ $$\mathtt{fexpt}(f, n) := \underbrace{f\circ \cdots \circ f}_{n\text{ times}}.$$

Implement fexpt without mutation (i.e., without imperative loops or set!).

Extra Credit: Try to optimize the runtime of the functions resulting from fexpt.

Part 2

The Babylonian method for computing square roots of positive numbers is as follows. To compute $\sqrt{X}$, start with an arbitrary positive number $x_0$. Define $x_n$ by the following recursive sequence:

​ $$x_{n+1} = \frac{1}{2}\left(x_n + \frac{x_n}{X}\right).$$

Then it can be proved that $\lim_{n\to\infty} x_n = \sqrt{X}$, and the sequence converges quadratically (the number of correct digits doubles with each iteration).

Implement this using fexpt.

• ← Previous
• Next →