Declare a function cubic that can be used together with the newtons_method function in expressions of the form

newtons_method(cubic(a, b, c), 1)

to approximate zeros of the cubic $x^3 +ax^2 +bx +c$.

function cubic(a, b, c) {
    return x => cube(x) + a * square(x) + b * x + c;
}

Declare a function double that takes a function of one argument as argument and returns a function that applies the original function twice. For example, if inc is a function that adds 1 to its argument, then double(inc) should be a function that adds 2. What value is returned by

double(double(double))(inc)(5);

function double(f) {
    return x => f(f(x));
}

Let $f$ and $g$ be two one-argument functions. The composition $f$ after $g$ is defined to be the function $x\mapsto f(g(x))$. Declare a function compose that implements composition. For example, if inc is a function that adds 1 to its argument,

compose(square, inc)(6);

49

returns 49.

function compose(f, g) {
    return x => f(g(x));
}

If $f$ is a numerical function and $n$ is a positive integer, then we can form the $n$th repeated application of $f$, which is defined to be the function whose value at $x$ is $f(f(\ldots(f(x))\ldots))$. For example, if $f$ is the function $x \mapsto x+1$, then the $n$th repeated application of $f$ is the function $x \mapsto x+n$. If $f$ is the operation of squaring a number, then the $n$th repeated application of $f$ is the function that raises its argument to the $2^n$th power. Write a function that takes as inputs a function that computes $f$ and a positive integer $n$ and returns the function that computes the $n$th repeated application of $f$. Your function should be able to be used as follows:

repeated(square, 2)(5);

625

Hint: You may find it convenient to use compose from exercise 1.42.

function repeated(f, n) {
    return n === 0
           ? x => x
           : compose(f, repeated(f, n - 1));
}

The idea of smoothing a function is an important concept in signal processing. If $f$ is a function and $dx$ is some small number, then the smoothed version of $f$ is the function whose value at a point $x$ is the average of $f(x-dx)$, $f(x)$, and $f(x+dx)$. Write a function smooth that takes as input a function that computes $f$ and returns a function that computes the smoothed $f$. It is sometimes valuable to repeatedly smooth a function (that is, smooth the smoothed function, and so on) to obtained the $n$-fold smoothed function. Show how to generate the $n$-fold smoothed function of any given function using smooth and repeated from exercise 1.43.

const dx = 0.00001;
function smooth(f) {
    return x => (f(x - dx) + f(x) + f(x + dx)) / 3;
}
function n_fold_smooth(f, n) {
    return repeated(smooth, n)(f);
}

We saw in section 1.3.3 that attempting to compute square roots by naively finding a fixed point of $y\mapsto x/y$ does not converge, and that this can be fixed by average damping. The same method works for finding cube roots as fixed points of the average-damped $y\mapsto x/y^2$. Unfortunately, the process does not work for fourth roots—a single average damp is not enough to make a fixed-point search for $y\mapsto x/y^3$ converge. On the other hand, if we average-damp twice (i.e., use the average damp of the average damp of $y\mapsto x/y^3$) the fixed-point search does converge. Do some experiments to determine how many average damps are required to compute $n$th roots as a fixed-point search based upon repeated average damping of $y\mapsto x/y^{n-1}$. Use this to implement a simple function for computing $n$th roots using fixed_point, average_damp, and the repeated function of exercise 1.43. Assume that any arithmetic operations you need are available as primitives.

function nth_root(n, x) {
    return fixed_point(repeated(average_damp, 
                                math_floor(math_log2(n)))
                       (y => x / fast_expt(y, n - 1)),
                       1);
}

Several of the numerical methods described in this chapter are instances of an extremely general computational strategy known as iterative improvement. Iterative improvement says that, to compute something, we start with an initial guess for the answer, test if the guess is good enough, and otherwise improve the guess and continue the process using the improved guess as the new guess. Write a function iterative_improve that takes two functions as arguments: a method for telling whether a guess is good enough and a method for improving a guess. The function iterative_improve should return as its value a function that takes a guess as argument and keeps improving the guess until it is good enough. Rewrite the sqrt function of section 1.1.7 and the fixed_point function of section 1.3.3 in terms of iterative_improve.

function iterative_improve(is_good_enough, improve) {
    function iterate(guess) {
        return is_good_enough(guess)
               ? guess
               : iterate(improve(guess));
    }
    return iterate;
}