Algorithm optimization / re-writing .

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[4] . So , bank[0]=2 ; bank[1]=4 ; bank[2]=7.5 and bank[3]=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.


Навыки: Программирование на С, Алгоритмы

О клиенте:
( 3 отзыв(-а, -ов) ) Vadodara, India

ID проекта: #27453609



Hello, I'm expert in C, python, Java and advanced algorithms. I have read your description an come up with idea of speeding up the algorithm. I have a M Sc degree in AI and extensive experience in problem solving, so I Больше

₹16500 INR за 7 дней(-я)
(5 отзывов(-а))

11 фрилансеров(-а) готовы выполнить эту работу в среднем за ₹18003


hiii, i think this is the second time you are posting this project , in previous project their was a lack of clearity now you come up with a clear idea , so your problem is that your code taking O(2^n) (roughly you can Больше

₹25000 INR за 3 дней(-я)
(31 отзывов(-а))

###### Having Teaching Experience in C, Python, Data structure, Algorithm Design and Analysis ######## Hi, Greetings. I am a computer engineer having masters in Mathematics, Computer Science and PhD in Computer Scien Больше

₹12500 INR за 7 дней(-я)
(26 отзывов(-а))

Hi! That's not an automated bid - your task is related to optimization of a set of capacitors. I've read the description and I am very interested in your project. I am professional C/C++ developer I have some ideas ab Больше

₹30000 INR за 7 дней(-я)
(10 отзывов(-а))

Hi there. I read your complete proposal and am interested in it. I have done similar projects before related with C programming (ANSI C languages) and combinatorial optimization, which are the skills you need to perfor Больше

₹14033 INR за 5 дней(-я)
(8 отзывов(-а))

I am embedded systems engineer with good experience in programming by using C language I can do this algorithm with complexity at the worst case n^2+(n^2)*log(n) instead of 2^n that you used this mean that for 32 banks Больше

₹12500 INR за 2 дней(-я)
(4 отзывов(-а))

Hi Please clarify some doubts about the project. Does the optimal solution require just the value closest to the required value? Or should the number of capacitors be minimized? Will the bank values be static or will Больше

₹12500 INR за 7 дней(-я)
(6 отзывов(-а))

Hello sir. Thank you for giving me a chance to bid on your project I have gone through your requirements. I have much experience in this field. I am sure that I can finish your project as you want. So please come up on Больше

₹25000 INR за 8 дней(-я)
(0 отзывов(-а))

hello i can do this project its very easy for me fast delivery trust me im waiting for you... thank you...

₹25000 INR за 7 дней(-я)
(0 отзывов(-а))

This is an optimization problem. Having experience in solving algorithmic optimization problems, I can complete the task with best efficiency constraints in minimum time.

₹12500 INR за 2 дней(-я)
(0 отзывов(-а))

Hello From my experience you can do is: A. If you know your capacitor banks ahead than: 1. Have all the results saved in memory/array in increasing order. 2. And than it is really easy way for solution B. If you do N Больше

₹12500 INR за 4 дней(-я)
(0 отзывов(-а))