गुणक और divisor मानों की गणना के लिए अनुकूलन एल्गोरिदम

Question

मैं एक एल्गोरिदम अनुकूलित करने की कोशिश कर रहा हूं और मैं इसे करने का बेहतर तरीका नहीं सोच सकता।

एक इनपुट (घड़ी घड़ी आवृत्ति मान) है जो गुणक और divisors के संयोजन के माध्यम से जाना होगा।

• लक्ष्य गुणक और विभाजक मूल्यों का सेट ढूंढना है जो इनपुट के अनुसार वांछित आउटपुट मान का उत्पादन करेंगे।

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

है किसी भी इसे अनुकूलित करने का तरीका? या कुछ एल्गोरिदमिक दृष्टिकोण का उपयोग करें?

मैं सी का उपयोग कर रहा हूं, लेकिन किसी भी प्रकार का छद्म कोड मेरे साथ ठीक है।

संपादित करें: स्पष्टीकरण के लिए कुछ उदाहरण। यह 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 प्राप्त करने में परिणाम होगा साथ गुणक का कोई संयोजन है।

Answer 1

सूत्र पुन: क्रम में, हम

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.

और विभाजन के बाद इनकल्क में क्या छोड़ा गया है, हम इसे प्रत्येक 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, हम और झूठे सच लौटने के लिए,।

समय जटिलता है हे (एन) n के साथ, सभी mul1_vals में तत्वों की अधिकतम संख्या है ...