Newton's method, due to Isaac Newton (1642-1726) is a procedure to find zero-crossings of a function f. The procedure needs an initial guess for x, which is uses iteratively to find a new x such that f(x)=0. Because of numerical imprecision and floating point errors, the procedure might not terminate with f(x)=0, so many implementations of the procedure stop after a limited number of iterations or when the absolute value of f(x) is smaller than some small value epsilon.

Part of Newton's method needs to use the derivative of f; a common use of Newton's method is to find roots of a polynomial because the derivative is easy to compute exactly.

Here is the Double types:

import kotlin.math.absoluteValue // EPSILON is how "close" two numbers need to be // to be considered approximately equal for the Newton // algorithm; LIMIT is a maximum number of iterations // of the Newton algorithm before it gives up val EPSILON = 1.0e-10 val LIMIT = 50 // LimitError is a custom Java error just for Newton class LimitError: Error() /*************************************************************************** * The Newton-Raphson (see https://en.wikipedia.org/wiki/Newton%27s_method) * * algorithm searches for the root of a function f(x), where "root" means a * * value for x such that f(x)=0. Here, we only consider polynomial f(x) * * Example: f(x) = (3x-2)*(-4x+3) = -12x^2 + 17x - 6 * * has coefficients [-12, 17, -6] and the roots are 2/3 and 3/4 * * The solve() method of the Newton class has two inputs, an array for * * the coefficients and an initial "guess" for a root's value; solve() * * will either return a root or throw a LimitError. * ***************************************************************************/ class Newton { // solve() needs the polynomial coefficients and an initial guess  // for the value of a root of the polynomial; try different guess  // values to discover different roots of the polynomial  fun solve(coef: Array, guess: Double): Double { // func() evaluates and returns the polynomial for  // a given input value; it is a local function to Newton  fun func(p: Array, value: Double): Double { var result: Double = 0.0 var powerd: Double = 1.0 for (c in p.reversedArray()) { result += c * powerd powerd *= value } // println("coef=${p.toList()},guess=$guess,result=$result")  return result } // deriv() evaluates the first derivative of the input  // polynomial at a given input value  fun deriv(p: Array, value: Double): Double { val prime = Array(p.size - 1, { i -> (p.size - 1 - i).toDouble() * p[i] }) return func(prime, value) } var x = guess var t = func(coef, x) / deriv(coef, x) var loopcount = 0 while (t.absoluteValue >= EPSILON) { // println("x=$x func(x)=${func(coef,x)}")  t = func(coef, x) / deriv(coef, x) x = x - t loopcount++ if (loopcount > LIMIT) throw LimitError() } return x } } fun main(args: Array) { // for deugging, run main and test Newton().solve()  val coef = arrayOf(1.0,0.0,-9.0) val T = Newton().solve(coef,1.5) println(T) // should print 3.0  }

The homework asks you to take the working procedure for Double types and replace all uses of Double with a new type, Complex, that you define. Here are some things to know about the Complex type.

Each instance of Complex has two properties, real and imaginary (each is a Double value)

The traditional mathematical notation for a complex number is a+bi, where a is the real part an b is the imaginary part, and i is the square root of -1 (most tutorials use this notation to explain operations)

Operations of plus, minus, times, and div are defined for complex numbers:

(a+bi) + (c+di) = (a+c) + (b+d)i

(a+bi) - (c+di) = (a-c) + (b-d)i

(a+bi) * (c+di) = (ac-bd) + (ad+bc)i

The reciprocal of a complex number (a+bi) is

1/(a+bi) = (a/s) - (b/s)i where s = a*a + b*b

To do division of two complex numbers t and w, simply calculate t*(1/w)

All of the basic operations plus, minus, times and div should be infix functions (methods) of the Complex class.

In addition, Complex also needs an absoluteValue property. The absolute value of (a+bi) is defined as sqrt(a*a + b*b)

Code in Kotlin

Complete the following code to pass the Test code

import kotlin.math.absoluteValue val EPSILON = 1.0e-10 val LIMIT = 50 class LimitError: Error() // documentation is found in the newton project (this is newtoncomplex) // the solve() method is the same as in newton, except that the new // Complex type of number is used instead of Double class NewtonComplex { fun solve(coef: Array, guess: Complex): Complex { fun func(p: Array, value: Complex): Complex { var result: Complex = Complex(0.0,0.0) var powerd: Complex = Complex(1.0,0.0) for (c in p.reversedArray()) { result += c * powerd powerd *= value } // println("coef=${p.toList()},guess=$guess,result=$result")  return result } fun deriv(p: Array, value: Complex): Complex { val prime = Array(p.size - 1, { i -> Complex((p.size - 1 - i).toDouble(),0.0) * Complex(p[i].real,p[i].imaginary) }) return func(prime, value) } var x = guess var t = func(coef, x) / deriv(coef, x) var loopcount = 0 while (t.absoluteValue >= EPSILON) { // println("x=$x func(x)=${func(coef,x)}")  t = func(coef, x) / deriv(coef, x) // println("** $t ** ${t.absoluteValue}")  x = x - t loopcount++ if (loopcount > LIMIT) throw LimitError() } return x } } fun main(args: Array) { // debugging test, just for equation x^2 + 1 = 0, ie x^2 = -1  val coef = arrayOf( Complex(1.0,0.0), Complex(0.0,0.0), Complex(1.0,0.0)) val soln = NewtonComplex().solve(coef,Complex(2.0,2.0)) println("Root = $soln") // should be 0.0+1.0i approximately  }

Test Code:

import org.junit.Assert.* import org.junit.Test class NewtonComplexTest { @Test fun test1() { // test of x^2 + 9 = 0  val solver = NewtonComplex() val coef = arrayOf( Complex(1.0,0.0), Complex(0.0,0.0), Complex(9.0,0.0)) var soln = solver.solve(coef,Complex(2.0,0.01)) var dist = (soln - Complex(0.0,3.0)).absoluteValue  assertTrue( dist <= EPSILON ) // test that 3i is the solution  } @Test fun test2() { // test of x^2 + (1-i)x + (2-2i) = 0  val solver = NewtonComplex() var coef = arrayOf( Complex(1.0,0.0), Complex(1.0,-1.0), Complex(2.0,-2.0)) var soln = solver.solve(coef,Complex(1.0,1.0)) // println(soln)  var dist = (soln - Complex(0.0,2.0)).absoluteValue  assertTrue( dist <= EPSILON) // 0+2i is one root  soln = solver.solve(coef,Complex(2.0,-3.0)) // println(soln)  dist = (soln - Complex(-1.0,-1.0)).absoluteValue  assertTrue( dist <= EPSILON ) // -1-1i is another root  } }