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 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-oopg2xiWS6UcBL0E%2BsjdjB89-TvmDFqdKptGP1U6J19Q%40mail.gmail.com.
