Newton's Method (also know as the Newton-Raphson method, named after Isaac Newton and Joseph Raphson) is an algorithm for finding the root of a nonlinear function, that is, given f(x), this algorithm can find C such that f(C) = 0. Suppose we have a function that is twice continuously differentiable on some interval [a,b]. Twice continuously differentiable means that the first and second derivatives exist and they are continuous (their graphs are smooth and have no breaks). Given an initial approximation to the root, in the interval [a,b], Newton's method finds successive approximations to the root. It is derived from the Taylor series expansion for f(x).

The input to Newton's method is an initial approximation to the root C, the maximum number of iterations to perform, and the error tolerance. Each iteration produces a closer approximation C. The algorithm stops iterating when it exceeds the maximum number of iterations (failure to find an acceptable solution) or when the difference between successive solutions is less than the error tolerance (success!).

We will use Newton's method to calculate square roots. If x = sqrt(num), then x² = num, or x² - num = 0. Thus to find sqrt(2), for example, we solve x² - 2 = 0. Your program should prompt for numbers and calculate square roots until the user enters a negative number.

Input

1. p₀, the initial approximation to the root (use num)
2. the maximum number of iterations to perform
3. error tolerance

Algorithm

Print a line which will be the heading for your ouput, so it should look like:

i p(i) 

Set i = 1, set p_last = p₀ then create a while loop to repeat the following steps:

1. p_i = p_last - f(p_last)/f^'(p_last)
2. Print i and p_i. Print them on one line separated by blanks, and print a newline after p_i. Line them up under your heading.
3. i++
4. p_last = p_i

When to stop looping:

• Stop if the number of iterations exceeds the maximum. Print a message saying that the method failed, and include the number of iterations in the message.
• Stop if | p_i - p_last | < tolerance. Print a message saying that the root is p_i.

Put the input and the algorithm inside a loop, so that you can calculate multiple square roots. Terminate the program when the user enters a negative value for num.

The Function

Use Newton's method to find a root of the function x² - num = 0 to within 10^-5. Use num for p₀ and set the maximum number of iterations to 30.

Evaluating x² - num

Create a "function" to evaluate f(p_last). Use the jal instruction to branch to your function and use the jr instruction to branch back. The jal instruction branches to the label given as the operand, and also loads register $ra with the address of the statement following the jal

. The jr instruction branches to the address contained in the register given as the operand. So the jal instruction branches to the given label, and the jr branches back to the statement following the jal, just as we expect from a called function.

Your "parameter" to the function is the register that contains p_last. The "return value" of the function is the register that contains f(p_last). For example, the "call" looks like:

 jal calcf # get the value of f at plast

and the "called function" looks like:

calcf: ... ... ... jr $ra # return

Do the same to evaluate f'(p_last).

Hints

• There is no way to tell the syscall how many places to print after the decimal point. I understand if this bothers you, but you have to live with it.
• Just like with integers, you will enter them as base 10 numbers (including a decimal point if necessary), and they will be output as base 10 numbers. The syscall does the work of converting between floating point and the characters we enter and see on our screen.
• Remember your comments should reflect the purpose of the statements. Write comments like "p(last) = p(i)" not comments like "$f7 = $f4".
• Don't be stubborn and wait to put in your comments till the end. You will drive yourself crazy. It's very important to comment your register usage.

Written in MIPS Assembly