# Interval halving (Bisection) method in Scala

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.

## (1) The interval-halving (bisection) method, Java style

Without any further introduction, here is the source code for the Interval Halving method, written in Scala, but in a Java 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)
{
var x3 = (x1wkg + x2wkg)/2.0
if (signsAreOpposite(fx(x3), fx(x1wkg)))
x2wkg = x3
else
x1wkg = x3
}
return 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) return true
else if (x > 0 && y < 0) return true
else return false
}

}
```

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 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)

}

/**
* 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)
{
var x3 = (x1wkg + x2wkg)/2.0
if (signsAreOpposite(fx(x3), fx(x1wkg)))
x2wkg = x3
else
x1wkg = x3
}
return x1wkg
}

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

}
```

Scala and other functional programmers will probably tell me that I should make the halveTheInterval function even more Scala-like by making it recursive, but I prefer the approach shown here. If anyone wants to write that function recursively and leave it in the Comments section below, feel free to do so.