Sign in to follow this  
BrickInTheWall

I'm having problems comparing values in my code (C++)

Recommended Posts

Hello everybody, I'm having a few problems comparing numbers in my program which forces me to round them, which doesn't always give me the desired results...I'll quickly try to explain what I'm doing...I wrote a bunch of code that builds together a mathematical function based on user input...the function class ( called "Func" ) I wrote which contains methods for the functions derivatives etc. works just fine...it's finding a functions roots that is causing me problems. I'm a beginner so please bear with me. Here is the code I'm currently using to evaluate a functions roots:
// A function used for rounding
double round( double x, double decimals )
{
	// Rounding one decimal
	x = x * pow( 10, decimals );
	x = int( x > 0.0 ? x + 0.5 : x - 0.5 );
	x = x / pow( 10, decimals );
	return x;
}

// Calculates a functions possible root using Newton's method
double newtonsMethod( Func* f, double x0 )
{
	// Start the loop
	for( int i = 0; i < 10; i++ )
	{
		x0 = x0 - ( f->func( x0 ) / f->dfunc( x0 ) );
	}
	return x0;
}

// Evaluate the number of roots a function has
int evaluateNumOfRoots( Func* f )
{
	double x = -10;		// Start at -10
	double dx = 0.01;	// Move in steps of 0.01
	int numOfReqMatches = 3;	// Number of required matches
	int numberOfRoots = 0;		// The number of roots found
	int matchCounter = 0;		// Is used to count the number of matches in the array
	int oldestValue = 0;		// Stores which value is to replaced because it is the oldest

	// Stores the last values which are to be checked for matches
	double* prevResults = new double[numOfReqMatches];
	double rootsFound[1000];	// 1000 should suffice

	// Start actual loop
	while( x < 10 )
	{
		if( x == 10 )
		{
			// Fill the elements with numOfReqMatches new values only for the first time
			for( int i = 0; i < numOfReqMatches; i++ )
			{
				prevResults[i] = newtonsMethod( f, x );
				x += dx;	// Change once more for next time before exiting loop
			}
		}
		else
		{
			// Fill the oldest one with a new value
			prevResults[oldestValue] = newtonsMethod( f, x );
			x += dx;	// Change for next time

			if( oldestValue == 2 )
			{
				oldestValue = 0;		// Reset if necessary
			}
			else
			{
				oldestValue++;			// Increment if necessary
			}
		}

		// Check to see if we have matching values within the array
		for( int i = 1; i < numOfReqMatches; i++ )
		{
			if( round( prevResults[i-1], 2 ) == round( prevResults[i], 2 ) )
			{
				matchCounter++;
			}
		}

		if( matchCounter == numOfReqMatches - 1 )
		{
			numberOfRoots++;	// Found one!!
			matchCounter = 0;
		}
		else
		{
			matchCounter = 0;	// Didn't find one
		}
	}
	// Delete the array and return the number of Roots
	delete[] prevResults;
	return numberOfRoots;
}

I'll quickly explain how the last function works: I'm using an array with three places to test whether or not I have found a root. A root is found, if all 3 of the elements in the array are the same. I am always replacing the oldest value in the array with the current result I get for a possible root using the newtons Method...the newtons Method will give me a possible answer (usually if the starting point is close enough). If I have the matching answers from that function, I have found a root, and the variable used for counting roots is incremented. Right now this function always increments said variable when 3 matches are found in the array, so I am of course getting way more roots than there are, because I find the same ones a lot of times. I think a look in the array will help explain what I mean. I'm calculating them for x[-10;10] in steps of dx = 0.01...the array looks as follows (note that the oldest value is always replaces each time x is increased by dx):
-2 | -2 | -2
-2 | -2 | -2
-2 | -2 | -2
-2 | -2 | -2
-2 | -2 | -2
-2 | -2 | -2
-2 | -2 | -2
-2 | -2 | -2
.
.
.
.
-2 | -2 | -2
-2 | -2 | -2
-2 | -2 | -2
-1.99999 | -2 | -2
-1.99999 | -1.99317 | -2
-1.99999 | -1.99317 | -5
-4.00069 | -1.99317 | -5
-4.00069 | -4 | -5
-4.00069 | -4 | -4
-4 | -4 | -4
-4 | -4 | -4
-4 | -4 | -4
-4 | -4 | -4
-4 | -4 | -4

.
.
.
-4 | -4 | -4
.
.
.
-2 | -2 | -2
-2 | -2 | -2
-2 | -2 | -2
-2 | -2 | -2

There are 2000 different array compositions and well over 1900 of them always have the same 3 elements (either -2 or -4) The function I am working with does infact have its roots at x = -2 and x = -4...as you can see not all arrays have either -4 or -2 as their only elements, simply because the newtons method doesn't work all the time...but it's no problem, since I strictly only want to accept those solutions of the newtonsMethod( &f, x ) which are found 3 times in a row and stored in the array. Now, as you can see by the rough course of this array's stored elements, almost all of these "pairs" will be evaluated as function roots...this is where problems occur... Here is the part which checks if we have a root:
// Check to see if we have matching values within the array
		for( int i = 1; i < numOfReqMatches; i++ )
		{
			if( round( prevResults[i-1], 2 ) == round( prevResults[i], 2 ) )
			{
				matchCounter++;
			}
		}

		if( matchCounter == numOfReqMatches - 1 )
		{
			numberOfRoots++;	// Found one!!
			matchCounter = 0;
		}
		else
		{
			matchCounter = 0;	// Didn't find one
		}
	}

Anyways, I have to use the round() function I wrote to get the nearly 2000 found roots (numberOfRoots) I desire (since the array shows that almost all x values for newtonsMethod result in either -2 or -4....-10 to 10 in steps of 0.01 is 2000 values). My problem best becomes visible when checking for roots which are only -2 or -4 and not rounding the values received from the newtonsMethod() method...here is what I mean: I change this line:
		if( matchCounter == numOfReqMatches - 1 )
		{
			numberOfRoots++;	// Found one!!
			matchCounter = 0;
		}
to:
		if( matchCounter == numOfReqMatches - 1 && newtonsMethod( f, x ) == -4 )
		{
			numberOfRoots++;	// Found one!!
			matchCounter = 0;
		}
I do the same thing for -2 ...without using the round() function I wrote, I only get about 68 matches and for -2 I get about 1300-something when there are clearly way more....sadly I don't get exactly the right amount of matches either when using the round() function which leads to the fact that it will find a root which is practically the same as one it has already found....I don't get why, because all the values in the array (see text file above) are not rounded, but actually calculated using the newtonsMethod() function and output to a text file....not rounded Hope you can understand what I mean...sorry about my English :) Cheers, Chris [Edited by - Zahlman on June 7, 2009 1:09:37 AM]

Share this post


Link to post
Share on other sites
in your calculations I see you using == with floating point numbers. That is your mistake right there. Repeat after me "There is no such thing as equality in floating point math" and keep it up until you realize that it is true. you need to compare that is with in some delta of the desired value. say x - 10 > -.05 && x - 10 < .05 or something. floating point math is imprecise and just doesn't work that way.


Also note :
if x is less than 10 then it will never be equal to ten.
while( x < 10 )
{
if( x == 10 )

Share this post


Link to post
Share on other sites
For extended information on what stonemetal has said, I suggest you check out What Every Computer Scientist Should Know About Floating-Point Arithmetic. There is also a nifty numeric_limits::epsilon() function in the limits header that you might find useful, depending on what you are doing and how much tolerance you want. Oh, and GameDev [code][/code] tags (as well as [source][/source] tags) are lowercase :)

Share this post


Link to post
Share on other sites
I see your point guys, I didn't know this...I'm still a noob...oh and stoneguy, I noticed that mistake a while ago that it should actually be x == -10 ...I copy pasted old code from one of my files...sorry about that...but a good eye you got there :D ...thanks for the help guys, I'll work with your advices.
Cheers,
Chris

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this