A83: Re: Calculating Distances Fast - any suggestions ?
[Prev][Next][Index][Thread]
A83: Re: Calculating Distances Fast - any suggestions ?
If you are working with 8 bit numbers, you might try using a straight lookup
table for square roots. Though, even with that the results are likely to
overflow into 16 bits. Multiply is pretty easy to get around, since a table
of squares is small. A quick way of doing square roots would be to store
the squares for the whole numbers in an array, then run through it and find
the largest square that is less than the number you are trying to take the
square root of:
00, 01, 04, 08, 16, 32, ...
0 1 2 3 4 5
The largest number that is smaller than 13, for example, is 8, which is in
position 3, so it's square root is 3 (assuming you can disregard the
fractional portion). I think there is a way to get more acurate results by
repeating the process, similiar to the textbook method for storing
fractional values in binary (as for a digital circuit), but I'll have to
think on it.
> I wondered if anyone knew a fast decent approximation to the distance
> calculation Sqrt(x^2+y^2). At present I'm using (|x|+|y|)/2 which is okay
> when objects are roughly scattered, but tends to stuff up any straight
> lines, drawing a boxed outline of objects this approximation morphs it
> into a "star" shape. I don't really want to multiply if possible so
> a couple of iterations of Newton-Rhapson are out.
_____________________________________________
NetZero - Defenders of the Free World
Click here for FREE Internet Access and Email
http://www.netzero.net/download/index.html
References: