計算乘數和除數值的優化算法

我想優化一個算法，我想不出一個更好的方法來做到這一點。計算乘數和除數值的優化算法

有一個輸入（時鐘頻率值）將經過乘法器和除數的組合。

目標是找到一組乘數和除數值，它們將在給定輸入的情況下產生所需的輸出值。

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可用值的組合。

來源

2015-06-05 user2162449

你能給所需的輸入和輸出的幾個例子？爲什麼特定的乘數和除數顯着？五個嵌套for循環看起來非常暴躁，但更詳細的問題規範將有助於確定是否有更高效的算法。 – paisanco

你有什麼比較基準嗎？一些編譯器開關可能會比人們可以做的更好地進行優化 – Alejandro

@paisanco所需的乘數和除數是具有物理限制的物理電子元件。我同意這是非常暴力的，這就是爲什麼我尋求幫助，因爲我無法弄清楚。 – user2162449

重新排列的公式，我們有

OutClk/(Mult1*Mult2*Mult3) = InClk/(Div1*Div2);

看看的Mult1 = {1, 2}和Mult2 = {1, 2, 4, 8}，請注意，它們是兩種一切權力。
同樣，與Div1和Div2，他們也是兩個冪。
Mult3 = {3,5,7}，它們都是素數。

所以，我們需要做的是他們最大的共同分頻器分兩個INCLK和OutClk（GCD）

int g = gcd(InClk, OutClk); 

InClk /= g; 

OutClk/= g;

爲了InClk == OutClk，我們需要做兩InClk/g和OutClk/g等於1.

InClk在劃分後剩下什麼，我們試圖用InClk可以劃分的每個div_vals中的最大元素進行劃分。（因爲div_vals中的每個元素都是兩個冪，所以我們需要挑選最大的）。

for(int i = sizeof(div1_vals) - 1; i>= 0; i--) 
    if(InClk % div1_vals[i] == 0){ 
     InClk/= div1_vals[i]; 
     break; 
    } 

for(int i = sizeof(div2_vals) - 1; i>= 0; i--) 
    if(InClk % div2_vals[i] == 0){ 
     InClk/= div2_vals[i]; 
     break; 
    }

同樣，對於OutClk

for(int i = sizeof(mul1_vals) - 1; i>= 0; i--) 
    if(OutClk % mul1_vals[i] == 0){ 
     OutClk/= mul1_vals[i]; 
     break; 
    } 
....

最後，如果InClk == 1 and OutClk == 1，我們返回true，否則爲false。

時間複雜度爲O（n）的其中n是所有mul1_vals元素的最大數量，...

來源

2015-06-05 06:19:11

計算乘數和除數值的優化算法

回答

相關問題