我正在尝试学习当分子和分母都受到约束时如何找到实数的有理近似值。我现在已经看了很多页，包括以下两页，并了解了连分式方法、Farey 序列和 Stern-Brocot 树。然而，在所有这些示例中，分子或分母都不受约束。
Algorithm for simplifying decimal to fractions
https://gist.github.com/mikeando/7073d62385a34a61a6f7
这是我的情况:
我正在测试混合信号 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>
// The fraction struct and the main() function were largely taken from:
// https://gist.github.com/mikeando/7073d62385a34a61a6f7
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)
{
// The frequency needs to be increased.
// The clock frequency could be increased:
int iFrqNew = (iFrqCurr + iFrqHi) / 2;
double dFrqIfClkInc = static_cast<double>(iFrqNew) / static_cast<double>(iDivCurr);
double dClkIncDiff = fabs(dTargetFreqMHz - dFrqIfClkInc);
// Or the divider could be decreased:
int iDivNew = (iDivLo + iDivCurr) / 2;
double dFrqIfDivDec = static_cast<double>(iFrqCurr) / static_cast<double>(iDivNew);
double dDivDecDiff = fabs(dTargetFreqMHz - dFrqIfDivDec);
// Find the option that produces a better result:
if (dClkIncDiff < dDivDecDiff && iFrqNew >= 25 && iFrqNew <= 66)
{
iFrqCurr = iFrqNew;
}
else if (dDivDecDiff < dClkIncDiff && iDivNew >= 1 && iDivNew <= 4096)
{
iDivCurr = iDivNew;
}
}
else
{
// The frequency needs to be decreased.
// The clock frequency could be decreased:
int iFrqNew = (iFrqLo + iFrqCurr) / 2;
double dFrqIfClkDec = static_cast<double>(iFrqNew) / static_cast<double>(iDivCurr);
double dClkDecDiff = fabs(dTargetFreqMHz - dFrqIfClkDec);
// Or the divider could be increased:
int iDivNew = (iDivCurr + iDivHi) / 2;
double dFrqIfDivInc = static_cast<double>(iFrqCurr) / static_cast<double>(iDivNew);
double dDivIncDiff = fabs(dTargetFreqMHz - dFrqIfDivInc);
// Find the option that produces a better result:
if (dClkDecDiff < dDivIncDiff && iFrqNew >= 25 && iFrqNew <= 66)
{
iFrqCurr = iFrqNew;
}
else if (dDivIncDiff < dClkDecDiff && iDivNew >= 1 && iDivNew <= 4096)
{
iDivCurr = iDivNew;
}
}
// See the frequency attainable with the current settings
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);
}
任何建议或提示将不胜感激。预先感谢您。
最佳答案
由于你的范围如此有限，你只能暴力破解。只有 172,032 种可能的分子和分母组合需要检查。通过从 25 迭代到 66 并计算最接近的两个分母，可以使算法更加高效，在这种情况下，您只需检查 84 种可能性:
fraction ApproximateFrequency(double dTargetFreqMHz, double dTol)
{
fraction result;
if (dTargetFreqMHz < (25.0 / 4096) || dTargetFreqMHz > 66.0)
{
return result;
}
else if (dTargetFreqMHz >= 33.0 && dTargetFreqMHz <= 66.0)
{
result.n = static_cast<int>(dTargetFreqMHz);
result.d = 1;
return result;
}
double smallestError = 66.0;
int closestNum = 0;
int closestDenom = 0;
for (int num = 25; num <= 66; num++)
{
int denom = floor((double)num / dTargetFreqMHz);
if (denom >= 1 && denom <= 4096)
{
double freq = (double)num / double(denom);
double err = fabs(dTargetFreqMHz - freq);
if (err < smallestError)
{
closestNum = num;
closestDenom = denom;
smallestError = err;
}
if (denom <= 4095)
{
freq = (double)num / double(denom + 1);
err = fabs(dTargetFreqMHz - freq);
if (err < smallestError)
{
closestNum = num;
closestDenom = denom + 1;
smallestError = err;
}
}
}
}
result.n = closestNum;
result.d = closestDenom;
return result;
}
未使用 dTol 参数，因此您可以将其删除。
关于c++ - 当分子和分母都具有受限范围时找到实数的有理近似，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/69832929/