Optimization algorithm for calculating multiplier and divisor values

Question

I am trying to optimize an algorithm and I cannot think of a better way to do this.

There is one input (clock frequency) that will go through a combination of multipliers and dividers.

• The goal is to find a set of multiplier and divisor values ​​that will produce the desired output value, given the input.

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

My current (naive?) Implementation:

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

Is there any way to optimize this? Or use some algorithmic approach?

I use C, but any pseudo code with me is suitable.

EDIT: Some examples for clarification. This will return 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 

This will return false :

 exists_mults_divs(2000000, 999999999); 

Since there is no combination of divisor and factor with the available values, which will result in 999999999 .

Answer 1

Reordering the formula, we have

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

• Take a look at Mult1 = {1, 2} and Mult2 = {1, 2, 4, 8} , note that they all have the power of two.

• Similarly, with Div1 and Div2 , they also have the power of two.

• Mult3 = {3,5,7} , which are all primes.

So what we need to do is split both InClk and OutClk into their largest common divisor (GCD)

 int g = gcd(InClk, OutClk); InClk /= g; OutClk/= g; 

For InClk == OutClk we need to make both InClk/g and OutClk/g equal to 1.

And what remains of InClk after the division, we will try to divide it into the largest element in each div_vals , which InClk can divide. (Since each element in div_vals everything has a power of two, so we need to choose the largest).

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

Similarly for OutClk

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

In the end, if InClk == 1 and OutClk == 1 , we will return true, else false.

The complexity of the time is O (n) , where n is the maximum number of elements in all mul1_vals, ...