Hello Bartek- I am happy to have been wrong here. Your changes look to be very promising.
I'd recommend adding them as a MR to the KiCad source code and we can do a full review. Seth [image: KiCad Services Corporation Logo] Seth Hillbrand *Lead Developer* +1-530-302-5483 Long Beach, CA www.kipro-pcb.com [email protected] On Thu, Aug 3, 2023 at 8:28 AM [email protected] <[email protected]> wrote: > I implemented that algorithm (without any pre-computation in source) and > I'm quite optimistic. Benchmark results (on mobile i7-3610QM) are: > - 4R E12 - about 3ms > - 4R E24 - about 12ms > - 4R E96 - about 150ms > - 4R E192 - about 500ms > > My fork with the implementation is at > https://gitlab.com/bwaclawik/kicad/-/tree/new-resistor-substitution-algorithm > > wtorek, 25 lipca 2023 o 21:55:14 UTC+2 [email protected] napisał(a): > >> You will probably gain by pre-computing 2COMB and storing the values in >> the source. However, this would be quite large above E96 and would not be >> realistic to store. You could pre-compute in source to reduce the time >> after the first calculation. >> >> I'm skeptical of the gains to be made by this approach. Because 'n' is >> never very large, your greatest time sink is going to be in the prefactor. >> While the work may be of the order 'n', the multiplicative prefactor will >> dominate. >> >> For that reason, if you are interested in improving the algorithm, I >> would look at early escape metrics in the loops. We end up checking many >> value combinations that we do not need and some smarter heuristics here >> will have outsized impact. >> >> That said, if you have your heart set on the approach you laid out, I >> don't see the harm in testing it. >> >> Seth >> >> [image: KiCad Services Corporation Logo] >> Seth Hillbrand >> *Lead Developer* >> +1-530-302-5483 <(530)%20302-5483> >> Long Beach, CA >> www.kipro-pcb.com [email protected] >> >> >> On Tue, Jul 25, 2023 at 11:15 AM bebidek <[email protected]> wrote: >> >>> I would like to improve the performance of the "E-series" tool in the >>> PCB calculator. >>> At the moment, the solution implemented in the code is basically a >>> brute-force algorithm, reaching O(n^4) time complexity (where n is the >>> number of basic resistance values). >>> It can be easily improved to O(n^2 * log(n)) using a binary search >>> approach, keeping current memory complexity of O(n^2). >>> The draft of the new algorithm is as follows ('X' means "+ or |", 2COMB >>> means "some combination of 2 resistors"): >>> 1. Prepare an array of all combinations of two resistors (that is, >>> all possible values of 2COMB) and sort it >>> 2. For 2-solutions, use single binary search in our array to find >>> the two closest values (one less and one greater) >>> 3. For 3-solutions, all possible variants are of the form: "R1 X >>> 2COMB". Thus, we iterate over all values of R1, for each value calculate >>> "perfect" values of that combination in parenthesis and look for it >>> (bin-search) in the array. >>> 4. For 4-solutions, it is either "(2COMB X 2COMB)", "R1 + (R2 | >>> 2COMB)" or "R1 | (R2 + 2COMB)". The first one can be solved by iterating >>> over 2COMB array, the second and third one by iterating over pairs (R1, R2). >>> >>> Switching to this algorithm should make adding higher E-series possible >>> (some people in other threads have suggested this, but performance issues >>> made it impractical). >>> I believe that this algorithm is not too far from the most optimal >>> possible. The problem of finding "series only" combinations is basically a >>> 3-SUM problem for which we believe there is no O(n^a) algorithm for a<2 >>> (the "3-SUM hypothesis"). It appears that finding general solutions should >>> be at least that hard. >>> Additional benefit of that algorithm is that it correctly considers all >>> possible combinations of up to 4 resistors, unlike the current one which >>> cannot produce results of form R1 + (R2 | R3 | R4). >>> >>> I would like to implement that algorithm if approved. It would involve >>> rewriting RES_EQUIV_CALC class almost from scratch (this would also fix >>> some code quality issues in the current implementation). >>> >>> -- >>> You received this message because you are subscribed to the Google >>> Groups "KiCad Developers" group. >>> To unsubscribe from this group and stop receiving emails from it, send >>> an email to [email protected]. >>> To view this discussion on the web visit >>> https://groups.google.com/a/kicad.org/d/msgid/devlist/f204c4cf-b90c-460c-a59d-7f593cab37f5n%40kicad.org >>> <https://groups.google.com/a/kicad.org/d/msgid/devlist/f204c4cf-b90c-460c-a59d-7f593cab37f5n%40kicad.org?utm_medium=email&utm_source=footer> >>> . >>> >> -- You received this message because you are subscribed to the Google Groups "KiCad Developers" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To view this discussion on the web visit https://groups.google.com/a/kicad.org/d/msgid/devlist/CAFdeG-o%3DLx1KijzL%3DuA-3BrCdM1ZVtG73%3D%3DduXOwt64SeiOp5Q%40mail.gmail.com.
