## Description

1 Introduction

Let us change our traditional attitude to the construction of programs.

Instead of imagining that our main task is to instruct a computer what

to do, let us concentrate rather on explaining to human beings what

we want a computer to do.

—Donald Knuth

As we know, computers are simple machines that carry out a sequence of very simple steps, albeit very

quickly. Unless you have a special-purpose processor, a computer can only compute addition, subtraction,

multiplication, and division. If you think about it, you will see that the functions that might interest you

when dealing with real or complex numbers can be built up from those four operations. We use many of

these functions in nearly every program that we write, so we ought to understand how they are created.

If you recall from your Calculus class, with some conditions a function f(x) can be represented by its

Taylor series expansion near some point f(a):

f(x) = f(a)+∑∞

k=1

f

(k)

(a)

k!

(x−a)

k

.

Note: when you see Σ, you should generally think of a for loop.

If you have forgotten (or never taken) Calculus, do not despair. Attend a laboratory section for review:

the concepts required for this assignment are just derivatives.

Since we cannot compute an infinite series, we must be content to calculate a finite number of terms. In

general, the more terms that we compute, the more accurate our approximation. For example, if we expand

to 10 terms we get:

f(x) = f(a)+ f

(1)

(a)

1!

(x−a)

1 +

f

(2)

(a)

2!

(x−a)

2 +

f

(3)

(a)

3!

(x−a)

3 +

f

(4)

(a)

4!

(x−a)

4

+

f

(5)

(a)

5!

(x−a)

5 +

f

(6)

(a)

6!

(x−a)

6 +

f

(7)

(a)

7!

(x−a)

7 +

f

(8)

(a)

8!

(x−a)

8

+

f

(9)

(a)

9!

(x−a)

9 +O((x−a)

10).

© 2021 Darrell Long 1

Note: k! = k(k−1)(k−2)×…×1, and by definition, 0! = 1.

Taylor series, named after Brook Taylor, requires that we pick a point a where we will center the approximation. In the case a = 0, then it is called a Maclaurin series). Often we choose 0, but the closer to the

value of x the better we will approximate the function. For example, let’s consider e

x

centered around 0:

e

x =

∑∞

k=0

x

k

k!

= 1+

x

1

1!

+

x

2

2!

+

x

3

3!

+

x

4

4!

+

x

5

5!

+

x

6

6!

+

x

7

7!

+

x

8

8!

+

x

9

9!

+…

This is one of the simplest series when centered at 0, since e

0 = 1. Consider the general case:

e

x = e

a +

e

a

1!

(x−a)

1 +

e

a

2!

(x−a)

2 +

e

a

3!

(x−a)

3 +

e

a

4!

(x−a)

4 +

e

a

5!

(x−a)

5

+

e

a

6!

(x−a)

6 +

e

a

7!

(x−a)

7 +

e

a

8!

(x−a)

8 +

e

a

9!

(x−a)

9 +

e

a

10!

(x−a)

10 +O((x−a)

11).

Since d

dx e

x = e

x

the exponential function does not drop out as it does for a = 0, leaving us with the

original problem. If we knew e

a

for a ≈ x then we could use a small number of terms. However, we do not

know it and so we must use a = 0.

What is the O((x−a)

11) term? That is the error term that is “on the order of” the value in parentheses.

This is different from the big-O that we will discuss with regard to algorithm analysis.

2 Your Task

Programming is one of the most difficult branches of applied

mathematics; the poorer mathematicians had better remain pure

mathematicians.

—Edsger Dijkstra

For this assignment, you will be creating a small numerical library and a corresponding test harness. Our

goal is for you to have some idea of what must be done to implement functions that you use all the time.

You will be writing and implementing sin−1

(arcsin), cos−1

(arccos),tan−1

(arctan), and log functions.

For arcsin, arccos, and arctan you can choose to use a Taylor series approximation or the inverse method.

You will use Newton’s method to approximate log. You will then compare your implemented functions to

the corresponding implementations in the standard library <math.h> with a test harness and output the

results into a table similar to what is shown in Figures 1 and 2.

$ ./mathlib-test -s | head -n 5

x arcSin Library Difference

– —— ——- ———-

-1.0000 -1.57079633 -1.57079633 -0.0000000000

-0.9000 -1.11976951 -1.11976951 0.0000000000

-0.8000 -0.92729522 -0.92729522 -0.0000000000

Figure 1: First five lines of program output for arcsin.

© 2021 Darrell Long 2

$ ./mathlib-test -c | head -n 5

x arcCos Library Difference

– —— ——- ———-

-1.0000 3.14159265 3.14159265 -0.0000000000

-0.9000 2.69056584 2.69056584 0.0000000000

-0.8000 2.49809154 2.49809154 -0.0000000000

Figure 2: First five lines of program output for arccos.

From left to right, the columns represent the input parameter, your program’s arcsin/arccos value for

the input parameter, the library’s value for the input parameter and lastly, the difference between your value

and the library’s value.

You will test arcsin and arccos in the range [−1,1) with steps of 0.1, while arctan and log will be tested

in the range [1,10) with steps of 0.1.

Each implementation will be a separate function. You must name the functions arcSin(), arcCos(),

arcTan(), and Log(). Since the <math.h> library uses asin, acos, atan, and log, you will not be able

to use the same names. You may use the sin() and cos() functions from <math.h>. You may not use

any other functions from <math.h> in any of your functions. You may only use them in your printf()

functions. However, you should use constants such as M_PI from <math.h>. Do not define π yourself.

2.1 Sin−1 and Cos−1

The domain of sin−1

and cos−1

is [−1,1], and so centering them around 0 makes sense. The Taylor series

for arcsin(x) centered about 0 is:

arcsin(x) =∑∞

k=0

(2k)!

2

2k(k!)2

x

2k+1

2k+1

, |x| ≤ 1.

If we expand a few terms, then we get:

arcsin(x) = x+(

1

2

)

x

3

3

+(

1×3

2×4

)

x

5

5

+(

1×3×5

2×4×6

)

x

7

7

+O(x

9

).

The series for arccos(x) centered about 0 is:

arccos(x) = π

2

−

∑∞

k=0

(2k)!

2

2k(k!)2

x

2k+1

2k+1

.

So you can implement it as,

arccos(x) = π

2

−arcsin(x).

You can implement the Taylor series expansion or the inverse method when writing the functions for arcsin

and arccos.

© 2021 Darrell Long 3

2.2 Tan−1

The Taylor series expansion for arctan is also complex and is as follows:

arctan(x) =∑∞

k=0

2

2k(k!)2

(2k+1)!

x

2k+1

(1+x

2)

k+1

.

To make things simpler, you can also calculate arctan using the arcsin or arccos functions

arctan(x) = arcsin(

x

√

x

2 +1

) = arccos(

1

√

x

2 +1

), x > 0.

You can implement the Taylor series expansion or the inverse method when writing arctan.

2.3 e

x

Fortunately, we have a nice series for e

x

and it happens to converge very quickly. In Figure 3, we use our

expansion to 10 terms and plot for e

0

,…,e10. We see that the approximation starts to diverge significantly

around x = 7. What this tells us is that 10 terms are insufficient for an accurate approximation, and more

terms are needed.

2 4 6 8 10

x

2000

4000

6000

8000

ex

Taylor Approximation Figure 3: Comparing e

x with its Taylor approximation centered at zero.

If we are naïve about computing the terms of the series we can quickly get into trouble — the values of

k! get large very quickly. We can do better if we observe that:

x

k

k!

=

x

k−1

(k−1)! ×

x

k

.

At first, that looks like a recursive definition (and in fact, you could write it that way, but it would be

wasteful). As we progress through the computation, assume that we know the previous result. We then just

have to compute the next term and multiply it by the previous term. At each step we just need to compute

© 2021 Darrell Long 4

2 4 6 8 10

5

10

15

20

25

Figure 4: Comparing

x

k

k!

for x = 2,3,4,5.

x

k

, starting with k = 0! (remember 0! = 1) and multiply it by the previous value and add it into the total. It

turns into a simple for or while loop.

Conceptually, what you need to think about is:

1 new = previous * current;

2 previous = current;

We can use an ϵ (epsilon) to halt the computation since |x

k

| < k! for a sufficiently large k. Consider

Figure 4: briefly, x

k dominates but is quickly overwhelmed by k! and so the ratio rapidly approaches zero.

You should set ϵ = 10−10 for this assignment.

For this assignment, the Exp(x) function is provided to you and you must use it in order to write your

Log function.

2.4 Log

To compute log, you will use Newton’s method, also called the Newton-Raphson method, by computing the

inverse of e

x

. It is an iterative algorithm to approximate roots of real-valued functions, i.e., solving f(x) = 0.

Each iteration of Newton’s method produces successively better approximations.

xk+1 = xk −

f(xk)

f

′(xk)

Your function Log() should behave the same as log() from <math.h>: compute ln(x). Here we are

© 2021 Darrell Long 5

finding the root of f(x) = y−e

x

. Since e

x

is the inverse of ln, i.e. ln(e

y

) = x. This gives us:

xk+1 = xk +

y−e

xk

e

xk

.

Each guess xk+1 gives a successive improvement over the previous guess xk. The function begins with

an initial guess x0 = 1.0 that it uses to compute better approximations. Log() is sufficiently calculated

once the value converges, i.e. the difference between consecutive approximations is sufficiently small. This

occurs when when e

xi −y is small.

In order to implement this function, you will have to use the given Exp() function. Using the exp()

and pow() functions from <math.h> is strictly prohibited.

3 Command-line Options

GUIs tend to impose a large overhead on every single piece of software, even the smallest,

and this overhead completely changes the programming environment. Small utility

programs are no longer worth writing. Their functions, instead, tend to get swallowed up

into omnibus software packages.

—Neal Stephenson, In the Beginning…Was the Command Line

Your test harness will determine which implemented functions to run through the use of commandline options. In most C programs, the main() function has two parameters: int argc and char **argv.

A command, such as ./hello arg1 arg2, is split into an array of strings referred to as arguments. The

parameter argv is this array of strings. The parameter argc serves as the argument counter, the value in

which is the number of arguments supplied. Try this code, and make sure that you understand it:

Trying out command-line arguments.

1 #include <stdio.h>

2

3 int main(int argc , char **argv) {

4 for (int i = 0; i < argc; i += 1) {

5 printf(“argv[%d] = %s\n”, i, argv[i]);

6 }

7 return 0;

8 }

A command-line option is an argument, usually prefixed with a hyphen, that modifies the behavior

of a command or program. They are typically parsed using the getopt() function. Do not attempt to

parse the command-line arguments yourself. Instead, use the getopt() function. Command-line options

must be defined in order for getopt() to parse them. These options are defined in a string, where each

character in the string corresponds to an option character that can be specified on the on the commandline. Upon running the executable, getopt() scans through the command-line arguments, checking for

option characters.

© 2021 Darrell Long 6

Parsing options with getopt().

1 #include <stdio.h>

2 #include <unistd.h> // For getopt().

3

4 #define OPTIONS “pi:”

5

6 int main(int argc , char **argv) {

7 int opt = 0;

8 while ((opt = getopt(argc , argv , OPTIONS)) != -1) {

9 switch (opt) {

10 case ‘p’:

11 printf(“-p option.\n”);

12 break;

13 case ‘i’:

14 printf(“-i option: %s is parameter.\n”, optarg);

15 break;

16 }

17 }

18 return 0;

19 }

This example program supports two command-line options, ‘p’ and ‘i’. Note that the option character

‘i’ in the defined option string OPTIONS has a colon following it. The colon signifies that, when the ‘i’

option is enabled on the command-line using ‘-i’, getopt() is looking for an parameter to be supplied

following it. An error is thrown by getopt() if an argument for a flag requiring one is not supplied.

4 Deliverables

Thinking doesn’t guarantee that we won’t make mistakes. But not

thinking guarantees that we will.

—Leslie Lamport

You will need to turn in:

1. mathlib.h: You will be supplied this file and you are not allowed to modify it. The function prototypes for the math functions you are required to implement are as follows:

• double arcSin(double x);

• double arcCos(double x);

• double arcTan(double x);

• double Log(double x);

© 2021 Darrell Long 7

2. mathlib.c: This file will contain your math function implementations, as prototyped in mathlib.h.

Your functions must not print or have any side effects.

3. mathlib-test.c: This file will contain the main() program and acts as a test harness for your math

library. The code to parse command-line options and print out the results of testing your math functions belong here. The getopt() options that you must support are:

• -a: to run all tests.

• -s: to run arcsin tests.

• -c: to run arccos tests.

• -t: to run arctan tests.

• -l: to run log tests.

Note that these options are not mutually exclusive. You should be able to support any combination

of these options. Each function is tested at most once. Specifying all tests to be run and a specific

test does not result in that test running twice (e.g. ./mathlib-test -a -s). The output for each

function must match the format shown in Figures 1 and 2. Your compiled program must be called

mathlib-test. To aid you with the print formatting, the print statement is given as follows:

1 printf(” %7.4lf % 16.8lf % 16.8lf % 16.10lf\n”, …);

The spaces in the print format statement are intentional and account for negative (but not positive)

signs.

4. Makefile: This is a file that will allow the grader to type make to compile your program. Running

make or make all must build your mathlib-test program. Running make clean must remove

any compiler-generated files.

5. README.md: This must be in Markdown. This must describe how to build and run your program and

list the command-line options it accepts and what they do.

6. DESIGN.pdf: This must be in PDF. The design document should contain answers to the pre-lab

questions. It should also describe the purpose of your program and communicate the overall design

of the program with enough detail such that a sufficiently knowledgeable programmer would be able

to replicate your implementation. This does not mean copying your entire program in verbatim.

You should instead describe how your program works with supporting pseudocode. C code is not

considered pseudocode. You must push DESIGN.pdf before you push any code.

7. WRITEUP.pdf: This must be in PDF. WRITEUP.pdf should contain a discussion of the results for your

tests. This means analyzing the differences in the output of your implementations versus those in the

<math.h> library. Include possible reasons for the differences between your implementation and the

standard library’s.

Graphs can be especially useful in showing the differences and backing up your arguments. In this

document, graphs were effectively used to show the divergence of the Taylor series approximation

© 2021 Darrell Long 8

for e

x

as seen in Figure 3. A visual representation of data makes it easier to get your point across. For

this assignment, a plot can be used to show how close your approximation is to the value returned by

the library function. An example script for using gnuplot to create your graphs has been provided

to you in the Resources repository. gnuplot is a command-line graphing utility that allows you to

visualize data easily and with a few commands you can make your writeup very pretty!

5 Submission

A man who procrastinates in his choosing will inevitably have his

choice made for him by circumstance.

—Hunter S. Thompson, The Proud Highway: Saga of a Desperate

Southern Gentleman, 1955–1967

To submit your assignment, refer back to asgn0 for the steps on how to submit your assignment through

git. Remember: add, commit, and push!

Your assignment is turned in only after you have pushed. If you forget to push, you have not turned in

your assignment and you will get a zero. “I forgot to push” is not a valid excuse. It is highly recommended

to commit and push your changes often.

6 Supplemental Readings

• The C Programming Language by Kernighan & Ritchie

– Chapter 3 §3.4-3.7

– Chapter 4 §4.1 & 4.2 & 4.5

– Chapter 7 §7.2

– Appendix B §B4

• The Kollected Kode Vicious by George V. Neville-Neil

– Chapter 2 §2.6

© 2021 Darrell Long 9

C ņ ĲोÀाƒमग करना एक बƫदर को Öनसॉ ċī जƢसा ž।

© 2021 Darrell Long 10