### Approximating distance (alpha-max plus beta-min)

Posted:

**Mon Jun 19, 2017 11:20 pm UTC**I’ve been tinkering with the α·max + β·min approximation to the distance formula. As a quick refresher, if you know the x and y distances to some point and want to estimate the straight-line distance, you can take the dot product of ⟨x, y⟩ with an appropriately chosen vector ⟨α, β⟩. Since the dot product equals the product of the magnitudes times the cosine of the angle between the vectors, then as long as the vectors are nearly parallel and the second vector is close to unit length, the result will be approximately the magnitude of the first vector.

The “max” and “min” parts comes in when you let u = max(|x|, |y|) and v = min(|x|, |y|), so ⟨u, v⟩ is essentially ⟨x, y⟩ reflected into the lower half of the first quadrant. In other words, ⟨u, v⟩ lies along the arc from 0° to 45°. For simplicity of notation, let us call that vector u = ⟨u, v⟩. By symmetry we should choose the vector α = ⟨α, β⟩ to have angle 22.5°. Then the angle between α and u will have cosine at least cos(π/8) = ½√(2+√2) ≈ 0.924, so our estimate will be pretty good.

But what if want the best possible estimate? Well then we need to figure out the optimal length for α = c·⟨cos(π/8), sin(π/8)⟩. And we need to decide what we’ll optimize for: maximum error, root-mean-squared error, average error?

• • •

Maximum error:

RMS error:

Average error:

• • •

Now this is all well and good, but in practical use the purpose of the estimate is to speed up computation. If we have to do 2 multiplies, then we might as well just calculate the squared distance and work with that, at least for most purposes. No, the real benefit of this method comes in when we can replace the multiplies by a small number of bitshifts and adds. Specifically, we only want to multiply by powers of 2.

Numerical stuff:

• • •

Of course, we could do the same thing over other arcs besides 45°. For example, if we check whether u < 2*v then we split the 45° arc into two arcs, one from 0 to arctan(1/2) and another from arctan(1/2) to π/4. We can do similar calculations on those arcs, or any other. For an arc which subtends an angle δ, the optimal α vectors (facing the midpoint of the arc) have lengths:

c

c

c

Good approximations can be found for any particular arc of interest, though the mere act of splitting the circle into arcs entails additional comparisons. The cheapest are along the lines of (u < 2*v) or (u < 4*v).

• • •

I don’t really have a grand conclusion here, I just felt like sharing what I’ve been toying around with. If you’re looking for a challenge though, I’d appreciate having someone check my calculation for c

The “max” and “min” parts comes in when you let u = max(|x|, |y|) and v = min(|x|, |y|), so ⟨u, v⟩ is essentially ⟨x, y⟩ reflected into the lower half of the first quadrant. In other words, ⟨u, v⟩ lies along the arc from 0° to 45°. For simplicity of notation, let us call that vector u = ⟨u, v⟩. By symmetry we should choose the vector α = ⟨α, β⟩ to have angle 22.5°. Then the angle between α and u will have cosine at least cos(π/8) = ½√(2+√2) ≈ 0.924, so our estimate will be pretty good.

But what if want the best possible estimate? Well then we need to figure out the optimal length for α = c·⟨cos(π/8), sin(π/8)⟩. And we need to decide what we’ll optimize for: maximum error, root-mean-squared error, average error?

• • •

Maximum error:

**Spoiler:**

RMS error:

**Spoiler:**

Average error:

**Spoiler:**

• • •

Now this is all well and good, but in practical use the purpose of the estimate is to speed up computation. If we have to do 2 multiplies, then we might as well just calculate the squared distance and work with that, at least for most purposes. No, the real benefit of this method comes in when we can replace the multiplies by a small number of bitshifts and adds. Specifically, we only want to multiply by powers of 2.

Numerical stuff:

**Spoiler:**

• • •

Of course, we could do the same thing over other arcs besides 45°. For example, if we check whether u < 2*v then we split the 45° arc into two arcs, one from 0 to arctan(1/2) and another from arctan(1/2) to π/4. We can do similar calculations on those arcs, or any other. For an arc which subtends an angle δ, the optimal α vectors (facing the midpoint of the arc) have lengths:

c

_{max}= 2 / (1 + cos(δ/2)) = sec^{2}(δ/4)c

_{rms}= 2 / ((δ/2)/sin(δ/2) + cos(δ/2)) = 4·sin(δ/2) / (δ + sin(δ)c

_{avg}= 2 / √(3 + cos(δ/2)) =2 / √(4 − sin^{2}(δ))Good approximations can be found for any particular arc of interest, though the mere act of splitting the circle into arcs entails additional comparisons. The cheapest are along the lines of (u < 2*v) or (u < 4*v).

• • •

I don’t really have a grand conclusion here, I just felt like sharing what I’ve been toying around with. If you’re looking for a challenge though, I’d appreciate having someone check my calculation for c

_{avg}minimizing the average error.