Tagged as challenge

Written on 2018-01-30

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`

.

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`

.