我正在嘗試學習如何在分子和分母都受到約束的情況下找到實數的有理近似。我現在已經看了很多頁，包括以下兩頁，并且了解了連分數法、Farey 數列和 Stern-Brocot 樹。但是，在所有這些示例中，分子或分母都不受約束。
將小數簡化為分數的演算法
https://gist.github.com/mikeando/7073d62385a34a61a6f7
這是我的情況：
我正在測驗混合信號 IC。
在我們的一項測驗中，為了找到 IC 的最大作業頻率，進入 IC 的時鐘信號設定為 12 MHz 并不斷降低，直到 IC 能夠運行簡單的數字序列。
測驗平臺的主時鐘范圍為 25 到 66 MHz，設定它的功能需要加倍。
在當前版本的測驗中，它被設定為恒定的 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);
}
任何建議或提示將不勝感激。先感謝您。
uj5u.com熱心網友回復：
由于您的范圍如此有限，您可以暴力破解它。只有 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 >= 25.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 引數，因此您可以擺脫它。
轉載請註明出處，本文鏈接：https://www.uj5u.com/gongcheng/347687.html
下一篇：用于排序的重新洗牌次數