COMPSCI 1JC3 Introduction to Computational Thinking Fall 2020
Assignment 1
Dr. William M. Farmer and Curtis D’Alves McMaster University
Revised: October 1, 2020
The purpose of Assignment 1 is to write a program in Haskell that com- putes approximations to trigonometric functions (i.e., cos, sin, and tan). The requirements for Assignment 1 and for an extra credit assignment, Assign- ment 1 Extra Credit, are given below. You are required to do Assignment 1, but Assignment 1 Extra Credit is optional. Please submit Assignment 1 as a single Assign 1.hs file to the Assignment 1 folder on Avenue under Assessments / Assignments. If you choose to do Assignment 1 Extra Credit for extra marks, please submit it also as a single Assign 1 ExtraCredit.hs file to the Assignment 1 Extra Credit folder on Avenue in the same place. Both Assignment 1 and Assignment 1 Extra Credit are due Sunday, Oc- tober 11, 2020 before midnight. Assignment 1 is worth 6% of your final grade, while Assignment 1 Extra Credit is worth a maximum of 2 extra percentage points.
Late submissions will not be accepted! So it is suggested that you submit a preliminary Assign 1.hs file well before the deadline so that your mark is not zero if, e.g., your computer fails at 11:50 PM on the due date.
Although you are allowed to receive help from the instructional staff and other students, your submitted program must be your own work. Copying will be treated as academic dishonesty!
1 Background
The Taylor series of a function f : R → R provides a method of approxi- mating the value of a function at x using methods from calculus. A Taylor series is constructed at some chosen point a, and requires knowledge of the value of the function and its derivatives at this point. Formally, the Taylor series of f at the point a is:
∞ f(k)(a)(x − a)k (1)
k! k=0
Note: f(k)(a) denotes the kth derivative of f(a) with f(0)(a) = f(a), and k! denotes the factorial of k, i.e., k! = 1 ∗ 2 ∗ · · · ∗ (k − 1) ∗ k.
1
For most common functions, we have the following equality for x near a:
f(x) = ∞ f(k)(a)(x − a)k (2)
k! k=0
As you can see, a Taylor series is an infinite summation. So for common functions, we can approximate f(x) by the nth Taylor polynomial:
f(x) ≈ n f(k)(a)(x − a)k (3)
k! k=0
We can increase the accuracy of the approximation of f(x) by either increas- ing n (the number of iterations) or choosing a point a closer to x.
For example, the trig function cos has the following derivatives at a:
f(0)(a) = cos(a) f(1)(a) = −sin(a) f(2)(a) = −cos(a) f(3)(a) = sin(a) f(4)(a) = cos(a)
Notice that the fourth derivative is equal to the zeroth derivative (the orig- inal function), so all the other derivatives are repetitions of the first four. Therefore, we obtain the following equation:
cos(x) = cos(a) (x − a)0 0!
+ −sin(a)(x−a)1 1!
+ − cos(a) (x − a)2 (4) 2!
+ sin(a) (x − a)3 3!
+ cos(a) (x − a)4 4!
+···
where the right-hand side is the Taylor series for cos at a. When a = 0, this
simplifies nicely to:
∞ (−1)k x2k
(2k)!
(5)
cos(x) =
k=0
2
Finally, let mod : R → R → R be the modulus function (i.e., remainder of a division) for two real numbers. For example:
mod(3.1, 1.5) = 0.1 mod(4π, 2π) = 0.0
3π π mod 2,π =2
1.1 Aside
Feeling worried because you don’t know what a Taylor series is and why they can be used to approximate functions? Don’t Worry! As computer scientists, we often work with other disciplines, be it math, physics, biology, etc., and rely on explanations from experts in those fields. Accept the knowledge you’ve been given and apply the skills you have. You’ve been given a formula for approximating cos. You know what formulas are, how to interpret them, instantiate their variables, and code them up in Haskell. Don’t be scared by something you haven’t seen before. You have all you need to complete this assignment.
2 Assignment 1
The purpose of this assignment is to compute approximations for the trig functions cos, sin, and tan. Do so by carefully following these requirements:
2.1 Requirements
1. Download from Avenue Assign1 Project Template.zip which con- tains the Stack project files for this assignment. Modify the Assign 1.hs in the src folder so that the following requirements are satisfied.
2. Your name, the date, and “Assignment 1” are in comments at the top of your file. macid is defined to be your MacID. Note: Your MacID is not your student number. Your student number is a number, while your MacID is what you use use to sign into systems like Avenue and Mosaic.
3. The file includes a function cosTaylor of type Double -> Double -> Double -> Double -> Double that takes the values a, cos(a), sin(a) and x as input and computes the 4th Taylor polynomial approximation of cos(x) at a (i.e., Equation 4 with 5 iterations on the right-hand side).
4. ThefileincludesafunctionfmodoftypeDouble -> Double -> Double that computes mod.
3
5. The file includes a function cosApprox of type Double -> Double that computes an approximation of cos(x) using cosTaylor with appropri- ate values for a, cos(a), sin(a), and y as specified by the following table:
Value of x
Inputs for cosTaylor
a
cos(a)
sin(a)
y
0 ≤ mod(|x|, 2π) < π 4
π ≤ mod(|x|, 2π) < 3π 44
3π ≤ mod(|x|, 2π) < 5π 44
5π ≤ mod(|x|, 2π) < 7π 44
7π ≤mod(|x|,2π)<2π 4
0
π
2
π
3π 2 2π
1
0 −1 0 1
0 1 0
−1 0
mod(|x|, 2π) mod(|x|, 2π) mod(|x|, 2π) mod(|x|, 2π) mod(|x|, 2π)
6. The file includes a function sinApprox of type Double -> Double that uses cosApprox and the fact that
π sin(x)=−cos x+ 2
to approximate the value of sin(x).
7. The file includes a function tanApprox of type Double -> Double that
uses cosApprox, sinApprox, and the fact that tan(x) = sin(x)
cos(x)
to approximate the value of tan(x).
8. Your file loads successfully into GHCi and all of your functions perform correctly.
2.2 Testing
You should test on your own all of the functions in the file you submit. We recommend that you compare your cosApprox, sinApprox, and tanApprox function to the cos, sin, tan functions provide by Prelude. cosApprox should be fairly close to cos for all values of x, but there will an additional error due to using floating point arithmetic. You will be required to submit formal test plans for all subsequent assignments, but not for this assignment.
3 Assignment 1 Extra Credit
The purpose of this extra credit assignment is to compute approximations of trig functions to within a given tolerance. This is a very challenging assignment; do not be discouraged if you cannot complete it.
4
3.1 Requirements
1. Add the Extra Credit functions to the Assign 1 ExtraCredit.hs file in the src folder (not Assign 1.hs). Modify this file so that the following requirements are satisfied.
2. Your name, the date, and “Assignment 1 Extra Credit” are in com- ments at the top of your file. macid is defined to be your MacID.
3. The file includes a function cosApprox of type Double -> Double -> Double that takes a value x and a tolerance t and returns an approxi- mation of cos(x) with a relative error within tolerance t. (You may use the built-in Haskell cos function to find the relative error). The func- tion can result in a stack overflow if the tolerance is adjusted above the limits of floating point arithmetic.
4. The file includes a function sinApprox of type Double -> Double -> Double that takes a value x and a tolerance t and returns an approxi- mation of sin(x) with a relative error within tolerance t. (You may use the built-in Haskell cos function to find relative error). The function can result in a stack overflow if the tolerance is adjusted above the limits of floating point arithmetic
5. The file includes the same function tanApprox of type Double -> Double -> Double that takes a value x and a tolerance t and returns an approximation of tan(x) with a relative error within tolerance t. (You may use the built-in Haskell cos function to find relative error). The function can result in a stack overflow if the tolerance is adjusted above the limits of floating point arithmetic
6. Your file successfully loads into GHCi and all of your functions perform correctly.
3.2 Testing
Test on your own all of the functions in the file you submit. You will be required to submit formal test plans for all subsequent assignments.
5