#### Archived

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

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

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

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

"take a look around" - limp bizkit

##### 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 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 on other sites
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 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 on other sites
Roland: Binary search? In that case, why not use direct mapping?

/__fold

##### 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 on other sites
Roland: You''re right, I''ll go to bed now.

...or how about a hash map?

/__fold

1. 1
Rutin
25
2. 2
3. 3
4. 4
JoeJ
18
5. 5

• 14
• 14
• 11
• 11
• 9
• ### Forum Statistics

• Total Topics
631758
• Total Posts
3002137
×