The occasional appendices and optional examples in this module are for advanced material that you will not need for this module. They are intended for enthusiastic students who are interested in going further in programming for its own sake.

Extra example: the do() .. while loop

Comments and questions to John Rowe.

Extra example: successive halving

Successive halving is a useful algorithm for solving f(x) = y for a given y.

Suppose we can find two values, xmin and xmax such that:

1. f(xmin) < ytarget < f(xmax)
2. f(x) is continuous and monotonically increasing between xmin and xmax.

We now know there must be at least one solution in the range xmin to xmax.

We can reduce this range by considering a value of x somewhere between the two, for example x = (xmin + xmax)/2, and calculating the new value of f(x). If it is less than ytarget then we know the solution must be in the range x to xmax, if it is greater than ytarget then we know the solution must be in the range xmin to x.

We can turn this into the basis of an algorithm by saying that if we know the solution must be in the range x to xmax then x becomes the new xmin, if we know the solution must be in the range xmin to x then x becomes the new xmax.

This is a good candidate for the do() .. while loop as the loop always needs to be executed at once. Using a while() loop would require having an artificial measure to ensure the loop ran at least once.

#include <stdio.h>
#include <math.h>
/*
 * Demonstrate the use of successive halving to solve
 * atan(x) + exp(x) + fabs(log(x) = y
 */

int main() {
  double y, ytarget = 11.789474563, x, xmin=0, xmax=ytarget;
  
  printf("Diag: target is %g\n", ytarget);
  do  {
    x = (xmin + xmax)/2.0;
    y = atan(x) + exp(x) + fabs(log(x));

    printf("Diag: xmin = %g, xmax = %g, y = %g\n", xmin, xmax, y);

    if ( y < ytarget)
      xmin = x;
    else
      xmax = x;
  }  while ( fabs(y - ytarget) > 1e-6);

  printf("The solution is %g\n", x);
  return 0;
}

Step through this code

NB: this method is fairly slow, faster methods would involve estimating the dradiant of f(x) and hence the change required in x.