Çarpan ve bölme değerlerini hesaplamak için optimizasyon algoritması

Question

Bir algoritmayı optimize etmeye çalışıyorum ve bunu yapmanın daha iyi bir yolunu düşünemiyorum.

Bir çarpan ve bölme birimi kombinasyonundan geçecek bir giriş (saat frekansı değeri) var.

• Amaç, girdi verildiğinde istenen çıktı değerini üretecek olan çarpan ve bölme değerleri kümesini bulmaktır.

OutClk = (InClk * Mult1 * Mult2 * Mult3 * Mult4/div1)/DIV2

Bulunduğum (saf?) Uygulaması olan:

#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; 
} 

mi var herhangi Bunu optimize etmenin yolu? Ya da bazı algoritmik yaklaşımları kullanın?

C kullanıyorum ama herhangi bir tür sahte kod benimle tamam.

EDIT: Açıklama için bazı örnekler. Bu true döndürür: Bu false dönecektir

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 

:

exists_mults_divs(2000000, 999999999); 

999999999 almasını sağlayacağı mevcut değerlerle bölen ve çarpan hiçbir söz yok çünkü.

Answer 1

formülü yeniden sıralama, biz

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

• Mult1 = {1, 2} ve Mult2 = {1, 2, 4, 8} bir göz atın var, fark, onların ikisinin tüm güç vardır. Benzer şekilde

• ile Div1 ve Div2, iki aynı zamanda güç. Tüm asal sayıları olan

• Mult3 = {3,5,7},

. InClk == OutClk için Amacıyla

Ee, ne yapmamız gereken onların en büyük ortak böleni ile InClk ve OutClk hem bölmektir (GCD)

int g = gcd(InClk, OutClk); 

InClk /= g; 

OutClk/= g; 

, biz hem InClk/g ve OutClk/g eşit yapmak gerekir 1.

Ve InClk'de bölmeden sonra kalanlar, her bir div_vals öğesinin en büyük öğesiyle bölmeyi deneriz. (Çünkü div_vals'daki her elemanın ikisi de güçtedir, bu yüzden en büyükini seçmemiz gerekir).Sonunda OutClk

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

için Benzer

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; 
    } 

, InClk == 1 and OutClk == 1 eğer, başka false, true döndürür.

Zaman karmaşıklığı olduğunu O (n) n ile, tüm mul1_vals elemanların sayısını olduğunu ...