[quanhi21]

Hello all, I'm new here. This is my first semester taking C++ as a programming class (online course), I stuck on this problem hopefully someone can help out. I took college algebra II math also, but I've never recalled seeing this formula . I don't know or have no ideal on how to do this.

Here is the problem


The Maclaurin series for arctan(x) is a formula which allows us to compute an approximation to arctan(x) as a polynomial in x. The formula is:

arctan(x) = x - x3/3 + x5/5 - x7/7 + x9/9 - x11/11 + . . .

Write a program which reads in a double x, and a positive integer k, and prints out the partial sum from the first k terms in this series.

Sample output

Enter x:
0.5
Enter integer k:
3
The partial sum from the first k terms: 0.4645833333333333

-------------------------------------------------------

Well, here are my codes

#include <iostream>
using namespace std;

int main()
{ 
	double x, sum = 0.0; 
	int k;
	
//user input
	cout << "Enter x: \n";
	cin >> x;
	
	cout << "Enter interger k: \n";
	cin >> k;
	
	sum =  x - x3/3 + x5/5 - x7/7 + x9/9 - x11/11
	
	cout << "The partial sum from the first k terms" << sum << endl;
		 
 return 0;
}

I got these errors when I tried to compile. Pls point out of what I did wrong, thank you!

Error E2451 lab42.cpp 19: Undefined symbol 'x3' in function main()
Error E2451 lab42.cpp 19: Undefined symbol 'x5' in function main()
Error E2451 lab42.cpp 19: Undefined symbol 'x7' in function main()
Error E2451 lab42.cpp 19: Undefined symbol 'x9' in function main()
Error E2451 lab42.cpp 19: Undefined symbol 'x11' in function main()
Error E2379 lab42.cpp 21: Statement missing ; in function main()
Warning W8004 lab42.cpp 24: 'sum' is assigned a value that is never used in function main()
*** 6 errors in Compile ***

**Mod Edit: added code tags:

This post has been edited by NickDMax: 24 September 2009 - 07:13 PM

[eker676]

the x3, x5 really stands for x^3, x^5.

To use powers in C++

Include <cmath>

pow(initialvalue, exponent)

[quanhi21]

so how do I incorporate that "pow" expression into my codes?, sorry I'm kind of new to all this

[eker676]

#include <cmath>
using std::pow;

// ...

sum =  x - (pow(x, 3.0)/3.0) + (pow(x, 5.0))/5.0 - (pow(x, 7.0)/7) + (pow(x, 9.0)/9.0) - (pow(x, 11.0)/11.0);

[quanhi21]

awesome, thanks for your help eker676!

[NickDMax]

Just some academic information to put into your computer science vault:

So we are trying to calculate the following sum:

sum =  x - pow(x,3)/3 + pow(x,5)/5 - pow(x,7)/7 + pow(x,9)/9 - pow(x,11)/11

Using functions like pow() tends to be expensive and should generally be avoided if you can (i.e. for integer powers for which you know the value, use multiplication over the pow() function).

So the program would be faster if we were to use:

sum = x - x * x * x / 3.0 + x * x * x * x * x / 5.0 - x * x * x * x * x * x * x / 7.0 + x * x * x * x * x * x * x * x * x / 9.0 - x * x * x * x * x * x * x * x * x * x * x / 11.0;

But that is a LOT of multiplications and so we know that we can simplify things by precalculating some of the multiplication. Lets say x2 = x * x

this leaves us with:

x2 = x * x;
sum = x - x2 * x / 3.0 + x2 * x2 * x / 5.0 - x2 * x2 * x2 * x / 7.0 + x2 * x2 * x2 * x2 * x / 9.0 - x2 * x2 * x2 * x2 * x2 * x / 11.0

(lets keep this one in mind for a bit since this happens to look like a polynomial with respect to x2)

and we could carry on in this way until we had removed much of the redundancy:

x2 = x * x;
x4 = x2 * x2;
x8 = x4 * x4;
sum = x - x2 * x / 3.0 + x4 * x / 5.0 - x4 * x2 * x / 7.0 + x8 * x / 9.0 - x8 * x2 * x / 11.0;

We have gone from 31 multiplications down to 10!!! Surely that has to be faster...

However we can reduce it even a bit more if we look closely at the version where we just replaced x2 -- that version forms a polynomial with respect to x2 -- and we can use Horner scheme to reduce the number of multiplications which gives us:

x2 = x * x;
sum = ((((-x * x2/11.0 + x/9.0) * x2 - x/7.0) * x2 + x/5.0) * x2 - x/3.0) * x2 + x

which reduces our code to 6 multiplications (not a huge improvement over 10, but much much less than 31.

Now the sum is not readily recognizable but it should be faster... Time for some tests. The following program will do some basic profiling (not terribly scientific but enough to get a feel for things):

#include <iostream>
#include <string>
#include <cmath>
#include <ctime>

using namespace std;


double PowArcTan(double x) {
	return x - pow(x, 3)/3.0 + pow(x, 5)/5.0 - pow(x, 7)/7 + pow(x,9)/9 - pow(x, 11)/11;
}

double MulArcTan(double x) {
	return x - x * x * x / 3.0 + x * x * x * x * x / 5.0 - x * x * x * x * x * x * x / 7.0 + x * x * x * x * x * x * x * x * x / 9.0 - x * x * x * x * x * x * x * x * x * x * x / 11.0;
}

double Mul2ArcTan(double x) {
	double x2 = x * x;
	double x4 = x2 * x2;
	double x8 = x4 * x4;
	return x - x2 * x / 3.0 + x4 * x / 5.0 - x4 * x2 * x / 7.0 + x8 * x / 9.0 - x8 * x2 * x / 11.0;
}


double HornArcTan(double x) {
	double x2 = x * x;
	return ((((-x * x2/11.0 + x/9.0) * x2 - x/7.0) * x2 + x/5.0) * x2 - x/3.0) * x2 + x;
}


const double PI =  3.14159265;

const int SIZE = 100000000;

#define TEST(name) {  \
	double array[100];  \
	int count = 0; \
	double timeTaken; \
	unsigned long now = clock(); \
	for (double theta = -tau; theta < tau; theta += PI/SIZE) { \
		array[count++ % 100] = name(theta); \
	} \
	timeTaken =  double(clock() - now)/CLOCKS_PER_SEC; \
	cout << #name " Calculated " << count << " values in :\t" << timeTaken << " seconds." << endl;  \
}


int main() {
	double tau = PI/4;
	double tn = tan(tau);
	double matn = HornArcTan(tn);
	double oatn = PowArcTan(tn);
	cout << "calculating some values... " << endl;
	cout << tn << "> " << tau << "> " << matn << " : "  << oatn << " : " << matn-tau << " : " << matn-oatn << endl;

	TEST(PowArcTan);
	TEST(MulArcTan);
	TEST(Mul2ArcTan);
	TEST(HornArcTan);
	
	return 0;
}

Now the first compiler I ran this on gave me the following result:
Borland 5.5 compiler

Quote

> "C:\CProjects\Forum Help\ArcTanTest.exe "
calculating some values...
1> 0.785398> 0.744012 : 0.744012 : -0.0413866 : 1.11022e-16
PowArcTan Calculated 50000000 values in : 12.828 seconds.
MulArcTan Calculated 50000000 values in : 2.687 seconds.
Mul2ArcTan Calculated 50000000 values in : 1.906 seconds.
HornArcTan Calculated 50000000 values in : 2.188 seconds.

I was VERY surprised to see that Mul2ArcTan was the fastest!!! (still looking into why)

Visual Studio 10 Beta

Quote

> "C:\CProjects\Forum Help\ArcTanTest.exe "
calculating some values...
1> 0.785398> 0.744012 : 0.744012 : -0.0413866 : 0
PowArcTan Calculated 50000000 values in : 11.859 seconds.
MulArcTan Calculated 50000000 values in : 3.734 seconds.
Mul2ArcTan Calculated 50000000 values in : 3.813 seconds.
HornArcTan Calculated 50000000 values in : 4.094 seconds.

Here things came out as expected although slower than the Borland code...

Visual Studio 10 Beta x64 code:

Quote

> "C:\CProjects\Forum Help\ArcTanTest.exe "
calculating some values...
1> 0.785398> 0.744012 : 0.744012 : -0.0413866 : 0
PowArcTan Calculated 50000000 values in : 10.953 seconds.
MulArcTan Calculated 50000000 values in : 6.5 seconds.
Mul2ArcTan Calculated 50000000 values in : 5.5 seconds.
HornArcTan Calculated 50000000 values in : 4.453 seconds.

Many people might assume that the 64bit code would be faster, but really the computer is having to copy twice as much data in and out of memory which takes some time... Though we might note that the power function on the x64 version is faster than either of the 32bit compilers! In the assembly listing generated the pow function in VS is inline code -- I think this is why VS is so much faster than borland on the library call).

And finally: MinGW (Dev-C++)

Quote

> "C:\CProjects\Forum Help\ArcTanTest.exe "
calculating some values...
1> 0.785398> 0.744012 : 0.744012 : -0.0413866 : 1.11022e-016
PowArcTan Calculated 50000000 values in : 9.687 seconds.
MulArcTan Calculated 50000000 values in : 3.172 seconds.
Mul2ArcTan Calculated 50000000 values in : 3.172 seconds.
HornArcTan Calculated 50000000 values in : 3.203 seconds.

Here the Mul2ArcTan did not gain much if anything from our attempt to optimize it. More than likely this is because the compiler made similar optimizations as we did -- Note also that HornArcTan was beaten by the multiplication here too!!!

<EDIT>
MinGW version run on my laptop:

Quote

> "C:\Dev-Cpp\Projects\C++\Forum Help\ArcTanTests.exe"
calculating some values...
1> 0.785398> 0.744012 : 0.744012 : -0.0413866 : 1.11022e-016
PowArcTan Calculated 50000000 values in : 28.094 seconds.
MulArcTan Calculated 50000000 values in : 7.796 seconds.
Mul2ArcTan Calculated 50000000 values in : 10.141 seconds.
HornArcTan Calculated 50000000 values in : 10.156 seconds.

-- So it would seem that when using the MinGW compiler, it can optimize the multiplication version better than I can by hand. However I should note that this code is significantly SLOWER than the Borland version when run on my laptop... so while I may have the disadvantage in MinGW I still bring something to the party on Borland --- though the Mul2 version was still faster than the Horner Scheme.

</EDIT>

SO what did we discover: #1, that Pow() is slower than multiplication... and that some compilers optimize better than others, and some compilers optimize better than you can by hand! If we were to run these same test on other computers with the same compilers we would probably find different results as well since what is optimized for one platform is not necessarily optimized on another.

Ah... well I had fun...

[quanhi21]

hi all, my number still didn't come out right like the sample output, pls help!

I followed my professor suggestion on how to write this with the "for" loop. Also I have no ideal on how to change the sign each term?, like the first term has positive sign (+), second (-) and so on???

This is what he said "To sovle this problem you need to create a counter called i to keep track the k terms.The loop structure should execute k times. Each time in the loop structure, you need to accumulate each term in the series and increment the counter by one. If k is 5, then you accummulate the first five terms.You also need to change the sign for each term. The first term has positive sign, second term negative sign, third term positvie sign and so on"

#include <iostream>
#include <cmath>
using namespace std;



int main()
{ 
	double x, sum=0.0; 
	int k, counter;
	
//user input
	cout << "Enter x: \n";
	cin >> x;
	
	cout << "Enter interger k: \n";
	cin >> k;
	
	for (couter = 1; couter <= k; couter++)
	
	sum =  x - (pow(x, 3.0)/3.0) + (pow(x, 5.0))/5.0 - (pow(x, 7.0)/7.0) + (pow(x, 9.0)/9.0) - (pow(x, 11.0)/11.0);


	
	cout << "The partial sum from the first k terms " << sum << endl;
		 
 return 0;
}

This post has been edited by quanhi21: 25 September 2009 - 05:35 PM

[eker676]

I would suggest a bool variable that keeps track of the sign.

double sum = x;
bool negative = true;
for(int i = 3; i <= 11; i += 2)
{
	if(negative)
	{
		sum -= (pow(x, static_cast<double>(i)); 
		negative = false;
	}
	else
	{
		sum += (pow(x, static_cast<double>(i));
		negative = true;
	}
}

[CTphpnwb]

Better to let the math do the tracking:

#include <iostream>
#include <math.h>

int main (int argc, char * const argv[]) {
	double x,incr, sum =0;
	int i,j,k;
	std::cout << "Enter x: ";
	std::cin >> x;
	std::cout << "Enter integer k: ";
	std::cin >> k;
	j=3;
	for (i=0; i < k; i++) {
		incr = pow(-1,i)*pow(x,2*i+1)/(2*i+1);
		
		std::cout << "incr: " << incr << "\n";
		sum += incr;
		std::cout << sum << "\n";
	}
	std::cout << "The partial sum from the first "<< k << " terms: " << sum;
	
	return 0;
}

[NickDMax]

I would still prefer to use horner's scheme over using pow...

#include <iostream>
#include <string>
#include <cmath>
#include <ctime>

using namespace std;

//const int arcTanDepth = 10;
const int signs[2] = {-1, 1};

double hornerArcTan(double x, int arcTanDepth) {
/***/string formula = "0";
/***/char temp[10];
/***/int s;
	double x2 = x * x;
	double sum  = 0;
	int depth = arcTanDepth * 2 - 1;
	int signTracker = arcTanDepth;
	while (depth > 0) {
		sum *= x2;
		sum += signs[/***/s = (signTracker-- % 2)]*(x/depth);
/***/   sprintf(temp,"%d",signs[s]*depth);
/***/   formula = string("(")+formula+string(")*x*x + x/") + string(temp); 
		depth -= 2;
	}
/***/cout << formula << endl;
	return depth;
}

const double PI = 3.14159265;

int main() {
	hornerArcTan(PI/2, 20); //this one goes to 39 (20 terms) -- the max term is depth*2-1
	hornerArcTan(PI/2, 6); // this one goes to 11
	return 0;
}

I actually add the lines with /***/ so that it would print out the formula that it calculates the value of -- this can easily be removed to get the actual function. When the formula prints the sign value is in the denominator of the terms, this is done just because it was easier to put it there then try to print it out in the middle of the formula.

I also left in the initial multiplication by zero which could be removed since it offers no benefit and is just a waste of 1 iteration of the loop.

Again this is really just more academic than anything else. Its a chance for me to play a little. If you WERE going to program an arctangent formula using pow() would be a bad idea... then again using the Maclaurin series might not be the best way either.

[quanhi21]

[quote]

CTphpnwb, on 25 Sep, 2009 - 07:33 PM, said:

		incr = pow(-1,i)*pow(x,2*i+1)/(2*i+1);
		
	

Can you please elaborate more on this, I don't get how is it used to compute the arctan formula?

so this is can be written as: incr = (-1^i) * (x^2i+1) / (2i +1) in algebraic expression?

Thanks for all your help

[poncho4all]

Yes that is the algebraic expretion. Its a complete formula for n value.

You see the 2i+1, is gonna make all the i values that are gonna be tested in the range of numbers that you give the for become only odd
2*0+1 =1; 2*1+1 = 3; 2*2 +1 = 5 and so on

This post has been edited by poncho4all: 27 September 2009 - 08:13 AM