Quote:Original post by lunar-blue
Hey, im new here and im a junior programmer pretty much, but i did some projects for mathematic calculators and collision detection....i know that newton had a very efficient method of solving square roots.....i also have a method, im not sure if its as fast as you'd like but the good thing about it is that u can give it the accuracy you want. If you need the code i'll be glad to share

I use my own method, wich is the binary method.

Basically, you express number n in the form a * 2^0 + b * 2^1.... then you halve each exponent.

Dead simple in hw. (with some mods, it can be done without transisters at all).

In sw, you need tables tho...

Theres other things, like binary trees, ect. Which can be faster...

From,
Nice coder

"Nice coder"

Can you please show an example of this process of sqrt-ing? (I don't mean code example - I mean just pick a number and show the process of sqrt-ing it)

Quote:Original post by cyric74
I'm currently using:
*** Source Snippet Removed ***

I call this function many, many, many times per second server-side on my 2D space sim. The number of calls grows exponentially for each player that joins the server, so my question is, am I doing this the best way? Is there a cheat to get around doing it so much?

Thanks,
Cyric

WHy do you need the distance, and do you need the actual value or just use it for comparison against a threshold???

If only comparison, you need only compare the squares (no need for sqrt).

If it can be a rough distance to compare, you can do the clasic box test:
rough_dist = MAX(x2-x1, y2-y1, z2-z1);

You can also do whats called lazy evaluation where if you know the 2 objects
will not need to be processes if they are outside of a threshold distance, you first do a rough dist calc and then if its inside of your threshold then you do the costlier sqrt calculations.


Another estimation calc (that is only a few percent off) for 2D is adding the length of the longest delta (X or Y) to the shortest delta (Y or X) divided by 2.

dx = abs(x2-x1)
dy = abs(y2-y1)
if dx>dy dist=dx+(dy/2) else dist=dy+(dx/2)



Another idea (depending on how it is used) is to store the distances in a table
and then only update them on an interval proportinal to the distance (probably by distance intervals of squares).

that works just fine for an int value into float, but that's basiclly what the 2nd method I showed does, but it transfers from powers of 2 linearly(which is why it's so fast). I've tried it and any use of tables will either be inaccurate(using an incomplete table) or slows it down to the point where you should just use a sqrt(if you use a complete table or linearly interpolate). Having a 18%, 2% and a 1%< function isn't a bad combination.Just remember to use them right. So if you're testing something bounded by 10 then use 12 for the first function(18%) and like 10.2 for the 2nd one(1.8%). Don't be afrad of using a function with a moderatly sized error, because all the floating point calculations you make have errors... we just like to ignore them :)

So I'd say use the three functions in conjuction with quad-trees(oct-trees are 3d) if you want a real speed up. Maybe even make the real memory for preformace trade off and slice up your space.

In the end, you are the programmer. Run some time tests and see what ranges work the best, and maybe just drop the calculation quality when there's a slow down rather then always having some distances a certen % off.

EDIT: will ppl PLEASE stop posting how you can compare two vector distances without the square root, it's been said 3 times! It would be nice if ppl would read the thread rather then just posting everything they know!

Quote:Original post by Nice Coder
Also note, you are missing abs's in your distance formula

if (sqrt(abs(x1 - x2) * abs(x1 - x2) + abs(y1 - y2) * abs(y1 - y2))) > r {}

From,
Nice coder

Please define a number n where (n * n) != (abs(n) * abs(n) + e)
Where e is a small value.


As for the problem, you really have to tell us a bit more of what you are doing?