Assignment 3: Approximating the square root
1 Background
In the first two assignments you have developed algorithms for Charles-related problems, using control-structures to coordinate the function-units that have been developed in a top down or bottom up way. Starting with this assignment, we create console input / output based applications.
2. Learning objectives
After doing this assignment you are able to:
create and use void-functions that have parameters;
work with standard elementary data types, viz. bool, int, double, char, string;
work with console based input (cin, >>) and output (cout, <<);
create and compile such an
Preparing your project
In Code::Blocks, select “Create a new project”. Select “Console application” and press the “Go” button. In the language selection, choose “C++” and press the “Next >” button. In “Project title:” enter an appropriate name for your project, e.g. “assignment3” (if you choose this name, then Code::Blocks creates a project file named “assignment3.cbp” in the directory of your choice). Click the “Next >” button. For Charles-related projects you were advised not to activate the ‘Create “Debug” configuration:’ check box and select only the ‘Create “Release” configuration’ check box. However, for console input / output based applications, this is not an issue (with the “Debug” version, you can step-wise execute your application to see what is going on and inspect values of variables and so on). Click the “Finish” button to create the project. In the “Management” panel of Code::Blocks you can see that a “main.cpp” file has been created. This is the file that you edit and upload to Brightspace.
3. Assignment
Computing the square root of a number is usually a built-in function in most programming languages. C(++) is no exception, and uses sqrt for this purpose. In this assignment you implement two methods yourself that approximate the square root Öv of a given positive floating point value v (a double). You use only the basic arithmetic operations +, -, *, /, abs, comparison operations <, <=, ==, >, >=, and control structures. Both methods work with a sequence of approximations x0, x1, ... xn (n ³ 0), with the intention that eventually xn is sufficiently close to Öv. The halting-criterion is the desired precision with which the value should be approximated. Traditionally, the precision, which is denoted by e is a very small, positive value (0 < e << 1). In sum, we are looking for an xn such that:
| xn · xn – v | ≤ e.
This value (xn) can be computed by two algorithms (see part 1.2 and part 1.3). Part 1.1: Desktop test cases
The algorithms are already given in this assignment. To check your understanding of the algorithms,
you should do a desktop test of the following values for v (set e to 0.1):
v = 0,
v = 1,
some v for which 0 < v < 1,
some v > 1 for which there is a natural number n > 0 such that n n = v, and
some 10 < v < 100 that does not have the previous property. Include the results of these desktop tests as comment in cpp.
Part 1.2: Inclusion
Design and implement the function inclusion (double e, double v) that approximates Öv through a sequence of pairs of values (a0, b0), (a1, b1),…, (ai, bi) having the property:
ai · ai ≤ v and bi · bi ³ v
The value of a0 is 0. The value of b0 is the maximum of v and 1. If a0 happens to be the square root of v (a0·a0 = v), then you’re done (and a0 is the result). If b0 happens to be the square root of v (b0·b0 = v), then you’re done (and b0 is the result). In these cases, print the message: Inclusion square root of v is followed by the value of the variable carrying the result; and terminate the function with a return statement.
Otherwise, you iterate over i. In iteration i, the average of the values ai and bi is xi = (ai + bi) / 2. If xi satisfies the halting-criterion (| xi·xi – v | ≤ e), then you’re done (and xi is the result). Otherwise, you continue with:
(ai+1,bi+1) = (xi,bi) if xi · xi < v
= (ai,xi) otherwise
When you found a solution for xi, print the message: Inclusion square root of v is xi for epsilon e.
Part 1.3: Newton-Raphson
The classic Newton-Raphson algorithm (published by Isaac Newton at the end of the 17th century) computes the zero-value of a given function f using a sequence of approximations (it computes a value xn, such that f (xn) » 0). It works as follows: if xi is an approximation of the desired zero-value, then you can compute a better approximation xi+1 with:
xi+1 = xi – f(xi) / f’(xi), where f’ is the derivate function of f.
The algorithm can be used to compute the square root of a value v by choosing f(x) = x2 – v. The derivate function of f is f’(x) = 2x.
Design and implement the algorithm by the function newton_raphson (double e, double v). The value of x0 is the maximum of v and 1. The final value xn satisfies the property | xn·xn – v | ≤ e in the same way as in part 1.2.
Finally, the function prints the message: Newton_raphson square root of v is xn for epsilon e.
Part 1.4: Comparing the algorithms
Compare the effectiveness of the inclusion and newton_raphson implementations. Do this by counting how many approximations x0, x1, ... xn are generated by both algorithms when applied to each desktop test case that you have developed in part 1.1. Add your results in comment in “main.cpp”.
The output of the algorithm must be extended as follows: on each line of output, the values of i, ai, xi, bi are shown in the case of inclusion and the values of i, xi in the case of newton_raphson, where each value is separated with a ‘tab’-character
CS 340 Milestone One Guidelines and Rubric Overview: For this assignment, you will implement the fundamental operations of create, read, update,
Retail Transaction Programming Project Project Requirements: Develop a program to emulate a purchase transaction at a retail store. This
7COM1028 Secure Systems Programming Referral Coursework: Secure
Create a GUI program that:Accepts the following from a user:Item NameItem QuantityItem PriceAllows the user to create a file to store the sales receip
CS 340 Final Project Guidelines and Rubric Overview The final project will encompass developing a web service using a software stack and impleme
