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.
