In the first two assignments you have developed algorithms for Charles-related problems, using control-structures to coordinate the function-units

INSTRUCTIONS TO CANDIDATES

ANSWER ALL QUESTIONS

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

Attachments:

Related Questions

. Introgramming & Unix Fall 2018, CRN 44882, Oakland University Homework Assignment 6 - Using Arrays and Functions in C

DescriptionIn this final assignment, the students will demonstrate their ability to apply two ma

. The standard path finding involves finding the (shortest) path from an origin to a destination, typically on a map. This is an

Path finding involves finding a path from A to B. Typically we want the path to have certain properties,such as being the shortest or to avoid going t

. Develop a program to emulate a purchase transaction at a retail store. This program will have two classes, a LineItem class and a Transaction class. The LineItem class will represent an individual

Develop a program to emulate a purchase transaction at a retail store. Thisprogram will have two classes, a LineItem class and a Transaction class. Th

. SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 1 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of

. Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of Sea Ports. Here are the classes and their instance variables we wish to define:

1 Project 2 Introduction - the SeaPort Project series For this set of projects for the course, we wish to simulate some of the aspects of a number of