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!
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.