• ### Announcements

#### Archived

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

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

## Recommended Posts

MindWipe    940
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

##### Share on other sites
davepermen    1047
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

##### Share on other sites
CodeMunkie    805
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

##### Share on other sites
Nerusai    103
How about using a table?

#### Share this post

##### Share on other sites
MindWipe    940
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

##### Share on other sites
Roland    138
Wouldn''t it be possible to do it the other way arround? Store the 96 sqared border values and search the right one in this using a binary search?

#### Share this post

##### Share on other sites
TerranFury    142
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

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

/__fold

#### Share this post

##### Share on other sites
Roland    138
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

##### 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

##### Share on other sites
Roland    138
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

##### Share on other sites
JohnBolton    1372
If you are computing 2D distance, you might try the classic distance approximation: long side + 1/2 short side.

#### Share this post

##### Share on other sites
MindWipe    940
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

##### Share on other sites
thooot    122
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

##### Share on other sites
Pres    122
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

##### Share on other sites
M3d10n    170
Pres: that calculates the length of the x y 2D vector, thus, the distance from the coordinate (0,0).

#### Share this post

##### Share on other sites
davepermen    1047
shouldn''t it be abs(x) and abs(y) ?

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

#### Share this post

##### Share on other sites
fredizzimo    133
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

##### Share on other sites
MindWipe    940
Please continue disucussing, but I got it working using sin & cos.

kthx!

/MindWipe

#### Share this post

##### Share on other sites
Seriema    634
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

##### Share on other sites
MindWipe    940
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

##### Share on other sites
Seriema    634
got it :D

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

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

#### Share this post

##### Share on other sites
Carandiru    212
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

##### Share on other sites
coderx75    435
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

##### Share on other sites
Trienco    2555
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]