Arch Linux

alpha_gamma

Member

Registered: 2007-03-05

Posts: 9

C++, issues with converting a decimal to fraction

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:

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

KomodoDave

Member

From: Oxford, UK

Registered: 2007-04-22

Posts: 162

Website

Re: C++, issues with converting a decimal to fraction

Hi mate,

I've never coded in C/++, only Java and the web dev languages, so forgive me if anything I say seems odd

A few comments on function reduce(a, b):

* You have '++i' in your FOR loop, yet you wish to start with i = 2, so should this not be 'i++' instead?
* Your tests for a shared factor in reduce(a, b) can be replaced by modulus tests, for simplicity:

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

becomes

if (numer % i == denom % i == 0) {

* I'm not sure what your 'reduce' is supposed to achieve - your explanation is a bit vague (or alternatively, it's been a long day and my brain died at lunch =P). Could you let me know, so I can respond further?

- Dave

alpha_gamma

Member

Registered: 2007-03-05

Posts: 9

Re: C++, issues with converting a decimal to fraction

Hello Dave,

I admit that the description of the problem was very vague.   The reduce function will take the fraction that has just been converted from decimal form and reduce it to the lowest common multiple.

I will test the code with your suggestions of changing ++i to i++ and also using modulus test for simplicity.  I have not used modulus tests much before so I will have to read through my books on the subject and dry run the code.

Thank you for those suggestions they sound very good...

Andrew

KomodoDave

Member

From: Oxford, UK

Registered: 2007-04-22

Posts: 162

Website

Re: C++, issues with converting a decimal to fraction

The reduce function will take the fraction that has just been converted from decimal form and reduce it to the lowest common multiple.

You either mean lowest common denominator, or least common multiple. Which is it? =P

x modulus y (x % y) gives you the remainder of integer division x / y . So 17 % 3 = *2*, since 3 into 17 goes 5 times, with *2* left over

You understand ++i vs i++ ? The first will increment i before evaluating its container expression; the second will evaluate the expression, then increment i.

So if i = 0, then 'cout << ++i' shows '1', while 'cout << i++' shows '0', but i is left equal to 1 after the expression has been evaluated.

- Dave

Last edited by KomodoDave (2007-06-02 16:57:27)

alpha_gamma

Member

Registered: 2007-03-05

Posts: 9

Re: C++, issues with converting a decimal to fraction

I do mean the lowest common denominator... Sorry about the semantics.

Thank you for explaining the modulus operator a bit as well as the postfix/prefix operators.

I am using these algorithms in a larger program which is an open source C++ Algebra application for the Linux platform called 'Algebra-Agent'.  It has 13 files and over 900 lines of code, the source code is available at:

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

Hope you have a great weekend...

Andrew

Cerebral

Forum Fellow

From: Waterloo, ON, CA

Registered: 2005-04-08

Posts: 3,108

Website

Re: C++, issues with converting a decimal to fraction

Okay, a few things ('cause I'm picky too):  LCM == "least common multiple" or "lowest common multiple", it's really interchangable.  LCD == lowest common denominator, which is when you're adding two fractions and want to find the lowest denom.  Now that we have that out of the way...

Using ++i or i++ as the third expression in your for loop will make zero difference. 

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

will have exactly the same effect as

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

, though they may have slightly different performances.  The reason for this is that the third expression (i++ or ++i) is evaluated after every iteration of the loop, meaning it doesn't happen until the end of the loop body is reached, and then it's evaluated independently, meaning all you end up with is 'i' incrementing.

As for this:

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

becomes

if (numer % i == denom % i == 0) {

That's about right, it would look more like

if (numer %i == 0 && denom % i == 0)

- the other way would probably not behave the way you expect.

Some other tips:
numer and denom should be 'int' or 'long' - not double.  You don't expect your numerator and denominator to have decimal points, so use integral types - using floating point 'double's is likely what's getting you into this trouble -- floating point arithmetic is inherently imprecise.  You might have better luck parsing the input yourself and constructing the numerator from that instead of reading directly into a floating-point number.

I'm hacking around with your code right now for fun; I'll let you know if I find anything.

==edit==
Oh, something else I wanted to mention; to break on a line in gdb you type:

break filename:linenumber

ie.

break example.cc:16

Last edited by Cerebral (2007-06-03 02:43:42)

Cerebral

Forum Fellow

From: Waterloo, ON, CA

Registered: 2005-04-08

Posts: 3,108

Website

Re: C++, issues with converting a decimal to fraction

Second-post to bring attention to this.   The problem is definitely with this loop:

while(numerator != (int)numerator) {

        numerator *= 10;

        denominator *= 10;

    }

numerator probably never equals (int)numerator because of floating-point trickiness.  I'm not the best manipulator of floating-point numbers, so I don't know if there's a trickier way to do this properly than inputting into an std::string and manually parsing the number out.

e_tank

Member

Registered: 2006-12-21

Posts: 80

Re: C++, issues with converting a decimal to fraction

as Cerebral pointed out floating point arithmetic and how you're using it is your problem here.  floating point data types probably aren't the best choice for something like this.  floats/doubles are base 2, many base 10 numbers cannot be represented exactly as floats or doubles (off the top of my head i don't think any of those numbers you posted in your first post can be stored exactly as doubles).
depending on how you use them you can't expect results without some degree of error.
in the dec_to_frac loop, each time you multiply the numerator by 10 you're accumulating error on some numbers, also on some of these numbers by the time this produces a float/double that contains a whole number the result is too large to fit into a standard integer (so the comparison you're doing there will fail)
you could devise your own base 10 format (floating or fixed) or use an arbitrary precision arithmetic library (such as CLN).

two good floating point references:
chris hecker's gdmag article, good introduction to the format
What Every Computer Scientist Should Know About Floating-Point Arithmetic, explains how error affects floating point arithmetic among other things

KomodoDave

Member

From: Oxford, UK

Registered: 2007-04-22

Posts: 162

Website

Re: C++, issues with converting a decimal to fraction

Using ++i or i++ as the third expression in your for loop will make zero difference. The reason for this is that the third expression (i++ or ++i) is evaluated after every iteration of the loop, meaning it doesn't happen until the end of the loop body is reached, and then it's evaluated independently, meaning all you end up with is 'i' incrementing.

Yeah, he's right, I was being a muppet when I put that. Also, it's actually BETTER to use a prefix increment in that situation I think, since it'll save an address copy, ne?

- Dave

Cerebral

Forum Fellow

From: Waterloo, ON, CA

Registered: 2005-04-08

Posts: 3,108

Website

Re: C++, issues with converting a decimal to fraction

Yeah, he's right, I was being a muppet when I put that. Also, it's actually BETTER to use a prefix increment in that situation I think, since it'll save an address copy, ne?

It seems to make logical sense that ++i would perform slightly better than i++, but the compiler may optimize away the difference since it's a primitive and it's an independent statement.  Hard to say exactly what'll happen, which is why I was vague and said "they may have performance differences." 

alpha_gamma

Member

Registered: 2007-03-05

Posts: 9

Re: C++, issues with converting a decimal to fraction

Thank you very much Cerebral and e_tank for your help. I know have to analyze what information I have and write down the code and do some dry running before I compile anything....