我想优化一个算法,我想不出一个更好的方法来做到这一点。计算乘数和除数值的优化算法
有一个输入(时钟频率值)将经过乘法器和除数的组合。
- 目标是找到一组乘数和除数值,它们将在给定输入的情况下产生所需的输出值。
OutClk =(INCLK * MULT1 * MULT2 * Mult3 * Mult4/Div1构成)/ Div2的
我现在的(幼稚?)实现:
#define PRE_MIN 10000000
#define PRE_MAX 20000000
// Available values of the multipliers and divisors.
uint8_t mult1_vals[] = {1, 2};
uint8_t mult2_vals[] = {1, 2, 4, 8};
uint8_t mult3_vals[] = {3, 5, 7};
uint8_t div1_vals[] = {1, 2, 4};
uint8_t div2_vals[] = {1, 2, 4, 8};
bool exists_mults_divs(uint32_t in_val, uint32_t out_val)
{
uint8_t i_m1, i_m2, i_m3, i_d1, i_d2;
uint32_t calc_val;
for (i_m1 = 0; i_m1 < sizeof(mult1_vals); i_m1++) {
for (i_m2 = 0; i_m2 < sizeof(mult2_vals); i_m2++) {
for (i_m3 = 0; i_m3 < sizeof(mult3_vals); i_m3++) {
for (i_div1 = 0; i_div1 < sizeof(div1_vals); i_div1++) {
calc_val = in_val * (mult1_vals[i_m1] * mult2_vals[i_m2] *
mult3_vals[i_m3]/div1_vals[i_div1]);
if ((calc_val <= PRE_MIN) || (calc_val > PRE_MAX))
continue; // Can this be refactored?
for (i_div2 = 0; i_div2 < sizeof(div2_vals); i_div2++) {
calc_val /= div2_vals[i_div2];
if (calc_val == out_val)
return true;
}
}
}
}
}
// No multiplier/divisor values found to produce the desired out_val.
return false;
}
有什么如何优化这个?或者使用一些算法方法?
我正在使用C,但任何类型的伪代码都可以。
编辑: 澄清的一些例子。这将返回true
:
exists_mults_divs(2000000, 7000000); // in=2000000, out=7000000
// Iterating over the values internally:
// 1. in * 1 * 1 * 3/1 = 6000000
// 6000000 is not within PRE_MIN/MAX range of 10-20000000.
// 2. in * 1 * 1 * 5/1 = 10000000 is within range, try varying div2
// 2a. div2=1 => 10000000/1 = 10000000 != 7000000 not desired out
// 2b. div2=2 => 10000000/2 = 50000000 != 7000000
// etc.
// 3. in * 1 * 1 * 7/1 = 7000000 not within range
// etc.
// 4. in * 1 * 2 * 7/1 = 14000000 is within range, try varying div2
// 4a. div2=1 => 14000000/1 != 7000000
// 4b. div2=2 => 14000000/2 == 7000000 IS desired out
//
// RETURN RESULT:
// TRUE since a 2000000 in can generate a 7000000 out with
// mult1=1, mult2=2, mult3=7, div1=1, div2=2
这将返回false
:
exists_mults_divs(2000000, 999999999);
因为没有除数和乘数,这将导致在获得999999999
可用值的组合。
你能给所需的输入和输出的几个例子?为什么特定的乘数和除数显着?五个嵌套for循环看起来非常暴躁,但更详细的问题规范将有助于确定是否有更高效的算法。 – paisanco
你有什么比较基准吗?一些编译器开关可能会比人们可以做的更好地进行优化 – Alejandro
@paisanco所需的乘数和除数是具有物理限制的物理电子元件。我同意这是非常暴力的,这就是为什么我寻求帮助,因为我无法弄清楚。 – user2162449