Cheap algorithm to find measure of angle between v

Question

Finding the angle between two vectors is not hard using the cosine rule. However, because I am programming for a platform with very limited resources, I would like to avoid calculations such as sqrt and arccos. Even simple divisions should be limited as much as possible.

Fortunately, I do not need the angle per se, but only need some value that is proportional to said angle.

So I am looking for some computationally cheap algorithm to calculate a quantity that is related to the angle between two vectors. So far, I haven't found something that fits the bill, nor have I been able to come up with something myself.

Answer 1

Have you tried a CORDIC algorithm? It's a general framework for solving polar ↔ rectangular problems with only add/subtract/bitshift + table, essentially doing rotation by angles of the form tan^-1 (2^-n). You can trade off accuracy with execution time by altering the number of iterations.

In your case, take one vector as a fixed reference, and copy the other to a temporary vector, which you rotate using the cordic angles towards the first vector (roughly bisection) until you reach a desired angular accuracy.

(edit: use sign of dot product to determine at each step whether to rotate forward or backward. Although if multiplies are cheap enough to allow using dot product, then don't bother with CORDIC, perhaps use a table of sin/cos pairs for rotation matrices of angles π/2ⁿ to solve the problem with bisection.)

(edit: I like Eric Bainville's suggestion in the comments: rotate both vectors towards zero and keep track of the angle difference.)

Answer 2

The dot product might work in your case. It's not proportional to the angle, but "related".

Answer 3

Here on SO I still don't have the privilege to comment (though I have at math.se) so this is actually a reply to Timo's post on diamond angles.

The whole concept of diamond angles based on the L1 norm is most interesting and if it were merely a comparison of which vector has a greater/lesser w.r.t. the positive X axis it would be sufficient. However, the OP did mention angle between two generic vectors, and I presume the OP wants to compare it to some tolerance for finding smoothness/corner status or sth like that, but unfortunately, it seems that with only the formulae provided on jsperf.com or freesteel.co.uk (links above) it seems it is not possible to do this using diamond angles.

Observe the following output from my Asymptote implementation of the formulae:

Vectors : 50,20 and -40,40
Angle diff found by acos      : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond         : 1.21429
Convert that to degrees       : 105.255
Rotate same vectors by 30 deg.
Vectors : 33.3013,42.3205 and -54.641,14.641
Angle diff found by acos      : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond         : 1.22904
Convert that to degrees       : 106.546
Rotate same vectors by 30 deg.
Vectors : 7.67949,53.3013 and -54.641,-14.641
Angle diff found by acos      : 113.199
Diff of angles found by atan2 : 113.199
Diamond minus diamond         : 1.33726
Convert that to degrees       : 116.971

So the point is you can't do diamond(alpha)-diamond(beta) and compare it to some tolerance unlike you can do with the output of atan2. If all you want to do is diamond(alpha)>diamond(beta) then I suppose diamond is fine.