Urban Hafner

CTM: Exercise 3-3

Posted by Urban Hafner Sun, 11 Sep 2005 17:34:45 GMT

The problem

The half-interval method. The half-interval method is a simple but powerful technique for finding roots of the equation f(x) = 0, where f_ is a continuous real function. The idea is that, if we are given real numbers _a and b_ such that f(a) < 0 < f(b), then _f must have a least one root between a_ and _b. To locate a root, let x = (a + b)/2 and compute f(x). If f(x) > 0, then f_ must have a root between _a and x_. If f(x) < 0 then _f must have a root between x_ and _b. Repeating this process will define smaller and smaller intervals that converge on a root. Write a declarative program to solve this problem using the techniques of iterative computation.

My solution

  local
     fun {GoodEnough A B} {Abs A-B} < 0.00001 end
  in
     fun {HalfInterval A B F}
        Mean=(A+B)/2.0 in
        if {GoodEnough A B} then
         Mean
        elseif {F Mean} > 0.0 then
         {HalfInterval A Mean F}
        else
         {HalfInterval Mean B F}
        end
     end
  end