分子分母范围受限的实数有理近似算法求解（IC测试时钟场景）

我正在学习分子、分母同时存在约束的实数有理近似求解方法，目前查阅了诸多资料，了解了连分数法、Farey序列、Stern-Brocot树等实现方案，但现有公开示例均仅支持单独约束分子或分母其中一项。

应用场景 #

我目前从事混合信号IC测试工作，其中一项测试需要测定IC的最高工作频率：初始给IC输入12 MHz的时钟，之后逐步降低时钟频率，直到IC可以正常运行简单数字序列。
测试平台的主时钟可调范围为25~66 MHz，时钟设置函数接收double类型参数。当前测试版本将主时钟固定为50.0 MHz，通过循环调用分频函数调整输出频率，分频系数为1~4096之间的整数。

但该方案存在测量精度不足的问题：当前测试中器件总是只能在以下档位通过测试：

• 50 / 5 = 10 Mhz
• 50 / 6 = 8.333 MHz

为了提升测量精度，我希望每次循环迭代时可以同时调整主时钟频率和分频系数，因此需要实现同时约束分子、分母的类连分数近似算法，预期调用逻辑如下：

while(dFmax > dFmin)
{
    std::pair<double, int> bestSettings = GetBestClkSettings(dFmax);
    double dFreq = bestSettings.first;
    int iDiv = bestSettings.second;

    // Set up clock and timesets        
    clkset(dFreq);
    clkdivide(iDiv);

    // Run pattern
    // ...
    
    // Get results
    // ...
    
    dFmax -= 0.1;
}

我花了数小时调试相关代码，还尝试编写了类二分查找的逻辑验证思路，我知道当前的代码存在缺陷无法达到目标，仅用来展示已做过的相关尝试，代码如下：

#include <iostream>
#include <stdio.h>
#include <cmath>

struct fraction {
    int n;
    int d;
    
    fraction()
    {
        this->n = -1;
        this->d = -1;
    }
    fraction(int n, int d)
    {
        this->n = n;
        this->d = d;
    }
    
    double asDouble()
    {
        double dReal = static_cast<double>(n) / static_cast<double>(d);
        return dReal;
    }
};

fraction ApproximateFrequency(double dTargetFreqMHz, double dTol)
{
    fraction result;
    
    if (dTargetFreqMHz < (25.0 / 4096) || dTargetFreqMHz > 66.0)
    {
        return result;
    }
    else if (dTargetFreqMHz >= 25.0 && dTargetFreqMHz <= 66.0)
    {
        result.n = static_cast<int>(dTargetFreqMHz);
        result.d = 1;
        return result;
    }

    int iFrqLo = 25;
    int iFrqHi = 66;
    int iDivLo = 1;
    int iDivHi = 4096;

    int iFrqCurr = (iFrqLo + iFrqHi) / 2;
    int iDivCurr = (iDivLo + iDivHi) / 2;
    double dFreq = static_cast<double>(iFrqCurr) / static_cast<double>(iDivCurr);
    double dPrevFreq = 0;
    int iNumIters = 1;
    
    while (fabs(dTargetFreqMHz - dFreq) > dTol && fabs(dFreq - dPrevFreq) > 1e-8 && iNumIters < 25)
    {
        dPrevFreq = dFreq;
        
        if (dFreq < dTargetFreqMHz)
        {
            // 需提升频率
            // 方案1：提高主时钟频率
            int iFrqNew = (iFrqCurr + iFrqHi) / 2;
            double dFrqIfClkInc = static_cast<double>(iFrqNew) / static_cast<double>(iDivCurr);
            double dClkIncDiff = fabs(dTargetFreqMHz - dFrqIfClkInc);
            
            // 方案2：降低分频系数
            int iDivNew = (iDivLo + iDivCurr) / 2;
            double dFrqIfDivDec = static_cast<double>(iFrqCurr) / static_cast<double>(iDivNew);
            double dDivDecDiff = fabs(dTargetFreqMHz - dFrqIfDivDec);
            
            // 选择效果更好的方案
            if (dClkIncDiff < dDivDecDiff && iFrqNew >= 25 && iFrqNew <= 66)
            {
                iFrqCurr = iFrqNew;
            }
            else if (dDivDecDiff < dClkIncDiff && iDivNew >= 1 && iDivNew <= 4096)
            {
                iDivCurr = iDivNew;
            }
        }
        else
        {
            // 需降低频率
            // 方案1：降低主时钟频率
            int iFrqNew = (iFrqLo + iFrqCurr) / 2;
            double dFrqIfClkDec = static_cast<double>(iFrqNew) / static_cast<double>(iDivCurr);
            double dClkDecDiff = fabs(dTargetFreqMHz - dFrqIfClkDec);
            
            // 方案2：提高分频系数
            int iDivNew = (iDivCurr + iDivHi) / 2;
            double dFrqIfDivInc = static_cast<double>(iFrqCurr) / static_cast<double>(iDivNew);
            double dDivIncDiff = fabs(dTargetFreqMHz - dFrqIfDivInc);
            
            // 选择效果更好的方案
            if (dClkDecDiff < dDivIncDiff && iFrqNew >= 25 && iFrqNew <= 66)
            {
                iFrqCurr = iFrqNew;
            }
            else if (dDivIncDiff < dClkDecDiff && iDivNew >= 1 && iDivNew <= 4096)
            {
                iDivCurr = iDivNew;
            }
        }
        
        // 输出当前设置对应的频率
        dFreq = static_cast<double>(iFrqCurr) / static_cast<double>(iDivCurr);
        std::cout << "prev = " << dPrevFreq << ", current = " << dFreq << std::endl;
        iNumIters++;
    }
    
    result.n = iFrqCurr;
    result.d = iDivCurr;
    return result;
}

int main(int argc, char* argv[])
{
    double dTargetFreqMHz = 20.0;
    std::cout << "Target: " << dTargetFreqMHz << "\n\n";
    double dTol = 0.05;
    fraction mcf = ApproximateFrequency(dTargetFreqMHz, dTol);
    printf("tol=%f, n/d = %d/%d = %f (err=%f)\n", dTol, mcf.n, mcf.d, mcf.asDouble(), mcf.asDouble()-dTargetFreqMHz);
}

恳请各位提供相关建议或思路指引，非常感谢。

内容的提问来源于stack exchange，提问作者szojss62