Exercise 1: Approximating π

Write a C program that approximates π using the Nilakantha series.

Your program takes a single non-negative integer n as a command-line argument, specifying how many terms of the series to include in the estimate. The count is inclusive of term. For example, n = 3 sums terms 0, 1, 2, and 3.

Your program should print the resulting estimate of π to 20 decimal places.

The Nilakantha series is an alternating series that can be used to calculate the value of π. It was published in the 15th century by a mathematician named Nilakantha Samayaji. It starts with a leading term of 3 (term 0) and then adds successively smaller correction terms (terms 1, 2, 3, …):

\[ \pi = 3 + \frac{4}{2 \cdot 3 \cdot 4} - \frac{4}{4 \cdot 5 \cdot 6} + \frac{4}{6 \cdot 7 \cdot 8} - \cdots \]

Each correction term has a numerator of 4 and a denominator that multiplies three consecutive integers starting at an even number (2·3·4, then 4·5·6, then 6·7·8, …), and the signs alternate. So term n (for n ≥ 1) is \((-1)^{n+1} \cdot \tfrac{4}{2n \cdot (2n+1) \cdot (2n+2)}\), which lets us write the whole series compactly as:

\[ \pi = 3 + \sum_{n=1}^{\infty} (-1)^{n+1} \cdot \frac{4}{2n \cdot (2n+1) \cdot (2n+2)} \]

The Nilakantha series isn't the most famous series for estimating π. That honor usually goes to the Leibniz series, named after Gottfried Leibniz, who discovered the series in the 1670s. However, as the mathematics community began to globalize, people realized that the Leibniz series had also been discovered nearly three centuries earlier by an Indian mathematician Madhava of Sangamagrama, founder of the Kerala school of mathematics. It is sometimes referred to as the Madhava-Leibniz series.

Nilakantha belonged to that same Kerala school, and his contribution was improving on the convergence speed. The Leibniz series (sometimes called the Madhava-Leibniz series) is considered elegant, but extremely slow. To approximate π to ten decimal places, it takes nearly 5 billion terms. Nilakantha's series takes some clever shortcuts and reaches the same ten decimals in roughly 1,700 terms.

While testing, you should compile your program into an executable called ex1.

$ gcc -Wall -g -std=c17 -o ex1 ex1.c
$ ls
ex1     ex1.c

Here ex1.c is your program and ex1 is your executable.

Here are some examples that display how your program should behave. Your output should match these exactly:

$ ./ex1 1
Our estimate of Pi is 3.16666666666666651864
$ ./ex1 10
Our estimate of Pi is 3.14140671849650177094
$ ./ex1 100
Our estimate of Pi is 3.14159241097198238535

In addition, your program should handle unexpected inputs gracefully (i.e., without crashing). For each malformed input, you may choose how you want to respond and document the decision with a short comment in your code (one or two short sentences is fine). Please consider the following cases:

$ ./ex1
$ ./ex1 hello
$ ./ex1 -20
$ ./ex1 0.05432
$ ./ex1 10000000 3234

One case you can safely ignore is an integer that is too large to fit into an int (e.g., 2³³³ will not fit in 32 bits).

Standard Library

To convert the command-line argument from a digit-string to an int and print the result, you'll need a handful of standard C library functions. See www.cplusplus.com/reference (also linked from the C/C++ menu in the nav bar above) for documentation; ignore the C++ pages for now.

• In particular, you will find it useful to look at
  • (1) stdio.h for basic input and output,
  • (2) string.h for handling C-strings (i.e., null-terminated arrays of characters), and
  • (3) stdlib.h for some useful functions.
• There are many ways to parse strings into integer values, including sscanf, atoi, strtol, and others; think about the tradeoffs and differences between them.
• You are allowed to use any standard library function that does not require additional compilation options (see Submission details).
  • Notably, you may not use functions from the math.h library as it requires additional compilation options.

Arithmetic

To avoid floating-point arithmetic errors, please make sure your code adheres to the following rules:

1. Use C's double type for intermediate and final results.
2. Sum the series in order from term 0 to term n (and not the other way around).

Since this is the first exercise, we want you to get comfortable with the C best practices mentioned in the lecture.

Common Issues

Here are some common style issues to keep in mind:

• layout your program with proper function ordering
• indent your code consistently
• factor out code into helper functions (when appropriate)
• write an adequate amount of useful comments

---

User Input

As mentioned earlier in the spec, your program should handle user inputs in a robust way. If users enter unexpected or malformed input, your program should not crash. Instead, it should have prechecks that detect these inputs and display helpful information to the user.

There are multiple ways to handle these prechecks. If you make a design decision (i.e. choose one way over another way to handle something), then leave a comment above that code explaining why.

---

Tools

We recommend you run cpplint and valgrind periodically while developing. Resolve any indicated issues before submitting.

• A linter is a tool that analyzes your code to check for style or formatting errors. In this class, we use cpplint.py (included in your repo). When you have fixed all linter errors, you should see the following output:

  $ ./cpplint.py --clint ex1.c
  Done processing ex1.c
  

• For each choice of <input>, you should be looking to see the following line of output from valgrind:

  $ valgrind ./ex1 <input>
  ...
  ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
  

• For this exercise only: you may ignore the error "sscanf can be ok, but is slow and can overflow buffers".

To submit your assignment, you must:

1. Clone your exercise repo to a local machine
2. Commit your ex1.c submission
3. Push your changes to the remote repository. Verify that your changes show up on the Gitlab web interface.
4. Tag that commit with ex1-submit.

You can find more detailed instructions in our Git tutorial. Our course infrastructure will automatically copy your submissions to Gradescope. Once the TAs have given feedback on the exercise, scores will be published on Gradescope.

---

Requirements for Full Credit

For full credit, your code must:

• Compile without errors or warnings on CSE Linux machines (lab workstations, attu, or CSE home VM). We will compile your code with the command:

  $ gcc -Wall -g -std=c17 -o ex1 ex1.c

• Have no runtime errors, memory leaks, or memory errors (gcc and valgrind).
• Have a comment at the top of your .c file with your name(s) and CSE or UW email address(es).
• Be pretty: formatting, modularization, naming, and comments should follow the class style guidelines, and cpplint.py --clint should run clean.
• Be robust: handle edge cases and bogus user input gracefully.