CPSC-298-6 Programming in C++

Programming Project Pi
CPSC-298-6 Programming in C++

Introduction
In this assignment, you'll use the Leibnitz formula to approximate the value of π (pi), the
ratio of the circumference to the diameter of a circle.
The Leibnitz formula for π,
is an alternating series:
The value of π is approximately
3.1415926535897932384626433832795028841971693993751058209749445923
Of course, the digits go on forever.
We can't carry out the expansion to infinity in C++ but we can approximate π using a
large value for the upper bound of k.
In the first part of the assignment, you'll write a program that uses a single for loop
implementing a truncated Leibnitz formula to approximate the value of pi using an upper
bound for k entered by the user.
In the second part of the assignment, you'll reuse your earlier code but encapsulate it in
an outer for loop that increases the upper bound of k and observe the computed value for
pi approach the actual value.
These programs appear deceptively simple and don't take long to write. However, there's
more to them than meets the eye.
(The Background section that follows is optional; you can skip to the assignment.
However, it may contain information that will save you time. It might, just might, be
interesting, too.)
2
Background
Pi in Sci Fi
Computer viruses, a form of malware, began to appear in the early 1970s. The earliest of
these, Creeper, was a legitimate experiment in self-replicating programs; it didn't cause
any damage beyond printing the message "I'm the creeper; catch me if you can!" as it
propagated across the ARPANET, the forerunner of the Internet. Viruses took on a more
sinister tone in the next decade, when the Elk Cloner virus appeared on early Macintosh
computers in 1982. Written by a fifteen-year-old, it propagated by means of floppy disks.
More destructive viruses appeared in the mid- to late-1980s. The most serious of these,
the Morris Worm, took down the ARPANET within 24 hours. It's author, Robert Morris,
became the first malware author convicted of a crime. Today, malware is ubiquitous.
Science fiction postulated computers being subverted by malware much earlier. For
instance, in the 1967 episode "Wolf in the Fold" of the original Star Trek television
series, a malicious, incorporeal entity inhabits and gains control of the main computer
system of the starship Enterprise. Just as in today's spacecraft, the computer manages
most of the functions aboard the starship, allowing the malevolent entity to wreak havoc.
Captain Kirk and Mr. Spock devise a plan to force the computer to solve an insoluble
mathematical problem. After programming the "duotronic" computer's "compulsory scan
unit," Mr. Spock compels it to solve the problem by issuing a voice command:
"Computer, this is a class A compulsory directive; compute to the last digit the value of
pi."
3
He comments to Captain Kirk "As we know, the value of pi is a transcendental figure
without resolution."
The malevolent entity reacts much as any undergraduate would when given the
assignment: "No, no, nooooooo!"
The computation continues, consuming ever more memory, until the malevolent entity
can no longer tolerate it and flees the computer.
Now, most of us would be happy if we had only one malevolent entity in our computer.
Nonetheless, what, exactly, did Mr. Spock do?
The Leibnitz Formula and Summation Notation
Mr. Spock likely used the Leibnitz formula for π,
which is an alternating series:
He also probably used arbitrary precision arithmetic. Instead of being limited to the
precision available in 32-bit (float) or 64-bit (double) floating-point values, he
programmed the computer to use much greater precision. This is actually available in
C++ through the Boost Multiprecision Library
(https://www.boost.org/doc/libs/1_77_0/libs/multiprecision/doc/html/boost_multiprecisio
n/intro.html).
However, we're going to use double precision for this assignment. (Students entering the
data analytics field or computer scientists or electrical engineers writing numerical
analysis programs may want to keep the Boost Multiprecision Library in mind. Other
programming languages have similar libraries.)
4
The Leibnitz formula uses summation notation. Let's review that.
Summation Notation
Often mathematical formulae require the addition of many variables. Summation or
sigma notation is a convenient shorthand used to give a concise expression for a sum of
the values of a variable. Here's the general form:
Notice that the notation says that i goes from 1 to n but doesn't indicate what the
increment is; it's assumed to be 1.
In the Leibnitz formula, k is used as the index of summation rather than i. Additionally, k
begins at 0 rather than 1 (we computer scientists like that). The stopping point for the
Leibnitz formula is infinity,∞. We can't add up an infinite number of terms so we'll need
to rewrite the equation,
as an approximation:
Infinity is replaced by n, a constant upper summation limit and the equal sign is replaced
with an approximately equal sign, ≈.
The xi in the Liebnitz formula is the term
where, as mentioned earlier, k is used instead of i as the index of summation.
5
Our approximation,
expands to:
Suppose we choose n to be 5,
then our approximation becomes
which reduces to:
Translating Summation Notation to C++ Code
How does summation notation translate to C++?
The upper limit of the summation, n, could simply be a constant, 5, say, or 1048576
(which is 220), in C++:
6
The sigma character represents a summation and maps to a C++ for loop. The index of
the for loop is k, the upper bound on the for loop is n and the increment (implicit in the
summation notation) is 1.
The condition expression for the loop is k <= n. The loop continues to iterate as long as
the condition expression is true; the iterations terminate when it is not true. We want n to
be "counted", so k <=n is used instead of k < n. The upper limit of the summation is n
after all, not n-1. The loop terminates when k is greater than n.
The update expression changes k on each iteration of the loop, incrementing it by one.
Now, we need to accumulate the value for each term as we iterate through the loop. How
do we do that?
We introduce a new variable, piOver4, to accumulate the values of each term as the loop
iterates.
Our approximation,
7
translates to the following pseudo code:
Notice that we haven't yet translated the "typical term", , to C++ code.
Instead of the assignment operator, as in piOver4 = piOver4 ..., we could use the +=
addition assignment operator.
Notice that piOver4 is initialized to 0.0 before entering the loop. If it were initialized to
something else, such as 1.0, the sum would be incorrect. The accumulator in this case
must be initialized to 0.0.
Pow!
For (-1)k
, you could use a straightforward approach such as the power function, pow. For
example,
pow(-1.0, k)
which raises -1.0 to the k'th power.
To use the pow function, you'll need to include header file cmath.
For the denominator of the typical term, remember that you're computing a floating-point
value, so you may want to use 2.0 instead of 2, or 1.0 instead of 1 so that you avoid
integer arithmetic.
8
Output Formatting
Fixed Point Notation for Displaying Floating Point Values
Floating point can be displayed in scientific notation or in fixed point notation.
When displaying our approximations to pi, fixed point notation is more convenient.
To specify fixed point when outputting floating point values using the std::cout character
output stream object, used the std::fixed flag as follows:
std::cout    << std::fixed;
Precision
C++ float and double data types have limited precision. They have only 32 and 64 bits,
respectively, to represent floating point numbers. Of these bits, only 24 and 53 are
mantissa bits, respectively, (the bits that represent the value), the remainder are the
exponent bits and the sign bit.
The bit pattern for decimal 123 is shown in the figure below for a float data type.
The implicit 1 in front of the 23 mantissa boxes in the figure above counts as a mantissa
digit, giving a total of 24 mantissa digits for a float data type.
So we have 24 and 53 bits of precision for floats and doubles. That's the precision in base
2 digits. What about the precision for base 10?
15 decimal places is the precision in decimal digits of a 64-bit C++ double precision
floating point value (double). It's the value of log10(253) rounded down, where 53 is the
number of mantissa digits in a double.
The header file cmath (and cfloat) defines the macro constant DBL_DIG to be the
number of decimal digits of precision of a double, 15. When setting the precision to be
displayed for this assignment, you can pass the DBL_DIG macro constant to the
std::setprecision() function. For example,
std::cout    << std::setprecision(DBL_DIG);
9
The cmath header file also defines the macro constant DBL_MANT_DIG, which indicates the
number of mantissa digits in a double precision floating point value (double), which is 53.
When using the GNU Compiler Collection (GCC) C++ compiler, you may need to
include float.h (or, equivalently, cfloat) to obtain the definitions of DBL_DIG and
DBL_MANT_DIG.
#include <cfloat>
The Assignment
The assignment consists of two parts; each part is an independent program.
Part I
In the first part of the assignment, you'll write a program that implements the Leibnitz
formula to approximate the value of π using an upper bound for k entered by the user.
Call the integer variable for the upper bound n, and the integer variable of summation k.
Use a single for loop. Implement this program in a C++ source file named
leibnitz_pi.cpp.
Change the Leibnitz formula for π,
so that it is an approximation and so that it computes π directly, rather than π/4:
Represent π as a variable named pi.
When submitting the assignment, enter 1048576, which is 220, as the value for n, the
upper bound for index k.
Print the value of pi out to 15 decimal places and display it in fixed point notation. Use
the value DBL_DIG defined in header cmath (or cfloat) when setting the precision to 15
decimal places. (See the Output Formatting subsection in the Background section for
details.)
10
After displaying the value of pi to 15 decimal places as approximated by our truncated
Leibnitz formula, display the actual value of π to 15 decimal places (it's
3.141592653589793).
Display pi and n on the same line; set the width for n to 7. Print the actual value for π on
the following line. Your calls should look similar to the following:
std::cout    << "PI    (approx):    " << pi    << ";    n:    " << std::setw(7)    << n    << std::endl;
std::cout    << "PI    (actual):    " << "3.141592653589793" << std::endl;
Next, print out the value of the DBL_DIG and DBL_MANT_DIG macro constants. DBL_MANT_DIG
indicates the number of base 2 mantissa digits in a double, based on the IEEE 754
Floating Point standard (it's 53 for double).
Finally, use the std::nextafter method to determine if the value for pi to 15 digits could
have been represented exactly. This gives some idea of how the limited number of
representable floating point values might affect our calculations. Your code should be
similar to the following.
std::cout    << "Decimal    digits    of    precision:    " << DBL_DIG << std::endl;
std::cout    << "Number    of    base    2    mantissa    digits    of    double    precision    floating    point    value: "
                                        << DBL_MANT_DIG << std::endl;
std::cout    << "Next    representable    number    from    3.141592653589793:    "
                                        << std::nextafter(3.141592653589793,    3.14)    << std::endl;
The output of your program should appear similar to the following screen capture:
Part II
In Part II you'll reuse much of your code from Part I. Name the source file for this
program leibnitz_pi_converge.cpp
Encapsulate the for loop to calculate pi from Part I in another, outer, for loop whose
index is n, where n is the upper bound passed to the inner for loop.
n should start at 2 and double in value on each iteration until it reaches 220, or 1048576.
The output of your program should appear similar to the following.
11
Notice how the value of pi approaches (or converges on) the actual value of π as n
increases.
In Part II, you won't need to prompt the user for the value of n.