这个作业是用C++完成数学符号的计算

AMS 595 C++ Assignment

1 Functions
Write a single C++ program containing the following functions.
1. Write a function that determines whether a number is prime.
bool i s p rim e ( int n ) {
bool r e s u l t ;
// Your im plemen t a t i on
return r e s u l t ;
}
void t e s t i s p r i m e ( ) {
s t d : : cou t << ” i s p rim e ( 2 ) = ” << i s p rim e ( 2 ) << ’ \n ’ ;
s t d : : cou t << ” i s p rim e (10 ) = ” << i s p rim e (10 ) << ’ \n ’ ;
s t d : : cou t << ” i s p rim e (17 ) = ” << i s p rim e (17 ) << ’ \n ’ ;
}
2. Write a function that finds all the factors of a number.
s t d : : v e c to r<int> f a c t o r i z e ( int n ) {
s t d : : v e c to r<int> answer ;
// Your im plemen t a t i on
return answer ;
}
void t e s t f a c t o r i z e ( ) {
p r i n t v e c t o r ( f a c t o r i z e ( 2 ) ) ;
p r i n t v e c t o r ( f a c t o r i z e ( 7 2 ) ) ;
p r i n t v e c t o r ( f a c t o r i z e ( 1 9 6 ) ) ;
}
1
3. Write a function that finds the prime factorization of a number.
s t d : : v e c to r<int> p r i m e f a c t o r i z e ( int n ) {
s t d : : v e c to r<int> answer ;
// Your im plemen t a t i on
return answer ;
}
void t e s t p r i m e f a c t o r i z e ( ) {
p r i n t v e c t o r ( p r i m e f a c t o r i z e ( 2 ) ) ;
p r i n t v e c t o r ( p r i m e f a c t o r i z e ( 7 2 ) ) ;
p r i n t v e c t o r ( p r i m e f a c t o r i z e ( 1 9 6 ) ) ;
}
NOTE: You will also need to implement the following function that prints a C++
vector of integers:
void p r i n t v e c t o r ( s t d : : v e c to r<int>& v ) {
// Your im plemen t a t i on
}
2 Collatz
The Collatz function is defined for (positive) natural numbers as follows:
Collatz(n): If n is even, return n/2, otherwise return (n ∗ 3) + 1
The Collatz sequence applies the Collatz function repeatedly to a starting value until the
returned value is 1. Write a C++ program (recursive or iterative) that accepts a starting
value (e.g. command-line argument or manual input) and prints out the trace of return
values from the Collatz function until 1 is reached.
(The interesting thing about this sequence is that no one has been able to prove definitively
whether all starting values eventually reduce to 1.)
3 Performance Programming
The following C++ loop nest might not perform well on a typical modern architecture.
Explain what the problems are and rewrite the loop nest in a manner that you expect will
improve performance. You do NOT need to create and execute a complete program, you
should write your version of this code fragment and explain in a paragraph why you think
it will be faster.
2
// n and a r r ay s a , b and c are d e cl a r e d , i n i t i a l i z e d p r i o r t o l o o p
for ( i =1; i<n ; i++)
for ( k=1; k<n ; k++)
for ( j =1; j<n ; j++)
{
i f ( n − 20 > i ) {
a [ j ] [ k ] [ i ] = b [ j ] [ k ] [ i ] + c [ j−i ] [ k ] [ i ] ;
c [ j ] [ k ] [ i ] = 2 ∗ b [ j ] [ k ] [ i +1];
}
e l s e {
a [ j ] [ k ] [ i ] = b [ j ] [ k ] [ i ] − c [ j−i ] [ k ] [ i ] ;
}
}
4 Computing π
The value of π can be computed using the following formula:
Z 1
0
√
1 − x
2dx =
π
4
To evaluate this integral with computers, we can use the trapezoidal rule:
Z b
a
f(x)dx ≈
X
N
k=1
f(xk−1) + f(xk)
2
∆xk
Your Work
You will write a C++ program that computes the value of π using the following formula:
π ≈ 2∆xk
X
N
k=1
[f(xk−1) + f(xk)]
For this C++ program, the user will input the number of intervals (N in the formula
above), and your program should compute the value of π and print the error (the pre-supplied
value of π in C++ is M PI from the <cmath> header).
Try several compiler optimization levels for your program and see if they lead to any
performance differences. In your documentation, include a paragraph that states which
levels (or flags) you tried and summarize the outcome in a sentence or a table.
If you would like an additional challenge, you may also create an optional second program
based on the same formula for computing π, as follows. For the second C++ PI program,
the user will instead input the maximum acceptable error, and your program should find the
3
appropriate number of intervals to use such that the error tolerance is respected, then print
the error and the number of intervals it used. To achieve this, your program should first try
to evaluate the integral with a small number of intervals, and try again with bigger numbers
if the error is greater than the tolerance.
Note that there are several ways to write the second C++ PI program: for example,
one could estimate the number of intervals to use with the asymptotic error formula of the
trapezoidal rule. But to practice your C++ skills, you should stick to the method provided
above. Also, you may want to enforce an upper limit to the number of intervals to try,
since the trapezoidal rule is only first-order and thus a very large number of intervals will be
needed to satisfy any error tolerance less than 10−8
.