how can i get numerator and denominator from a fractional number?

Question

How can I get numerator and denominator from a fractional number? for example, from "1.375" i want to get "1375/1000" or "11/8" as a result. How can i do it with c++?? I have tried to do it by separating the numbers before the point and after the point but it doesn't give any idea how to get my desired output.

Answer 1

You didn't really specify whether you need to convert a floating point or a string to ratio, so I'm going to assume the former one.

Instead of trying string or arithmetic-based approaches, you can directly use properties of IEEE-754 encoding.

Floats (called binary32 by the standard) are encoded in memory like this:

 S EEEEEEEE MMMMMMMMMMMMMMMMMMMMMMM
 ^                                ^
bit 31                           bit 0

where S is sign bit, Es are exponent bits (8 of them) Ms are mantissa bits (23 bits).

The number can be decoded like this:

value = (-1)^S * significand * 2 ^ expoenent

where:
    significand = 1.MMMMMMMMMMMMMMMMMMMMMMM (as binary)
    exponent = EEEEEEEE (as binary) - 127

(note: this is for so called "normal numbers", there are also zeroes, subnormals, infinities and NaNs - see Wikipedia page I linked)

This can be used here. We can rewrite the equation above like this:

(-1)^S * significand * exponent = (-1)^s * (significand * 2^23) * 2 ^ (exponent - 23)

The point is that significand * 2^23 is an integer (equal to 1.MMMMMMMMMMMMMMMMMMMMMMM, binary - by multiplying by 2^23, we moved the point 23 places right).2 ^ (exponent - 23) is an integer too, obviously.

In other words: we can write the number as:

(significand * 2^23) / 2^(-(exponent - 23))    (when exponent - 23 < 0)
or
[(significand * 2^23) * 2^(exponent - 23)] / 1 (when exponent - 23 >= 0)

So we have both numerator and denominator - directly from binary representation of the number.

---

All of the above could be implemented like this in C++:

struct Ratio
{
    int64_t numerator; // numerator includes sign
    uint64_t denominator;

    float toFloat() const
    {
        return static_cast<float>(numerator) / denominator;
    }

    static Ratio fromFloat(float v)
    {
        // First, obtain bitwise representation of the value
        const uint32_t bitwiseRepr = *reinterpret_cast<uint32_t*>(&v);

        // Extract sign, exponent and mantissa bits (as stored in memory) for convenience:
        const uint32_t signBit = bitwiseRepr >> 31u;
        const uint32_t expBits = (bitwiseRepr >> 23u) & 0xffu; // 8 bits set
        const uint32_t mntsBits = bitwiseRepr & 0x7fffffu; // 23 bits set

        // Handle some special cases:
        if(expBits == 0 && mntsBits == 0)
        {
            // special case: +0 and -0
            return {0, 1};
        }
        else if(expBits == 255u && mntsBits == 0)
        {
            // special case: +inf, -inf
            // Let's agree that infinity is always represented as 1/0 in Ratio 
            return {signBit ? -1 : 1, 0};
        }
        else if(expBits == 255u)
        {
            // special case: nan
            // Let's agree, that if we get NaN, we returns max int64_t by 0
            return {std::numeric_limits<int64_t>::max(), 0};
        }

        // mask lowest 23 bits (mantissa)
        uint32_t significand = (1u << 23u) | mntsBits;

        const int64_t signFactor = signBit ? -1 : 1;

        const int32_t exp = expBits - 127 - 23;

        if(exp < 0)
        {
            return {signFactor * static_cast<int64_t>(significand), 1u << static_cast<uint32_t>(-exp)};
        }
        else
        {
            return {signFactor * static_cast<int64_t>(significand * (1u << static_cast<uint32_t>(exp))), 1};
        }
    }
};

(hopefully comments and description above are understandable - let me know, if there's something to improve)

I've omitted checks for out of range values for simplicity.

We can use it like this:

float fv = 1.375f;
Ratio rv = Ratio::fromFloat(fv);
std::cout << "fv = " << fv << ", rv = " << rv << ", rv.toFloat() = " << rv.toFloat() << "\n";

And the output is:

fv = 1.375, rv = 11534336/8388608, rv.toFloat() = 1.375

As you can see, exactly the same values on both ends.

---

The problem is that numerators and denumerators are big. This is because the code always multiplies significand by 2^23, even if smaller value would be enough to make it integer (this is equivalent to writing 0.2 as 2000000/10000000 instead of 2/10 - it's the same thing, only written differently).

This can be solved by changing the code to multiply significand (and divide exponent) by minimum number, like this (ellipsis stands for parts which are the same as above):

// counts number of subsequent least significant bits equal to 0
// example: for 1001000 (binary) returns 3
uint32_t countTrailingZeroes(uint32_t v)
{
    uint32_t counter = 0;

    while(counter < 32 && (v & 1u) == 0)
    {
        v >>= 1u;
        ++counter;
    }

    return counter;
}

struct Ratio
{
    ...

    static Ratio fromFloat(float v)
    {
        ... 

        uint32_t significand = (1u << 23u) | mntsBits;

        const uint32_t nTrailingZeroes = countTrailingZeroes(significand);
        significand >>= nTrailingZeroes;

        const int64_t signFactor = signBit ? -1 : 1;

        const int32_t exp = expBits - 127 - 23 + nTrailingZeroes;

        if(exp < 0)
        {
            return {signFactor * static_cast<int64_t>(significand), 1u << static_cast<uint32_t>(-exp)};
        }
        else
        {
            return {signFactor * static_cast<int64_t>(significand * (1u << static_cast<uint32_t>(exp))), 1};
        }
    }
};

And now, for the following code:

float fv = 1.375f;
Ratio rv = Ratio::fromFloat(fv);

std::cout << "fv = " << fv << ", rv = " << rv << ", rv.toFloat() = " << rv.toFloat() << "\n";

We get:

fv = 1.375, rv = 11/8, rv.toFloat() = 1.375

Answer 2

In C++ you can use the Boost rational class. But you need to give numerator and denominator.

For this you need to find out no of digits in the input string after the decimal point. You can do this by string manipulation functions. Read the input character by character and find no of characters after the .

char inputstr[30]; 
int noint=0, nodec=0;
char intstr[30], dec[30];
int decimalfound = 0;
int denominator = 1;
int numerator;

scanf("%s",inputstr);

len = strlen(inputstr);

for (int i=0; i<len; i++)
{
    if (decimalfound ==0)
    {
        if (inputstr[i] == '.')
        {
            decimalfound = 1;
        }
        else
        {
            intstr[noint++] = inputstr[i];
        }
     }
     else
     {
        dec[nodec++] = inputstr[i];
        denominator *=10;
     }
}
dec[nodec] = '\0';
intstr[noint] = '\0';

numerator = atoi(dec) + (atoi(intstr) * 1000);

// You can now use the numerator and denominator as the fraction, 
// either in the Rational class or you can find gcd and divide by 
// gcd.

Answer 3

I hope I'll be forgiven for posting an answer which uses "only the C language". I know you tagged the question with C++ - but I couldn't turn down the bait, sorry. This is still valid C++ at least (although it does, admittedly, use mainly C string-processing techniques).

int num_string_float_to_rat(char *input, long *num, long *den) {
    char *tok = NULL, *end = NULL;
    char buf[128] = {'\0'};
    long a = 0, b = 0;
    int den_power = 1;

    strncpy(buf, input, sizeof(buf) - 1);

    tok = strtok(buf, ".");
    if (!tok) return 1;
    a = strtol(tok, &end, 10);
    if (*end != '\0') return 2;
    tok = strtok(NULL, ".");
    if (!tok) return 1;
    den_power = strlen(tok);  // Denominator power of 10
    b = strtol(tok, &end, 10);
    if (*end != '\0') return 2;

    *den = static_cast<int>(pow(10.00, den_power));
    *num = a * *den + b;

    num_simple_fraction(num, den);

    return 0;
}

Sample usage:

int rc = num_string_float_to_rat("0015.0235", &num, &den);
// Check return code -> should be 0!
printf("%ld/%ld\n", num, den);

Output:

30047/2000

Full example at http://codepad.org/CFQQEZkc .

Notes:

• strtok() is used to parse the input in to tokens (no need to reinvent the wheel in that regard). strtok() modifies its input - so a temporary buffer is used for safety
• it checks for invalid characters - and will return a non-zero return code if found
• strtol() has been used instead of atoi() - as it can detect non-numeric characters in the input
• scanf() has not been used to slurp the input - due to rounding issues with floating point numbers
• the base for strtol() has been explicitly set to 10 to avoid problems with leading zeros (otherwise a leading zero will cause the number to be interpreted as octal)
• it uses a num_simple_fraction() helper (not shown) - which in turn uses a gcd() helper (also not shown) - to convert the result to a simple fraction
• log10() of the numerator is determined by calculating the length of the token after the decimal point

Answer 4

What about this simple code:

double n = 1.375;
int num = 1, den = 1;
double frac = (num * 1.f / den);
double margin = 0.000001;
while (abs(frac - n) > margin){
    if (frac > n){
        den++;
    }
    else{
        num++;
    }
    frac = (num * 1.f / den);
}

I don't really tested too much, it's only an idea.

Answer 5

I'd do this in three steps.

1) find the decimal point, so that you know how large the denominator has to be.

2) get the numerator. That's just the original text with the decimal point removed.

3) get the denominator. If there was no decimal point, the denominator is 1. Otherwise, the denominator is 10^n, where n is the number of digits to the right of the (now-removed) decimal point.

struct fraction {
    std::string num, den;
};

fraction parse(std::string input) {
    // 1:
    std::size_t dec_point = input.find('.');

    // 2:
    if (dec_point == std::string::npos)
        dec_point = 0;
    else {
        dec_point = input.length() - dec_point;
        input.erase(input.begin() + dec_point);
    }

    // 3:
    int denom = 1;
    for (int i = 1; i < dec_point; ++i)
        denom *= 10;
    string result = { input, std::to_string(denom) };
    return result;
}