(I need help programming this code. If you can do it in Scala, that would be great. If not, Python works too. Thank you.)

Suppose we wanted to find the root for an equation : $ f(x) = 0$,

The bisection method starts with two bounds $\ell < u$ where $f(\ell), f(u)$ have opposite signs. I.e, either - (A) ()<0 and ()>0 or - (B) ()>0 and ()<0.

At each iteration, it computes =(+)/2 and checks the sign of (). Depending on the sign of () it updates , by setting: = if (), () have the same signs or $u = m$ if = if (), () have the same signs.

The method terminates under the following conditions:

- |()| where is a given tolerance (typically 10^{10} ). In this case, is the root and we declare success. - || but () > . In this case, we return but declare failure. Here is a version of the bisection method implemented using a while loop for your convenience.

Note: ??? indicates that there is a missing function or code fragment that needs to be filled in. In scala, it is also a macro that throws a NotImplemented exception. Make sure that you remove the ??? and replace it with the answer.

###CODE

def bisectWhileLoop(f: Double => Double, l0: Double, u0: Double, epsilon: Double=1E-10): (Double, Boolean) = { var l = l0 var u = u0 require ( u - l >= epsilon) require ( (f(l) < 0.0 && f(u) > 0.0 ) || (f(l) > 0.0 && f(u) < 0.0)) /* Note: we may have as well just said assert(f(l) * f(u) < 0.0) */ var m = (l + u)/2.0 while (math.abs(f (m)) > epsilon && (u - l) > epsilon) { if ( f(m) * f(l) > 0) { /* Does l, m have same sign */ l = m } else { assert(f(m) * f(u) > 0) /* u, m must have the same sign */ u = m } m = (l + u)/2 } if (math.abs(f (m)) <= epsilon){ (m, true) /* good enough to count as a solution to f(x) = 0 */ } else { (m, false) /* Not good enough for the given tolerance. */ } }

Results:

defined function bisectWhileLoop

// Let's compute sqrt(2) val f: Double => Double = x => (x*x - 2) val l0 = 1.0 val u0 = 2.0 val (res, success) = bisectWhileLoop(f, l0, u0)

Results:

f: Double => Double = ammonite.$sess.cmd5$Helper$$Lambda$2032/0x0000000100ac9040@367d857 l0: Double = 1.0 u0: Double = 2.0 res: Double = 1.4142135623842478 success: Boolean = true

// Let's compute cube-root(5) val f: Double => Double = x => (x*x*x - 5) val l0 = 1.0 val u0 = 2.0 val (res, success) = bisectWhileLoop(f, l0, u0)

Results:

f: Double => Double = ammonite.$sess.cmd6$Helper$$Lambda$2061/0x0000000100ad8840@7e2d995a l0: Double = 1.0 u0: Double = 2.0 res: Double = 1.7099759466655087 success: Boolean = true

//Solve the equation sin(x) - cos(x) = 0 val f: Double => Double = x => math.sin(x) - math.cos(x) val l0 = 0.5 val u0 = 1.3 val (res, success) = bisectWhileLoop(f, l0, u0,1E-15) println(s"Estimated value of pi: ${4*res}")

Results:

Estimated value of pi: 3.141592653589794 

f: Double => Double = ammonite.$sess.cmd7$Helper$$Lambda$2073/0x0000000100adf840@42f131f l0: Double = 0.5 u0: Double = 1.3 res: Double = 0.7853981633974485 success: Boolean = true

###INSTRUCTION

Implement a tail recursive version of bisection called `bisectTail` that inputs - Function `f: Double => Double` - limits `l: Double`, `u: Double` - tolerance `epsilon:Double` that defaults to `1E-10`. It must return `(Double, Boolean)` where the first component is the approximate root and the second component of the tuple signals success/failure. - Your function must be tail recursive. - Avoid the use of `var` and loops in your code. - Do not use any API functions outside of those used in the while loop solution above such as `math.abs`.

###CODE

import scala.annotation.tailrec @tailrec // YOUR CODE HERE ???

//BEGIN TEST

// Let's compute sqrt(2) val f: Double => Double = x => (x*x - 2) val l0 = 1.0 val u0 = 2.0 val (res, success) = bisectTail(f, l0, u0,1E-10) assert (success && math.abs(res - 1.4142135) <= 1E-6) passed(3)

//END TEST

//BEGIN TEST

// Let's compute sqrt(5) val f: Double => Double = x => (x*x - 5) val l0 = 2.0 val u0 = 2.5 val (res, success) = bisectTail(f, l0, u0,1E-10) assert(success && math.abs(res - 2.236067977) <= 1E-08) passed(2)

//END TEST

//BEGIN TEST

//Solve the equation sin(x) - cos(x) = 0 val f: Double => Double = x => math.sin(x) - math.cos(x) val l0 = 0.5 val u0 = 1.3 val (res, success) = bisectWhileLoop(f, l0, u0,1E-15) println(s"Estimated value of pi: ${4*res}") assert(success && math.abs(res - 0.78539816) <= 1E-07) passed(2)

//END TEST

//BEGIN TEST

//Solve the equation sin(x) - cos(x) = 0.5 val f: Double => Double = x => math.sin(x) - math.cos(x) - 0.5 val l0 = 1.0 val u0 = 1.5 val (res, success) = bisectTail(f, l0, u0,1E-15) assert(success && math.abs(math.sin(res) - math.cos(res) -0.5) <= 1E-09) passed(3)

//END TEST