C++, issues converting decimal to fraction

alpha_gamma · #1 02-Jun-2007, 10:01

Hi all,

I am working on a C++ program that converts a decimal to a fraction, finds the lowest common multiple, multiplies the numerator by the denominator, then reduces the fraction again so the fraction will be 'numerator/1'.

I am using this code in a larger program to change a floating point slope value to a whole value for slope-intercept equations and standard form equations.

The program will run but I tested almost 500 numbers and 20 numbers made the program crash (it stalled and did not finish the equation, I had to close the terminal and open it up again... )

These 20 numbers I had problems with:

2.36, 7.36, 1.11, 1.001, 1.66, 1.88, 2.22, 2.13, 3.24, 3,26, 3.32, 3.43, 3.49, 3.51, 3.57, 3.68, 3.74, 3.76, 3.82

(I am sure there are more...)

I have tried c-style casting and dynamic and static casting to try to resolve this issue. Can someone help me out and point out why these certain numbers make the program crash and offer a possible sloution?

I tried debugging this program on gdb and keep on getting this frustrating message..

(gdb) break 16
No line 16 in file "init.c".
(gdb)

Here is the program's code, zip file with source code is attached to this email:

CPP / C++ / C Code:


//example.cc
#include <iostream>
#include "reduce.h"
#include "decimal-to-fraction.h"
using namespace std;

int main()
{
	double deci;
	double n, d;

	while(1) {
		cout << "Enter a decimal to convert to a fraction ('0' to quit): ";
		cin >> deci;
		cin.ignore(INT_MAX, '\n');
		if(!deci) exit(0);
		
		dec_to_frac(deci, n, d);
		
		if (n * d != n){
			cout << '\n' << deci << " = " << n << '/' << d << "\n\n";
			cout<<'\n' << d << " x " << n;
			n = d * n;
			cout<< " = " << n << "\n\n";
			cout<<'\n' << n << '/' << d; 
			reduce(n, d);
		
			cout << " = " << n << '/' << d << "\n\n";

			cout<<'\n' << n << "\n\n";
		}
		
		else
			cout<<'\n' << deci<< "\n\n";
	
	}

	return 0;
}

#ifndef _REDUCE_H_

#error You must include "reduce.h" before this file

#endif /* def _REDUCE_H_ */



#ifndef _DECIMAL_TO_FRACTION_H_

#define _DECIMAL_TO_FRACTION_H_



void dec_to_frac(double decimal, double &numerator, double &denominator)

{

	//numerator = static_cast<int >(decimal);
	//numerator = (int )decimal;
	numerator = decimal;

	denominator = 1;
	


	while(numerator != (int)numerator) {

		numerator *= 10;

		denominator *= 10;

	}

	reduce(numerator, denominator);

}



#endif /* def _DECIMAL_TO_FRACTION_H_ */

#ifndef _REDUCE_H_

#define _REDUCE_H_



void reduce(double &numer, double &denom)

{

	int i;



	for(i=2; i<=numer; ++i) {
		

		if( ((numer/i) == ((int )(numer/i))) && ((denom/i) == ((int)(denom/i))) ) {

			numer /= i;

			denom /= i;

			--i;              

		}

	}

}



#endif /* def _REDUCE_H_ */

davekw7x · #2 02-Jun-2007, 13:11

Quote:

Originally Posted by alpha_gamma

Hi all,

I am working on a C++ program that converts a decimal to a fraction
.
.
.

I tried debugging this program on gdb and keep on getting this frustrating message..

First of all, let me say that I admire and appreciate your efforts in testing. Good show.

Now, there are two aspects of your problem:
1. Program doesn't work
2. Debugging with gdb is not productive.

I will address the second one in this post, and, if you still need some help with number one, I'll get back to you (or, maybe, someone else will pitch in---all helpful contributions are cheerfully accepted).

Debuggers such as gdb are powerful tools, but I rarely try to help people with gdb by remote control.

Most people who post here have relatively little experience in programming, and I sincerely believe that learning to use the program itself to lead you to the problem is more important at first. Make the program tell you what is happening.

For example:

in the main program, do something like the following:

CPP / C++ / C Code:

        cout << "calling dec_to_frac with deci = " << deci << endl;
        dec_to_frac(deci, n, d);
        cout << "back from dec_to_frac with n = " << n 
             << ", d = " << d << endl;

This tells you whether you are feeding the function what you think it should be getting, and what the values are when (if) it returns.

You have already indicated a "bad" input value, so I'll test it with something that "should be" OK and then with the bad boy:

When I ran your program with this in place, I got the following

Code:

Enter a decimal to convert to a fraction ('0' to quit): 1.23
calling dec_to_frac with deci = 1.23
back from dec_to_frac with n = 123, d = 100

1.23 = 123/100


100 x 123 = 12300


12300/100 = 123/1


123

Enter a decimal to convert to a fraction ('0' to quit): 2.36
calling dec_to_frac with deci = 2.36

The program never returned from the function when I fed it 2.36.

So: now put some stuff inside the function to see what is happening:

CPP / C++ / C Code:

    cout << "Entering dec_to_frac with decimal = " << decimal << endl;
    while (numerator != (int) numerator) {
        cout << "in loop: numerator = " << numerator
             << ", (int)numerator = " << (int)numerator << endl;
        numerator *= 10;
        denominator *= 10;
    }

Output:

Code:


Enter a decimal to convert to a fraction ('0' to quit): 1.23

calling dec_to_frac with deci = 1.23
Entering dec_to_frac with decimal = 1.23
in loop: numerator = 1.23, (int)numerator = 1
in loop: numerator = 12.3, (int)numerator = 12
back from dec_to_frac with n = 123, d = 100

1.23 = 123/100


100 x 123 = 12300


12300/100 = 123/1


123

Enter a decimal to convert to a fraction ('0' to quit): 2.36

calling dec_to_frac with deci = 2.36
Entering dec_to_frac with decimal = 2.36
in loop: numerator = 2.36, (int)numerator = 2
in loop: numerator = 23.6, (int)numerator = 23
in loop: numerator = 236, (int)numerator = 235
in loop: numerator = 2360, (int)numerator = 2359
in loop: numerator = 23600, (int)numerator = 23599
in loop: numerator = 236000, (int)numerator = 235999
in loop: numerator = 2.36e+06, (int)numerator = 2359999
in loop: numerator = 2.36e+07, (int)numerator = 23599999
in loop: numerator = 2.36e+08, (int)numerator = 235999999
in loop: numerator = 2.36e+09, (int)numerator = -2147483648
in loop: numerator = 2.36e+10, (int)numerator = -2147483648

It was an infinite loop. (After long years of training and with adherence a rigorous fitness regime, I have practiced enough that my ctrl-c fingers are pretty quick. I get a fair amount of practice with my own stuff.)

Now you have located the point of the problem. I'll give you a hint as to the nature of the problem: round-off error in representing certain decimal fractional values in the machine's binary floating point number system.

If it had turned out to leave the loop in orderly fashion you could have put print statements around the place where it calls reduce.

Now, for the best chances to get others to help from this point onward, just boil the program down to a small subset that contains just the problem part. (That's the way I typically do program development anyhow: implement and test ---and debug--- one thing at a time before trying to put everything together. I sometimes think that I am the last 'bottom-up' guy in this 'top-down' world.)

Regards,

Dave

Footnote: to get a better "picture" of the problem, then #include <iomanip> and try the following:

CPP / C++ / C Code:

    cout << scientific << setprecision(18);
    while (numerator != (int) numerator) {
        cout << "in loop: numerator = " << numerator

and you might see something like

Code:

calling dec_to_frac with deci = 2.36
Entering dec_to_frac with decimal = 2.36
in loop: numerator = 2.359999999999999876e+00, (int)numerator = 2
in loop: numerator = 2.359999999999999787e+01, (int)numerator = 23
in loop: numerator = 2.359999999999999716e+02, (int)numerator = 235
in loop: numerator = 2.359999999999999545e+03, (int)numerator = 2359
in loop: numerator = 2.359999999999999636e+04, (int)numerator = 23599
in loop: numerator = 2.359999999999999709e+05, (int)numerator = 235999
in loop: numerator = 2.359999999999999534e+06, (int)numerator = 2359999
in loop: numerator = 2.359999999999999627e+07, (int)numerator = 23599999
in loop: numerator = 2.359999999999999702e+08, (int)numerator = 235999999
in loop: numerator = 2.359999999999999523e+09, (int)numerator = -2147483648
in loop: numerator = 2.359999999999999619e+10, (int)numerator = -2147483648

alpha_gamma · #3 02-Jun-2007, 16:11

Thank you very much Dave for your helpful advice. This is a great help, I really need some guidance on testing & debugging.

I found your examples of of printing out the values very helpful. I should develop my own statements this evening and will certainly make use of this method on my next significant bug.

I can certainly see the problem with accurately representing a decimal number in binary. Another issue I was not aware of ( and would have been if I used the techniques that you implemented ) is that comparing double integer values for equality or inequality is very tricky and will lead to these kind of errors. The program wound up with an infinite loop the comparing condition was never met.

I guess now I have these options to implement better comparing methods.

-A simpler method would be to use modulus tests...

-I could take the absolute value of the difference between the numbers being compared, if the difference is 'very small' then the double valus could be considered to be equal.

-I could normalize the double values to integers

-I could use an epsilon approach with something nice and portable like:

Code:

std::numeric_limits<double>::epsilon())

I definitely will dry run these algorithms on paper for several days before putting them through a compiler. I too admire your commitment to testing & debugging as well. I will become one too if I print out the values in the program flow the next time I come across design errors.

Thanks again,

Andrew

davekw7x · #4 02-Jun-2007, 17:58

Quote:

Originally Posted by alpha_gamma

I guess now I have these options to implement better comparing methods.

Another thing to consider is: what is it that you really want to do with user input?

Suppose the user gave 2.35999999 as an input?
Do you want to use 235999999/100000000 as your fraction to begin reducing?

If you input the values as a floating point number, the computer may not be able to distinguish between a user input of 2.35999999 and 2.36. (Actually, it might very well distinguish between the two, but might have an integer overflow when it tried to get the numerator to a whole number. It's kind of a Jabberwocky situation. See footnote.)

You could get the user input as a string and count decimal places to determine the multiplier and then round off the results and then ...

Or, you could specify that the numerator would be rounded to four decimal places and go from there. (That requires a little thinking, but not much work, and the program would be simpler than what you have tried so far.)

Note that floating point numbers are not really about "decimal place" accuracy (or "binary place" accuracy, if you prefer). Floating point numbers are about "significant digit" precision. That's why people are sometimes surprised that they have to do some work converting fractional decimal entries with a certain number of decimal places to floating point representations and manipulating and comparing the little beasties.

What if the user entered 0.236? If the program is supposed to handle that case, then be sure to test it. (And if it is not supposed to handle that case, then you should make sure that user input is not out of range, and the program should inform the user that such input is illegal.)

Regards,

Dave

Footnote:

"Beware the Jabberwock, my son!
The jaws that bite, the claws that catch!
Beware the Jubjub bird, and shun
The frumious Bandersnatch!"
---Lewis Carroll
Through the Looking-Glass and What Alice Found There

alpha_gamma · #5 02-Jun-2007, 19:23

Hello Dave,

I do agree that the decimal places should be reduced to make it easier on the program. I am using these algorithms in a larger program I am working on. I was using this particular application as a smaller test case.

The program is an open-source project I started called Algebra-Agent (13 files and over 900 lines of code). I have the source code and binary file for download at this website:

http://www.andrew.gonzales.com/Algebra-Agent.htm

In this program mentioned, I take an ordered pair of coordinates and compute linear functions and values like: distance, slope, midpoint, y-intercept, x-intercept, a point slope equation for each point, a slope-intercept equation and a standard-form equation.

I use these algorithms in a file called 'coordinates1.cc', they can be found in the functions 'Coordinates::point_slope()' and 'Coordinates::slope_intercept()'.

The algorithms are used on a calculated slope value from the two coordinates and change the floating point slope value to a non-floating point, non-fraction whole number. The academic rules for algebra state that the slope of a slope-intercept equation ( y=mx+b, m being the slope ) cannot be a fraction or floating point number. A similar rule is in place for the standard form equation but I have not added these algorithms to it's function yet.

I will look for an algorithm to round the floating point number down to 2 or maybe 4 decimal places. The scenario you mentioned of taking a number such as '0.236' and handling that case has given me some work with testing/debugging cut out for me this weekend. I collect old C programming books from 15-25 years ago and I'm sure that there is an algorithm available that can do this. I should look through some C++ code as well....

Please feel free to look at the code at the project's web site and also let me know if you know of any good safe methods of trimming/rounding double values floating point decimals to fixed places or so.

Thank you again for your insight to using floating point values and also for the clever quotation from Lewis Carroll. I certainly got chased by the beast this weekend :-)

Regards,

Andrew

Footnote:
"Believing and understanding are not different things but the same thing in different periods of growth..."

-Samuel Tyler Coleridge

davekw7x · #6 02-Jun-2007, 20:37

Quote:

Originally Posted by alpha_gamma

I collect old C programming books from 15-25 years ago and I'm sure that there is an algorithm available that can do this.

Although bankers and some mathematicians do a little more work to keep symmetry in the universe, the classical programmer's way of rounding a positive floating point number to an integer is the following. (See footnote.)

CPP / C++ / C Code:

    unsigned int int_value;
    double floating_value;

    int_value = floating_value + 0.5; /* assignment truncates the fractional value */

Of course, this only works if the number of bits required to represent the integer is no more than the maximum number of bits in an unsigned int. (Note that the number of bits in the mantissa of a double may be more than the number of bits in an int, so you may get a compiler warning on the assignment, but you would surely have made certain that the number wasn't too big to work with, right?)

So how about this to round to one decimal place:

CPP / C++ / C Code:

    int_value = 10.0 * floating_value + 0.5; /* resulting integer is 10 times original */
    floating_value = int_value / 10.0  /* is nearest you can get to 1 decimal place accuracy */

Now, in your case you don't need the division at all. since you will just multiply the integer denominator by 10. And once you get an int, you do everything else with ints, so there is no further possibility of introducing roundoff error(!)

Similarly for two, three, or however many decimal places you want to keep, just multiply by 100 or 1000, or whatever, then add 0.5 and truncate (by assignment to an int).

Regards,

Dave

Footnote: the difference between the "bankers' method" and the "simple-minded programmers' method": With the "bankers' method", numbers whose fractional part is exactly equal to 0.5 are "rounded" to the nearest even integer, but the programmer goes to the next higher integer.

So a programmer and a banker would both round 1.5 to 2, but they would get a different result with 4.5. (Banker gets 4; programmer gets 5.)

With the programmers' method and an ever-increasing number of random quantities subjected to rounding, the universe gets heavier and heavier, since "ties" between integers are always rounded up.

WIth the bankers' method, everything stays balanced, since the number of "ties" that are rounded up is equal (in the long run) to the number that are rounded down.

alpha_gamma · #7 03-Jun-2007, 09:23

Thank you very much for the very informative explanation on floating point arithmetic on CPU architecture. This is a wealth of information on this thread :-) I have plenty of research to do on what I have learned and plan to write a lot of code down on paper before i implement anything. I will certainly spend more than one day dry running the code...

I am thinking of changing my while loop and putting a loop limiter value in it and increment the limiter each time through. This can prevent infinite loops. When I am certain my code is correct and robust I will remove the limiter in confidence that the loop will not be infinite.

something like this:

while(1 && looplimit < maxloops) {....looplimit +=1;}

I am also thinking of changing numerator and denominator to 'int' or 'long' instead of being 'double'. I guess I'm not expecting the numerator and denominator values to have decimal points, so I should probably use integral types. Hopefully this may get me out of trouble.

I may be wrong....

Regards,

Andrew

Thread Tools	Search this Thread
Show Printable Version Email this Page	Search this Thread: Advanced Search
Rate This Thread
Rate This Thread:

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Binary to Decimal Conversion	Saberwing	C Programming Language	5	28-Dec-2006 14:57
Issues converting Fahrenheit to celsius	Skampy	CPP / C++ Forum	7	25-Feb-2006 08:04
overloading operators in a class.	fevershark	CPP / C++ Forum	11	22-Feb-2006 19:34
fraction class program	fevershark	CPP / C++ Forum	7	31-Jan-2006 11:12
Hex Result giving strange answers.	Rosdahale	C Programming Language	6	07-Dec-2004 20:28

C++, issues converting decimal to fraction

Re: C++, issues converting decimal to fraction

Re: C++, issues converting decimal to fraction

Re: C++, issues converting decimal to fraction

Re: C++, issues converting decimal to fraction

Re: C++, issues converting decimal to fraction

Re: C++, issues converting decimal to fraction