Question
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
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 x2 = num, or x2 - num = 0. Thus to find sqrt(2), for example, we solve x2 - 2 = 0. Your program should prompt for numbers and calculate square roots until the user enters a negative number.
Input
- p0, the initial approximation to the root (use num)
- the maximum number of iterations to perform
- 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 plast = p0 then create a while loop to repeat the following steps:
- pi = plast - f(plast)/f'(plast)
- Print i and pi. Print them on one line separated by blanks, and print a newline after pi. Line them up under your heading.
- i++
- plast = pi
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 | pi - plast | < tolerance. Print a message saying that the root is pi.
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 x2 - num = 0 to within 10-5. Use num for p0 and set the maximum number of iterations to 30.
Evaluating x2 - num
Create a "function" to evaluate f(plast). 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 plast. The "return value" of the function is the register that contains f(plast). 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'(plast).
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
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started