BrickInTheWall

06-05-2009, 10:41 PM

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

-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

-4 | -4 | -4

-4 | -4 | -4

-4 | -4 | -4

-4 | -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

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).

If I don't use this round function, I only get about 800-something matches...why? The array clearly shows that newtonsMethod() returns values that are practically always exactly -2 or -4 as it returns doubles...why do I have to round these values to get more matches (and with that, the actual amount of matches) when the values of the array I printed out aren't like -2.00012 or -4.00035 or something like that, but rather, just -2 or -4?

I hope I explained what my question is...I simply don't understand what the cause of this is as I am still very inexperienced...I also apologize for the wall of text and my not-so-good English (I'm German).

Anyone know what the cause of this is? Also, if you have any suggestions of how I could optimize my code, I'd be more than happy to accept them, as the function I wrote (which isn't even complete yet), is already waaaaay to long.

Cheers,

Chris!

// 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

-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

-4 | -4 | -4

-4 | -4 | -4

-4 | -4 | -4

-4 | -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

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).

If I don't use this round function, I only get about 800-something matches...why? The array clearly shows that newtonsMethod() returns values that are practically always exactly -2 or -4 as it returns doubles...why do I have to round these values to get more matches (and with that, the actual amount of matches) when the values of the array I printed out aren't like -2.00012 or -4.00035 or something like that, but rather, just -2 or -4?

I hope I explained what my question is...I simply don't understand what the cause of this is as I am still very inexperienced...I also apologize for the wall of text and my not-so-good English (I'm German).

Anyone know what the cause of this is? Also, if you have any suggestions of how I could optimize my code, I'd be more than happy to accept them, as the function I wrote (which isn't even complete yet), is already waaaaay to long.

Cheers,

Chris!