Archived

This topic is now archived and is closed to further replies.

Really, really fast sqrt (not Carmacks)!?!?!?

This topic is 5232 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Okey... I''m trying to do a raycaster in j2me, now I stumbled uppon a problem. I need a pretty damn fast sqrt. Or an sqrt for that matter (not one being supported). Camrmack''s sqrt won''t work because j2me does not support floating points (or doubles). Anyone got any idea?!?! I might make a lookup table but that will take alot of memory... It doesn''t have to be too accurate at all. /MindWipe

Share this post


Link to post
Share on other sites
no floats? so.. fixed point? sorry, i don''t know much about the platform you use..

but.. if you have an unsigned integer, and take the square root of it, it''ll be an unsigned short.. means a 4byte value will have a 2byte root..

that could help for a lookuptable.. or not.. dunno:D i''m tierd.. sorry..

but there are tons of algorithms for all sort of constraints out there (even without multiplication and addition supported, etc:D)..

just use google..

"take a look around" - limp bizkit
www.google.com

Share this post


Link to post
Share on other sites
Do you have to calculate the square root? If you are doing something like comparing distances you can just compare the squared value. Of course, I don''t know exactly what you are doing.

Share this post


Link to post
Share on other sites
quote:
Original post by CodeMunkie
Do you have to calculate the square root? If you are doing something like comparing distances you can just compare the squared value. Of course, I don''t know exactly what you are doing.


Well, I''m using it to get a distance. But I think I''ll use some sort of table. Because the sqrt is only needed so that I know which value out of 96 to choose, hence it hasn''t got to be that exact.

/MindWipe

Share this post


Link to post
Share on other sites
You''re using some equations that involve a square root. Can you manipulate them by squaring both sides to eliminate the need for a square root? The simple example is, replace ''sqrt(x)==2'' with ''x==4.'' I''m sure it''s not that simple, but you might be able to reduce your dependance on sqrts!

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Roland: Binary search? In that case, why not use direct mapping?

/__fold

Share this post


Link to post
Share on other sites
What do you mean by direct mapping?
A lookuptable can't be used for squared values, because the table would become too big and the the distance between the values increases, so you cant use a constant scaling factor.

p.s. take a look at: http://www.azillionmonkeys.com/qed/sqroot.html
there are some sqare root algorithms described

[edited by - Roland on August 12, 2003 6:27:26 PM]

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
Roland: You''re right, I''ll go to bed now.

...or how about a hash map?

/__fold

Share this post


Link to post
Share on other sites
hash? interresting idea, but at the moment I can't think of an hashing function, that would solve the problem and no beeing as slow as an square root itself...

[edited by - Roland on August 12, 2003 6:58:35 PM]

Share this post


Link to post
Share on other sites
quote:
Original post by Roland
What do you mean by direct mapping?
A lookuptable can''t be used for squared values, because the table would become too big and the the distance between the values increases, so you cant use a constant scaling factor.

p.s. take a look at: http://www.azillionmonkeys.com/qed/sqroot.html
there are some sqare root algorithms described

[edited by - Roland on August 12, 2003 6:27:26 PM]


Thanks alot for that url! There was atleast one that seemed very good for my use. Gotta see how it works in action.

About my use of the sqrt, see, I need the distance to a wall to know how big it will look on the screen. But the screen has only got a height of 96px, and if the wall is really close it will fill up the whole screen, if it really far away it will not be visible at all. And it doesn''t have to look perfect at all, but it has to be fast.

But that url might just have provided me with a solution.

/MindWipe

Share this post


Link to post
Share on other sites
Here''s an approximation for distance (I think it''ll be within 7% of the actual value):


int findDist(int x, int y)
{
if (y < x)
return x + 5 * y / 16;
else
return y + 5 * x / 16;
}

Share this post


Link to post
Share on other sites
Thooot, what is that formula going to find the distance between ? You only pass one X int and one Y int - is it distance from origin ?

Share this post


Link to post
Share on other sites
quote:
Original post by MindWipe

Thanks alot for that url! There was atleast one that seemed very good for my use. Gotta see how it works in action.

About my use of the sqrt, see, I need the distance to a wall to know how big it will look on the screen. But the screen has only got a height of 96px, and if the wall is really close it will fill up the whole screen, if it really far away it will not be visible at all. And it doesn't have to look perfect at all, but it has to be fast.

But that url might just have provided me with a solution.

/MindWipe


Then you should be able to compare the squared distance against another squared distance, no square root needed. Or is there something I don't see here?

[edited by - fredizzimo on August 18, 2003 4:16:35 AM]

Share this post


Link to post
Share on other sites
this was kinda interesting

but as many has asked, and I don''t see a answer...

Why do you have to use sqrt? Why not just compare the squared distances?

I''m guessing you need to compare distance A to distance B? B being a "maximum far away distance that needs to be drawn"? If both are squared you can just compare them
if A < B then A^2 > B^2 will be true too.

The normal distance formula is: sqrt( x*x + y*y ). Is that what you''re using?..

kinda curious what _really_ must be sqrt

"No lies of sugar can sweeten the sournes of reality"

}+TITANIUM+{ A.K.A. DXnewbie[onMIRC]

Share this post


Link to post
Share on other sites
quote:
Original post by Seriema
this was kinda interesting

but as many has asked, and I don''t see a answer...

Why do you have to use sqrt? Why not just compare the squared distances?

I''m guessing you need to compare distance A to distance B? B being a "maximum far away distance that needs to be drawn"? If both are squared you can just compare them
if A < B then A^2 > B^2 will be true too.

The normal distance formula is: sqrt( x*x + y*y ). Is that what you''re using?..

kinda curious what _really_ must be sqrt

"No lies of sugar can sweeten the sournes of reality"

}+TITANIUM+{ A.K.A. DXnewbie[onMIRC]



Well, see, you want to know the distance how far away a sphere for example is, to be able to draw it in the right scale.

Thing don''t get smaller with Dirstance_To_Obj^2

/MindWipe

Share this post


Link to post
Share on other sites
Using Calculus, you can define the accuracy of your sin / cos wave forms. Using a series, and limiting the accuracy with yeild higher performance. But unfortunately, I''m talking about the precision of a float or double in this case.
a(o) = sigma( a(n)cos(nx) + b(n)sin(nx) )
where n is the number of terms needed for precision.

Share this post


Link to post
Share on other sites
Why are you using a sqrt in a raycaster? Since you should already know the angle of the ray, you can use sine or cosine to find the distance.

x = current x-position of ray being cast
y = current y position of ray being cast
a = angle of ray
d = unknown current length of ray

When x >= y,
d = x / cos(a)

When y > x,
d = y / cos(a)

It would require much less memory to create sine and cosine look-ups than it would to create a square root look-up. I''d written raycasters back in the day and never used sqrt''s. They''re too slow.

- Jay


[ Here, taste this ]

Share this post


Link to post
Share on other sites
quote:
Original post by coderx75
I'd written raycasters back in the day and never used sqrt's. They're too slow.


careful with that. i spent an eternity testing all those "fast" sqrts etc. and the best i could get was just as fast/slow as the built in sqrt (thats the optimized build, else it wouldnt even come close).
even the look up table on nvidias site was slower, so id guess that on current machines we really shouldnt worry about sqrt as much as 10 years ago ,-)

the only thing that was really making a difference was a crude approx. using bit shifting. that takes about 2.5 times longer than a simple multiplication (unless my test sucked).

__forceinline float _asFloat(INT32 i) {
return *(float *)&i;
}
__forceinline float InvSqrt(float x) {
return _asFloat(0x5f3759df - ((*(int *)&x) >> 1));
}
__forceinline float Sqrt( float x ) {
return _asFloat(((*(int*)&x) >> 1) + 0x1FC00000);
}

the sqrt is a version i found on a board (dont ask why, but this "doing all in one line" version was twice as fast as carmacks "clean" code, so i adjusted his invsqrt.

but remember, that there are no refinement steps and the result isnt as precise as it could be.

anyway, avoiding the sqrt in the first place is probably always the better solution.

[edited by - Trienco on August 21, 2003 4:00:30 AM]

Share this post


Link to post
Share on other sites