26288 total geeks with 3498 solutions
Recent challengers:
 Welcome, you are an anonymous user! [register] [login] Get a yourname@osix.net email address 

Articles

GEEK

User's box
Username:
Password:

Forgot password?
New account

Shoutbox
MaxMouse
It's Friday... That's good enough for me!
CodeX
non stop lolz here but thats soon to end thanks to uni, surely the rest of the world is going good?
stabat
how things are going guys? Here... boring...
CodeX
I must be going wrong on the password lengths then, as long as it was done on ECB
MaxMouse
lol... the key is in hex (MD5: of the string "doit" without the "'s) and is in lower case. Maybe i should have submitted this as a challenge!

Donate
Donate and help us fund new challenges
Donate!
Due Date: May 31
May Goal: $40.00
Gross: $0.00
Net Balance: $0.00
Left to go: $40.00
Contributors


News Feeds
The Register
ServiceKey, Oracle
end "grey market"
code spat without
bloodshed
BBC suspends CTO
after it spaffs
£100m on doomed IT
system
Open wide, Google:
Here comes an
advertising
antitrust probe
El Reg drills into
Office 365: Email
migration
Daft tweet by
Speaker Bercow"s
loquacious wife DID
libel lord
Paul Allen buys
lovingly restored
vintage V-2 Nazi
ballistic missile
Hey, you, dev. What
do you mean,
storage is BORING?
Curse you, old
person, for
inventing
computers!
Feds slam
hacker-friendly
backdoors in
jalopy, grub
factories
4G LTE: Good for
tweets and watching
Dr Who. Crap
at saving lives
Slashdot
Possible Collision
Between
Cube-satellite and
Old Space Junk
AT&T Quietly
Adds Charges To All
Contract Cell Plans
Drupalcon Attendees
Come Together To
Build Help4ok.org
In 24 Hours
Twitter"s New
Money-Making Plan:
Lead Generation
Bandages That Can
Turn Off Genes
Encourages Wound
Healing
BT Runs an 800Gbps
Channel On Old
Fiber
Australian Police
Move To Make 3D
Printed Guns
Illegal
Cockroaches
Evolving To Avoid
Roach Motels
Meet the 23-Ton
X-Wing, the World"s
Largest Lego Model
Android Malware
Intercepts Text
Messages, Forwards
To Criminals
Article viewer

Length of a Line Without Square Root



Written by:niki
Published by:Nightscript
Published on:2006-01-03 05:08:43
Topic:Maths
Search OSI about Maths.More articles by niki.
 viewed 14956 times send this article printer friendly

Digg this!
    Rate this article :
Ever needed to calculate the Length of a line, but processing time is critical, or you just plain dont have a square root function?

Here are a couple simple functions to do just that, depending on the precision you need, and instrucion set available, you can create a variety of similar functions.

All it takes is some imagination, a bit of math, and an indepth understanding of the instruction set available to you.

I have used similar functions in a physics enging for pinball on gameboy, and in pixel shader assembly for complex Xbox rendering routines.

This same type of thing can be done for basically any function. Just let me know if you have any requests.

int length(int x,int y)
//average error of about 4%
{
    if(abs(x)>abs(y))
        return abs(x)+(abs(y)>>1);
    else
        return abs(y)+(abs(x)>>1);
}

float length(float x,float y)
//average error of about 0.005%
//similar error as the 'rounding error' of 32bit floating point)
{
    float a,b;
    if(abs(x)>abs(y))
    {
        a=abs(x);
        b=abs(y);
    }
    else
    {
        b=abs(x);
        a=abs(y);
    }
    a=a+0.42f*b*b/a;
    return (a+(x*x+y*y)/a)/2;
}




If you want the length of a 3d line, you can create a similar function, or just call this same function twice.

int length3d(int x, int y, int z)
{
    return length(length(x,y),z);
}
float length3d(float x, float y, float z)
{
    return length(length(x,y),z);
}


Did you like this article? There are hundreds more.

Comments:
Geek_Freek
2006-01-06 09:40:00
Hmm.. is tis present in Hacker's delight
Anonymous
2006-01-27 21:07:36
I'm intrigued... How did you come about that formula?
niki
2006-01-27 21:44:02
made them from scratch.
the first one, was derived from "abs(x)+abs(y)"
to simply come up with something that is more accurate, on an integer based system, with limited isntruction set(eg. z80, C64, etc.)

the second is similarly derived from the first, but using some complex instructions (multiply/divide)..
the idea for them basically stemed form the desire to do complex math functions, on weak processors, and then rezlizing, that the results of such functions, need not be exact.
eg. the length of (3,4) is exactly 5.
but the length of say.. (7,9) will be 11: which actually has an error of 3.65% in itself, just due to the raw nature of rounding error in using integers.

then with doing the same types of things on complex systems(eg. physics for a game), optimization remained a concern, but more complex instructions were available. and accuracy became more important.
Anonymous
2006-01-27 22:27:52
The second function is quite a bit more complicated than the first. How did you derive it?
niki
2006-01-28 00:28:16
a=a+0.42f*b*b/a;
is similar to the original a=a+0.5*b
but 0.41..(sqrt(2)-1) yields the correct result for the limit of a=b
then b*b/a isntead of plin b: matches the curve much more closely

and then the last step:
return (a+(x*x+y*y)/a)/2;
simply average's the value, with it's recipricol,

ie. using the fact that |sqrt(n)-a| >=
|sqrt(n)-(a+n/a)/2|

clearly neither of these functions are fully optimized, or even provide the optimal accuracy within their formula.
but they are simple to read, and easy to modify.

I've done similar for sin, tan, log, other roots, random number generators, etc.

for performance, the best gains are arrived, not by refining the formula, but by changing the formula to come up with results that are similar enough to do what you want.
Anonymous
2006-01-28 00:55:37
That's clever!
I'm not sure how to adapt this method to other functions, but I'm seriously impressed, nonetheless.
niki
2006-01-28 04:36:06
if there's any particular function you'd like to see something like this for, just let me know.
as long as you can describe what the function is mathematically(even if you don't have the actual formula), and have a specific example of it's intended use, I can probably come up with something that should be fast enough and/or accurate enough.
Anonymous
2006-01-28 16:29:46
I wouldn't mind seeing what other functions you've come up with. I'd be interested to see how you came up with log approximation.
Anonymously add a comment: (or register here)
(registration is really fast and we send you no spam)
BB Code is enabled.
Captcha Number:


Test Yourself: (why not try testing your skill on this subject? Clicking the link will start the test.)
Math Test by mattman059

Goes through some basic Boolean arithmetic and a little set theory.
Number Translation Test by crazynird

So you think you're good at translating numbers? Then try out this test!


     
Your Ad Here
 
Copyright Open Source Institute, 2006