Friday 22 July 2016

algorithms - Best Approach to Rank Complex Magnitude Comparision Problem


This is in reference to the responses for an efficient algorithm for the comparison of bounded fixed point complex numbers at this post.


Efficient Magnitude Comparison for Complex Numbers


See the details of that post for the objectives of the problem. I am now determining my approach to ranking the algorithms to determine who best met the objectives I was seeking, and welcome debate on the ranking approach before I dive in.



Key qualifying factors:


I will baseline a standard CORDIC approach (rotate both vectors to real axis and compare absolute magnitude), as well as what can be done with the use of multiplier operations. The algorithm must be more efficient than either of these approaches (using the equivalent score for the multipliers - see below).


Algorithm must be 100% correct for for magnitude differences within $|z_2- z_1| \gt e$ for any e, where Where $z_n = \sqrt{I_n^2 + Q_n^2}$ with I and Q as bounded signed integers and e is any positive real number>0. (it is understood that it will likely take more operations as e decreases; in fact it would be attractive to be more efficient for large e). The CORDIC is a good example of this, you can select any error bound at the expense of the number of iterations needed.


Acceptable answers may return incorrect results for $|z_2- z_1| \le e$, but a bonus score is included for implementations that provide equivalence resolutions given by the following definitions, with a higher score for tight equivalence:


Loose Equivalence:


$|z_1| \gt |z_2| + e$ returns 1


$|z_1| \lt |z_2| -e$ returns -1


$|z_2- z_1| \le e$ returns 0


Tight Binary Equivalence:


$|z_1| > |z_2|$ returns 1



$|z_1| < |z_2|$ returns -1


Tight Ternary Equivalence:


$|z_1| > |z_2|$ returns 1


$|z_1| < |z_2|$ returns -1


$|z_1| = |z_2|$ returns 0


The function prototype is


result = CompareMagntitudes( I1, Q1, I2, Q2 )

With return values of either $-1,0,1$ corresponding to $<, =, > $ of the first compared to the second (and $0, 1$ for $<, \ge$ for binary solutions).


Test cases will be run with bit ranges from $b = 8$ to $b = 32$ bits for I and Q but nothing in the algorithm should prevent implementation with any size b.



Consider the following closely spaced complex points A, B, C, D as depicted in the diagram below ($A=3+j4$, $B=4+j4$, $C=3+j5$, $D4+j5$).


Cartesian Grid


The true radii are A = 5, B =5.66, C = 5.83 and D = 6.403. In this case, the algorithm should provide a solution to resolve all 4 with 100% confidence (setting e to be $e \le 0.17$ corresponding to the minimum distance between B and C), however it would be acceptable and even beneficial if the algorithm allowed for larger e with an associated efficiency gain.


For example if $e=0.5$ then the following results must be returned using the format $f(z_1,z_2)$ with relation to the function prototype given above:


$f(A,B) \rightarrow -1$


$f(C,A) \rightarrow 1$


$f(A,D) \rightarrow -1$


$f(B,D) \rightarrow -1$


Since all those points have a difference in magnitude from the origin > 0.5.


However the following would be acceptable:



$f(B,C) \rightarrow X$


Where X can be 1, 0 or -1 since B and C have a difference in magnitude from teh origin < 0.5.


The algorithm must be implementable with only the equivalent of standard Boolean operations, binary shifts and compares. Look-up tables if used would add to buffer size considerations in the scoring.


QUESTION: Please suggest / justify alternative metrics (including alternate scoring the starting numbers I list in my answer, or completely different approaches. It is understood that ultimately there is a trade space and can't be a one size fits all simple score, so consideration is weighted toward the objectives in the original question.




No comments:

Post a Comment

readings - Appending 内 to a company name is read ない or うち?

For example, if I say マイクロソフト内のパートナーシップは強いです, is the 内 here read as うち or ない? Answer 「内」 in the form: 「Proper Noun + 内」 is always read 「ない...