找到等于实数分数的自然数分数

Question

这更像是一道数学题，但我认为这里是提问的正确地点，它可能对某些人有用。

这是问题所在：

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

rA / rB = nA / nB

对于那些没有正确理解的人，问题是要求 Irreducible fraction 等于某个给定的实数。

当它成为一个精度问题时，我的问题就来了，找到这些数字需要很多时间（例如：rA = 665.32 和 rB = 875.1），我什至不知道是否有这样的数字自然数的组合来匹配问题。

我还实施了一些 KeyPress 以便您仍然可以检查 nA 和 nB 获得了多少，而无需使您的控制台已满。

我想到的最有效的方法是：

#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;
}

我的问题是：

我可以让这个算法更有效率吗？
如何将比较的precision设置为6位？
有没有办法从头判断unsigned long long范围内是否存在这样的一对？

编辑：这里有更多的例子需要太多时间来解决或无法解决。

rA = 1426.33 rB = 12.7

rA = 764342.33 rB = 98.02001

rA = 1.0001 rB = 1.010001

Answer 1

我相信这样会更有效率。

while(bPairFound == false)
{
    double left=(double)nA*rB;
    double right=(double)nB*rA;

    if(left>right){
         double quotient=left/right;
         unsigned long long prevB=nB;
         nB*=quotient;
         if(prevB==nB){
              nB++;
         }
    }else if(right>left){
         int quotient=right/left;
         unsigned long long prevA=nA;
         nA*=quotient;
         if(prevA==nA){
              nA++;
         }
    }else{
         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;
}

由于您是按商增加数字，因此您将跳过早期过程中的很多步骤。此外，此实现具有更多的乘法和更少的除法。由于乘法成本较低，因此这种方法会更有效。

希望对您有所帮助。

编辑 1：我找到了一种增加系统精度的方法

double left=(double)nA*rB;
double right=(double)nB*rA;
double quotient=left/right;
unsigned long long test;
if(quotient>=1){
   test=quotient*1000000;
}else{
   test=100000/quotient;
}
if(test==1000000){
    bPairFound = true;
}else if(left>right){
    unsigned long long prevB=nB;
    nB*=quotient;
    if(prevB==nB){
        nB++;
    }
}else if(right>left){
    unsigned long long prevA=nA;
    nA*=1/quotient;
    if(prevA==nA){
        nA++;
    }
}

Answer 2

除了精度问题^(a)，您可以通过确保数字是整数然后将它们除以最大公约数来最有效地做到这一点。

具体伪代码如：

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

在 Stack Overflow 上应该很容易找到 GCD 实现。

事实上，这里是 one I prepared earlier :-)

^(a) 可以使用任意精度的算术库解决精度问题，例如 MPIR.

找到等于实数分数的自然数分数

Finding a natural number fraction equal to a real number fraction

c++

algorithm

fractions