We have written an algorithm in C , to find the most optimum combination which yields a value closest to the one desired. Say , we have 16 different sizes of capacitor banks under my control. The user has connected banks of different sizes to these 16 stages , which I have 'sensed' and stored in non-volatile memory. During the course of my calculations , I see that the system needs X KVAR of capacitors to achieve unity PF . Now I need to find the BEST combination from those 16 stages , which will come closest to X . My method presently uses BRUTE force ; i.e. running a loop for 65535 times , each time adding all the bank values which correspond to the '1's in the loop counter and seeing if this combination is closer to the value X than the previous one. At the end of the loop , I will be left with that word combination which has given me the value closest to X .
For 65535 times ( 16 stages ) , this algorithm works well . The problem is when I want to make a bigger relay , with more control stages . Every additional bit doubles the number of times the loop will run. At 20 stages , the time on a 80 MHz ARM Controller is 500 msecs , where the key response begins to get sluggish and I lose it totally if I reach for 24 stages. Display freezes over and keys respond once in 10-12 seconds or more.
I need to find the best combination from 24 different bank sizes , which will come closest to the desired value X . Without looping forever .
Anu ideas ?
ADDITIONAL DATA : added 09.45 PM IST , 20th September.
Here is the problem in a nutshell . Say I have 4 capacitor banks , each with a value as under :
Bank1 = 2 KVAR , Bank2 = 4 KVAR , BANK3 = 7.5 KVAR and bank4=10 KVAR . I read these values and store them in an array bank . So , bank=2 ; bank=4 ; bank=7.5 and bank=10 ;
Note that these need not be in any particular order.
The prevailing system KVAR is , say , 7 KVAR lagging. That means I need to find a combination which comes closest to 7.0 .
My present algorithm looks at all possible values I can generate using the values in the array.
Since I have four banks ( in this example , in real life it is 16 presently and am trying to go 32 )..there can be 16 possible values here ,
0000 = 0 KVAR
0001 = 2 KVAR
0010 = 4 KVAR
0011 = 6 KVAR
0100 = 7.5 KVAR
0101 = 9.5 KVAR
0110 = 11.5 KVAR
0111 = 13.5 KVAR
1000 = 10 KVAR
1001 = 12 KVAR
1010 = 14 KVAR
1011 = 16 KVAR
1100 = 17.5 KVAR
1101 = 19.5 KVAR
1110 = 21.5 KVAR and finally
1111 = 23.5 KVAR
As the loop goes around 16 times , I add up the values in the array whose bit is 1 and then , as the values are generated , store the difference between generated value and target value ( i.e. 7.0 ) . If the new difference generated is lower than the one in the previous iteration of the loop , I store that in the variable lowest_ difference and also the iteration which generated this lowest difference. In this case , it would be 0100 ( generating 7.5 , thereby giving the lowest_difference=0.5 ;
I accept this and proceed further. My problem is , for an array size 16 , the loop goes around 65535 times. With the ARM microcontroller I am using presently , it gets over in less than 80 msecs. However , for array size 20 and then 24 , the controller just keeps doing the calculations for too long , missing other work. I cannot even hope to reach array size 32.
Thus , the problem is : HOW TO ARRIVE AT CLOSEST VALUE TO 7.0 ( BIT COMBINATION 0100) , WITHOUT LOOPING FOREVER ?
13 freelancers are bidding on average ₹19618 for this job
This is an optimization problem. Having experience in solving algorithmic optimization problems, I can complete the task with best efficiency constraints in minimum time.