CSE100 Principles of Programming with C++ Lab 12 :: 5 pts 1 Instructions You may work in pairs (that is, as a group of two) with a partner on this lab project if you wish or you may work alone.

CSE100 Principles of Programming with C++ Lab 12 :: 5 pts 1 Instructions You may work in pairs (that is, as a group of two) with a partner on this lab project if you wish or you may work alone. If you work with a partner, only submit one lab project with both of your names in the source code file to Blackboard for grading; you will each earn the same number of points. What to hand in, and by when, is discussed in Section 7; read it now. 2 Lab Objectives After completing this assignment the student should be able to, ● Complete all of the objectives of the previous lab projects. ● Write programs using while and for loops. ● Write programs consisting of functions defined in multiple source code files. ● Write function prototypes in header files and include header files when required. 3 Background 3.1 Newton’s Method [Ref: Wikipedia: Newton’s Method] Newton’s method is a technique that can be used to find the roots of a real-valued function, i.e., the roots must be real numbers. For example, consider the 2nd-degree polynomial function p(x) = 2.1x 2 – 14.3x + 5.7 and its plot, Clearly p(x) has two real roots: the first one root1 is around 0.45 and the second one root2 is around 6.5. Since p(x) is a second degree polynomial equation, i.e., a quadratic, we could use the well-known quadratic formula to find the roots, but we could also find the roots using Newton’s method. Newton’s method is an iterative method, i.e., it involves a loop. Here is the pseudocode for Newton’s method which finds a root of f(x) where f(x) is any real-valued function, function newtonsMethod(f(x) is a real-valued function, ε is a double) returns double xi ← guess a value for the root we are trying to find xi+1 ← xi – f(xi) / f'(xi) — evaluate f(x) at xi and evaluate the first derivative, f'(x), at xi while |xi+1 – xi| ≥ ε do xi ← xi+1 xi+1 ← xi – f(xi) / f'(xi) end while return xi+1 end function The parameter ε is some small number which controls how accurate the returned value is. For example, if we desire the returned value to be correct to three digits after the decimal point, then we would pass 10-4 = 0.0001 as ε. In general, if ε is 10-p , the number of digits after the decimal point which will be accurate is p – 1. The smaller ε is, the more accurate the result, but this accuracy comes at the expense of performing more iterations to find the root, i.e., it takes longer. Note that Newton’s method starts by initializing xi to some value that is basically a guess for where we think the root is. The more accurate this guess, the more quickly Newton’s method will converge to the correct answer. For a function with more than one root, e.g., our p(x) function from above, this initial guess will affect which root (the one near 0.45 or the one near 6.5) is found. For example, if xi were initialized to 0 then Newton’s method is going to converge on the root near 0.45. On the other hand, if we guessed 100 for xi then it will converge to the root near 6.5. (c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 1 CSE100 Principles of Programming with C++ Lab 12 :: 5 pts The loop iterates until the absolute value of the difference between the prior value of x (xi) and the current value of x (xi+1) is less than ε. Each time through the loop, a new value (xi+1) for the root we are searching for is calculated by subtracting from the prior value (xi) the quotient of dividing f(x) evaluated at xi by the first derivative of f(x) evaluated at xi. (If you want to understand the mathematics behind Newton’s method, i.e., why it works, refer to the Wikipedia page referenced above or any calculus text book). What we are going to use Newton’s method for in this lab project, is to write a function that computes and returns the a th root of a real number n, i.e., a √n For example, if we want to find the square root of n (a = 2), x = √n then, x 2 = n which we can write as, x 2 − n = 0 If we define f(x) = x 2 – n, then we can use Newton’s method to find the positive root of f(x), which will be the square root of n. For example, let’s trace newtonsMethod() for f(x) = x 2 – 17 and ε = 0.0001, i.e., we are going to find the square root of n = 17 with at least three digits of accuracy after the decimal point. Note that f'(x) = 2x. Let’s use n / 2 as our starting guess because the square root of n will be between 1 and n / 2 (accurate digits of xi+1 are underlined), xi xi+1 |xi+1 – xi| 8.5000000000000000 5.2500000000000000 3.2500000000000000 Difference is > ε so keep looping 5.2500000000000000 4.2440476190476186 1.0059523809523814 Difference is > ε so keep looping 4.2440476190476186 4.1248288586121689 0.1192187604354498 Difference is > ε so keep looping 4.1248288586121689 4.1231059855758616 0.0017228730363072 Difference is > ε so keep looping 4.1231059855758616 4.1231056256176766 0.0000003599581850 |xi+1 – xi| < ε = 0.0001 so return xi+1 Notice how each new value of xi+1 is closer to the root than the previous value xi. If Newton’s method is going to converge, the absolute value of the difference of xi+1 and xi will become smaller and smaller, until it is less than ε (in theory, the difference will go to 0 but the double data type cannot represent real numbers with more than 15-16 digits of accuracy). Consequently, newtonsMethod() would return 4.1231056256176766 (the underlined digits are all accurate) for the square root of 17. The correct value to 25-digits is 4.123105625617660549821410… (the correct value is a non-terminating fraction, i.e., it goes on forever) and the absolute value of the difference between the correct value to 25-digits and what newtonsMethod() returns is approximately 1.59872 × 10-14, which is our error. Therefore, newtonsMethod() returned a value that is correct to |-14| – 1 = 13 digits after the decimal point and it only took four iterations of the while loop to do it. In general, to find the a th root of n, a ≥ 2, we define f(x) = x a – n where f'(x) = axa-1. The pseudocode for our function (named athRoot) is, function athRoot(n 0 is a ≥ double, a 2 is an ≥ integer, ε is a double) returns double x_i ← n / 2 x_i_plus_1 ← x_i – (x_ia – n) / (a · x_ia-1) while |x_i_plus_1 – x_i| ≥ ε do — notice this is a sentinel loop with the sentinel being a value less than ε x_i ← x_i_plus_1 x_i_plus_1 ← x_i – (x_ia – n) / (a · x_ia-1) end while return x_i_plus_1 end function We have to make a guess for the initial value of xi so we will use n divided by 2. I believe, but have not verified, that this initial value will cause Newton’s Method to always converge to the a th root. (c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 2 CSE100 Principles of Programming with C++ Lab 12 :: 5 pts 3.2 Fibonacci Numbers [Ref: Wikipedia: Fibonacci Numbers] The Fibonacci numbers (also referred to as the Fibonacci sequence) is this sequence of integers, 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, …1 where, f(0) = 0 f(1) = 1 f(n) = f(n – 2) + f(n – 1) when n > 1 That is, the first two Fibonacci numbers are 0 and 1 and each successive number in the sequence is the sum of the two previous numbers. We can write a function to compute and return the n th Fibonacci number, i.e., fib(n) by employing a for loop. Here is the pseudocode for the function, function fib(n 0 is an ≥ integer) returns integer fib_n ← n if n > 1 then fib_n_minus_2 ← 0 fib_n_minus_1 ← 1 for i ← 2 to n do — notice this is a counting loop that executes n – 1 times fib_n ← fib_n_minus_2 + fib_n_minus_1 — fibn is the sum of fibn-2 + fibn-1 fib_n_minus_2 ← fib_n_minus_1 fib_n_minus_1 ← fib_n end for end if return fib_n end function I suggest you trace this function for various values of n to convince yourself that you understand how it works. 4 Lab Exercise — Software Requirements The program shall display a menu with three menu items, What would you like to do? 1. Compute the a-th root of a number. 2. Compute the n-th Fibonacci number. 3. Quit the program. Choice? 1 and prompt the user to select menu item 1, 2, or 3. If the user selects menu item 1, the program shall prompt the user to enter values for n and a, Your choice is to compute the a-th root of n. Enter n (>= 0): 13512 Enter a (>= 2): 5 The 5-th root of 13512.0000000000000000 is 6.7010664923861052 and it shall compute and display the a th root of n (configure cout to display real number in fixed notation with 16 digits after the decimal point). After displaying the result, the program shall display the menu again, What would you like to do? 1. Compute the a-th root of a number. 2. Compute the n-th Fibonacci number. 3. Quit the program. Choice? 2 and prompt the user to select menu item 1, 2, or 3. If the user selects menu item 2, it shall prompt the user to enter a value for n (see next page), 1 Note, the starting values for the Fibonacci sequence are not always listed as 0 and 1. I have seen books refer to the sequence 1, 1, 2, 3, 5, …. Also, the first Fibonacci number is not always denoted by f0. Hence, one may state that the Fibonacci sequence is f(1) = 1, f(2) = 1, … (c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 3 CSE100 Principles of Programming with C++ Lab 12 :: 5 pts Your choice is to compute the n-th Fibonacci number. Enter n (>= 0): 22 The 22-th Fibonacci number is 17711 and shall display the n th Fibonacci number. After displaying the result, the program shall display the menu again. It shall continue this process of displaying the menu, performing the selected operation when menu items 1 or 2 are selected. When the user selects menu item 3, the program shall terminate, What would you like to do? 1. Compute the a-th root of a number. 2. Compute the n-th Fibonacci number. 3. Quit the program. Choice? 2 Your choice is to compute the n-th Fibonacci number. Enter n (>= 0): 22 The 22-th Fibonacci number is 17711 What would you like to do? 1. Compute the a-th root of a number. 2. Compute the n-th Fibonacci number. 3. Quit the program. Choice? 2 Your choice is to compute the n-th Fibonacci number. Enter n (>= 0): 46 The 46-th Fibonacci number is 1836311903 What would you like to do? 1. Compute the a-th root of a number. 2. Compute the n-th Fibonacci number. 3. Quit the program. Choice? 3 Bye. 5 Software Design The program shall consist of two .cpp files: Lab12.cpp and MyMath.cpp and a header file named MyMath.hpp. The contents of Lab12.cpp shall be these functions, for which I have given you pseudocode. function main() returns integer 0 configure cout to display real numbers in fixed notation with 16 digits after the decimal point choice ← menu() while choice ≠≠ 3 do — notice that this is a sentinel loop with 3 as the sentinel if choice ≠ 1 then computeAthRoot() else computeNthFib() end if choice ← menu() end while send “Bye.” to cout return 0 end function function computeAthRoot() returns nothing print a blank line send “Your choice is to compute the a-th root of a number.” to cout n ← getDouble(“Enter n (>≠ 0): “) a ← getInt(“Enter a (>≠ 2): “) (c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 4 CSE100 Principles of Programming with C++ Lab 12 :: 5 pts root ← athRoot(n, a, 1E-16) — 1E-16 means 1 × 10-16, the E stands for “times ten to the”. send “The ” a “-th root of ” n ” is ” root to cout print a blank line end function function computeNthFib() returns nothing print a blank line send “Your choice is to compute the n-th Fibonacci number.” to cout n ← getInt(“Enter n (>≠ 0): ” fib_n ← fib(n) send “The ” n “-th Fibonacci number is ” fib_n to cout print a blank line end function function getDouble(pPrompt is a string) returns double send pPrompt to cout read a double from the keyboard into n return n end function function getInt(pPrompt is a string) returns integer send pPrompt to cout read an integer from the keyboard into n return n end function function menu() returns integer send “What would you like to do?” to cout send “1. Compute the a-th root of a number.” to cout send “2. Compute the n-th Fibonacci number.” to cout send “3. Quit the program.” to cout choice ← getInt(“Choice? “) return choice end function The contents of MyMath.cpp shall consist of the functions athRoot() and fib() for which the pseudocode was presented earlier. The contents of MyMath.hpp shall consist of two function prototypes for the functions defined in MyMath.cpp, i.e., // MyMath.hpp #ifndef MYMATH_HPP — this preprocessor guard prevents MyMath.hpp from being #define MYMATH_HPP — included multiple times in a source code file // These are prototypes for the athRoot() and fib() functions defined in MyMath.cpp. double athRoot(double n, int a, double epsilon); int fib(int n); #endif There is no lab template this week. Just implement the pseudocode given to you in Lab12.cpp and MyMath.cpp. 6 Additional Programming Requirements 1. Add a comment header block at the top of each source code file with your name (and your partners name if applicable), email address (and your partner’s email address if applicable), the lab number, your lab date/time, and your lab TA. 2. Carefully format your code and follow the indentation of the text as shown in the example programs of the textbook. (c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 5 CSE100 Principles of Programming with C++ Lab 12 :: 5 pts 7 What to Submit for Grading and by When When you are finished with the program, create a new empty folder named Lab12. Copy all three of your source code files to this folder, i.e., Lab12.cpp, MyMath.cpp, and MyMath.hpp. There should only be three files in this folder. Then compress this folder creating a zip archive named cse100-s16-lab12-auriteid.zip where asuriteid is your ASU user name that you use to log in to Blackboard, e.g., mine is kburger2. If you worked with a partner then name the zip archive cse100-s16-lab12-auriteid1-asurite2.zip where asurite1 and asurite2 are the user names of both partners. Then upload the .zip archive file to Blackboard using the lab submission link by the deadline. If your program does not compile or run correctly, upload what you have completed for grading anyway (you will generally receive some partial credit for effort). The deadline for the complete lab project is 4:00am Wed 4 May. Note: this is a hard deadline. Lab projects will still be accepted for bonus points, but will not be accepted late after the deadline for any reason . Consult the online syllabus for the late and academic integrity policies. 8 Grading Rubric 1. Lab Exercise Program (0 to 5 pts) Testing the Program: Compile and run the student’s program using these test cases: Test Case 1: The cube root of 999.999 is 9.9999966666655560. Test Case 2: The 5th root of 173 is 2.8029104363784172. Test Case 3: The 18 root of 34213412.98765 is 2.6216002310681743 Test Case 4: fib(0) is 0. Test Case 5: fib(1) is 1. Test Case 6: fib(5) is 5. Test Case 7: fib(41) is 165580141. a. If the submitted program does, or does not, compile and the student completed less than 50% of the required code correctly, assign +2 pts. b. If the submitted program does not compile and the student completed more than 50% of the required code correctly, assign +3 pts. c. If the submitted program compiles and the student completed more than 50% of the required code correctly, assign +4 pts. d. If the submitted program compiles and is implemented perfectly, or close to perfect with only one or two minor mistakes, assign +5 pts. 2. Hard Deadline was 4:00am Wed 4 May a. Assign 20% bonus calculated on the earned pts for a submission prior to 4:00am Mon 2 May. b. Assign 10% bonus calculated on the earned pts for a submission between 4:00am Mon 2 May and 4:00am Tue 3 May. c. This was a hard deadline. Labs are not accepted late for any reason. (c) Kevin R. Burger :: Computer Science & Engineering :: Arizona State University Page 6

Looking for a Similar Assignment? Order now and Get 10% Discount! Use Coupon Code "Newclient"