Interval halving (Bisection) method in Scala (OOP and FP styles)

I just picked up an old college textbook named Applied Numerical Analysis, and curious to see what the Interval Halving method (also known as the Bisection Method) would look like in Scala, I decided to code it up. Considering that Scala is similar to the Java programming language, if anyone else needs the Interval-Halving method in Java, this code can easily be adapted to Java as well.

After writing the code first in what I’d call a “Java style,” I then modified the code to be a little more Scala-like. I’ll show the source code for both versions here.

Note: I wrote all of the following code a few years before I wrote the Scala Cookbook, and my coding standards at that time were all over the place. Please don’t think of the following code as “good code.” But if you’ll think of the following Scala code as “starter code” that kinda-sorta shows a solution, that would be kind.

The interval-halving (bisection) method, Java/OOP style

Without any further introduction, here is the source code for the Interval Halving method, written in Scala, but in a Java/OOP/imperative coding style:

package numerical_analysis

/**
 * This is the numerical analysis technique known as "Halving the interval",
 * which is also known as the "Bisection method".
 * 
 * In short, if you define a continuous function in the method below
 * named "fx", then provide two starting values (x1 and x2) in the "main"
 * method, the code will determine a root of the equation between x1 and x2,
 * assuming the function f(x) crosses the x-axis between those two points.
 * 
 * Note that the code could be written a little more concisely, but I
 * have left it longer to make it more readable.
 */
object IntervalHalvingBisectionMethod {

  def main(args: Array[String]) {
      val x1 = 1.0
      val x2 = 2.0
      val tolerance = 0.00005
      val result = halveTheInterval(x1, x2, tolerance)
      println(result)
  }
  
  /**
   * "fx" is the function we want to solve, i.e., it is f(x).
   * In this example, f(x) is the following cubic polynomial:
   *    f(x) = x^3 + x^2 - 3x - 3
   */
  def fx(x: Double): Double = {
      // this is another example f(x) equation that can be solved:
      //return Math.pow(Math.E, x) - 3*x
    
      // this is the current f(x) function we want the solution for
      return x*x*x + x*x - 3*x -3
  }

  /**
   * This is the "interval halving" (Bisection method) function.
   * Note: I use temporary working variables in this function because 
   * I'm treating x1 and x2 in the Scala way, i.e., to let them default to
   * being 'val', which is 'final' in Java.
   */
  def halveTheInterval(x1:Double, x2:Double, tolerance:Double): Double = {
      var x1wkg = x1
      var x2wkg = x2
      while (Math.abs(x1wkg-x2wkg) > tolerance) {
         val x3 = (x1wkg + x2wkg)/2.0
         if (signsAreOpposite(fx(x3), fx(x1wkg)))
            x2wkg = x3
         else
            x1wkg = x3
      }
      x1wkg
  }
  
  /**
   * Returns true if the signs of x and y are opposite
   * (one is negative, the other is positive), otherwise
   * it returns false. (I'm not sure what should happen when
   * one variable is zero, so it will return false in that 
   * situation.)
   */
  def signsAreOpposite(x: Double, y: Double):Boolean = {
      if (x < 0 && y > 0) true
      else if (x > 0 && y < 0) true
      else false
  }

}

I'll be glad to answer any questions I can about this source code, but all I really did was read the pseudocode from my numerical analysis book and code it up.

One thing I should add is that it would probably be helpful if I added a “debug” option to the code so you can see how it iterates through the potential solutions in the halveTheInterval function. Seeing the values of x1 and x2 as the problem is solved, along with the number of iterations that are required to solve the given f(x) equation would be helpful to understanding the process. (I already understand that process, so I didn't include the debug code here.)

The interval halving method written in a slightly more functional style

I intentionally made the interval-halving (bisection) method above look a little more like Java than Scala, in case anyone in the Java world needed some help. However, because Scala is a functional programming language, we can easily pass the f(x) function around as a function literal, rather than define it as a standalone function. This isn't the perfect solution in every case, but in this example, it's a nice way to show off what a "functional programming language" is.

Here's the same code, written in a slightly more functional Scala style:

package numerical_analysis

/**
 * A second version of my "Interval Halving" code, this time written in 
 * a more "functional" Scala style. In this example I define the desired
 * f(x) function literal in the main method, then pass that function around.
 */
object IntervalHalving2 {

  def main(args: Array[String]) {
    val x1 = 1.0
    val x2 = 2.0
    val tolerance = 0.00005

    // define the f(x) function here
    val fx = (x: Double) => x*x*x + x*x - 3*x -3
    
    // pass the f(x) function as a parameter to the new halveTheInterval function
    val answer = halveTheInterval(fx, x1, x2, tolerance)

    // print the answer
    println(answer)
  }

  /**
   * The new interval-halving function.
   * Note that the first argument to this function is now a function, and
   * that function expects a Double to be passed in, and returns a Double.
   */
  def halveTheInterval(fx: Double => Double, x1:Double, x2:Double, tolerance:Double): Double = {
    var x1wkg = x1
    var x2wkg = x2
    while (Math.abs(x1wkg-x2wkg) > tolerance)
    {
      val x3 = (x1wkg + x2wkg)/2.0
      if (signsAreOpposite(fx(x3), fx(x1wkg)))
        x2wkg = x3
      else
        x1wkg = x3
    }
    x1wkg
  }

  /**
   * The "signs are opposite" helper function.
   */
  def signsAreOpposite(x: Double, y: Double):Boolean = {
    if (x < 0 && y > 0) true
    else if (x > 0 && y < 0) true
    else false
  }

}

You can actually make the halveTheInterval function a completely-FP style algorithm, but I wanted to show this approach first.

The same 'halveTheInterval' function in a completely FP style

A completely-FP halveTheInterval algorithm looks like this:

@tailrec
def halveTheIntervalFP(f: Double => Double,
                       x: Double,
                       y: Double,
                       tolerance: Double): Double = {
    if (Math.abs(x - y) <= tolerance) {
        x
    } else {
        val nextGuess = (x + y) / 2.0
        if (signsAreOpposite(f(nextGuess), f(x)))
            halveTheIntervalFP(f, x, nextGuess, tolerance)
        else
            halveTheIntervalFP(f, nextGuess, y, tolerance)
    }
}

When I first started with functional programming I found this approach a little harder to read, but these days it seems more natural. The code says:

• If the absolute value of the difference between x and y is less than the tolerance, you have found the solution, so return x.
• Otherwise, generate the nextGuess, handle the situation where the signs may be opposite, and then halve the interval again.

With any recursive algorithm you always want to make sure that you know and handle the end situation — how the recursion ends — so I almost always put that condition first. In this case the recursion ends when the absolute value is less than the tolerance. Then I handle the algorithm as desired in the other case.

If there is a concern that the algorithm will never end — that in this case the tolerance will never be reached — just add a counter to limit the number of attempts to reach the tolerance. (This is no different than what you would do with a for or while loop in an imperative algorithm.)