Approximating the square root of sum of two squares on a microcontroller

Question

I'm working on implementing an FFT algorithm in assembly on an 8-bit microcontroller (HCS08) for fun. Once the algorithm is completed, I'll have an array of 8-bit real/imaginary pairs, and I'll want to find the magnitude of each of these values. That is, if x is complex, I want to find

|x| = sqrt(Re{x}^2 + Im{x}^2)  

Now I have available to me a 16-bit register and an 8-bit register. I thought about just squaring them, adding them, and taking the square root of the result, but that poses a problem: the maximum possible value of the sum of the squares of two 8-bit numbers is ~130k, which is greater than the maximum value a 16-bit register can hold (65.5k).

I came up with a subroutine which computes the integer square root of a 16-bit number, which seems to work well, but obviously I'm not guaranteed to be working with values that will fit into 16 bits. My thinking right now is that there is an algorithm which will approximate what I need directly, but I can't seem to find anything. Any ideas would be greatly appreciated.

To summarize: Say I have a vector with two 8-bit components, and I want to find the length of the vector. How can I approximate this without actually computing squares and square roots?

Thanks!

Answer 1

There's a web page describing a Fast Magnitude Estimator. The basic idea is to get a least square (or other high quality) fit to the equation:

Mag ~= Alpha * max(|I|, |Q|) + Beta * min(|I|, |Q|)

for the coefficients Alpha and Beta. Several coefficient pairs are listed with mean square errors, max errors, etc., including coefficients suitable for integer ALUs.

Answer 2

If the sum is greater than 65535, divide it by 4 (shift right 2 bits), take the square root, and multiply that by 2. You'll lose one bit of accuracy, and naturally the result is not guaranteed to fit into 8 bits.