Search code examples
c++algorithmfractions

Finding a natural number fraction equal to a real number fraction

This is more like a math problem but i think here is the rights place to ask and it might be usefull to someone.

Here is what the problem is asking for:

Given two real numbers (rA and rB) find the smallest two natural numbers (nA and nB) so that

rA / rB = nA / nB

For those who did not understand properly, the problem is asking for an Irreducible fraction that is equal to some given real number.

My problem arrives when it becomes a precision problem and it takes a lot of time to find those numbers (Ex: rA = 665.32 and rB = 875.1) and i dont even know if there is such a combination of natural number to match the problem.

I also implemented a little KeyPress so that you can still check how much nA and nB got without making your console full.

The most efficient way i came up is:

#include <iostream>
#include <windows.h> // just for GetAsyncKeyState()

int main()
{
    /** The two natural numbers*/
    unsigned long long nA=1;
    unsigned long long nB=1;

    /** The two real numbers*/
    double rA;
    double rB;

    std::cin >> rA >> rB;

    bool bPairFound = false;

    /** The maximum of which nA or nB could go. */
    /** If the value is set to 0, the algorithm will stop when nA or nB overflows */
    #define NUMBER_LIMIT 0x0

    if ((double) nA / nB == rA / rB) bPairFound = true;

    while(bPairFound == false)
    {
        if ((double) nA / nB > rA / rB) nB++;
        if ((double) nA / nB < rA / rB) nA++;
        if ((double) nA / nB == rA / rB) bPairFound = true;

        /** A little keyPress that will show you how much nA and nB got. */
        /** Press space while the program is running. */
        if (GetAsyncKeyState(VK_SPACE) & 0x8000)
            std::cout << "nA: "<<nA<<"   nB: " << nB << "  ---> "<< (double) nA / nB << "   " << rA / rB << std::endl;

        if (nA <= NUMBER_LIMIT || nB <= NUMBER_LIMIT) break;
    }

    if (bPairFound == false) std::cout << "No pair could be found in the set limit." << std::endl;
    if (bPairFound == true) std::cout << "nA: "<<nA<<"   nB: " << nB << std::endl;
    return 0;
}

My questions are:

  1. Can i make this algorithm more efficient?

  2. How can i set the precision of the comparrison to 6 digits?

  3. Is there any way to determine from the start if there is such a pair inside unsigned long long range?

EDIT: Here are some more examples that take too much time to solve or are unsolvable.

rA = 1426.33 rB = 12.7

rA = 764342.33 rB = 98.02001

rA = 1.0001 rB = 1.010001

Solution

  • Other than precision issues(a), you can do this most efficiently simply by ensuring the numbers are integers and then dividing them both by the greatest common divisor.

    Specifically, pseudo-code such as:

    tA = rA
tB = rB
while tA != int(tA) or tB != int(tB):
    tA = tA * 10
    tB = tB * 10
gcd = calcGcd(tA, tB)
nA = tA / gcd
nB = tB / gcd

    GCD implementations should be fairly easy to find here on Stack Overflow.

    In fact, here's one I prepared earlier :-)

    (a) Precision issues can be solved by using an arbitrary-precision arithmetic library such as MPIR.