Subject line says it: I need a quick, approximate (+/- 1%) 3D vector length given its Cartesean components. Processor is a nuthin-special ARM m4, without the coprocessor. The vector is in floating point at the moment, but it could be in integers if that would speed things up. I haven't tested it yet, but my mind says "sqrt == expensive", so I want to avoid that. -- Tim Wescott Control system and signal processing consulting www.wescottdesign.com
Computationally efficient sqrt(x^2 + y^2 + z^2)
Started by ●April 9, 2014
Reply by ●April 9, 20142014-04-09
On Wed, 09 Apr 2014 15:15:00 -0500 Tim Wescott <tim@seemywebsite.please> wrote:> Subject line says it: I need a quick, approximate (+/- 1%) 3D vector > length given its Cartesean components. > > Processor is a nuthin-special ARM m4, without the coprocessor. The > vector is in floating point at the moment, but it could be in integers if > that would speed things up. > > I haven't tested it yet, but my mind says "sqrt == expensive", so I want > to avoid that. > > -- > Tim Wescott > Control system and signal processing consulting > www.wescottdesign.comIs http://en.wikipedia.org/wiki/Fast_inverse_square_root at all handy? -- Rob Gaddi, Highland Technology -- www.highlandtechnology.com Email address domain is currently out of order. See above to fix.
Reply by ●April 9, 20142014-04-09
On 4/9/14 4:29 PM, Rob Gaddi wrote:> > Is http://en.wikipedia.org/wiki/Fast_inverse_square_root at all handy? >sqrt(x) = x * (1/sqrt(x)) -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●April 9, 20142014-04-09
On Wednesday, April 9, 2014 4:15:00 PM UTC-4, Tim Wescott wrote:> Subject line says it: I need a quick, approximate (+/- 1%) 3D vector > > length given its Cartesean components. > > > > Processor is a nuthin-special ARM m4, without the coprocessor. The > > vector is in floating point at the moment, but it could be in integers if > > that would speed things up. > > > > I haven't tested it yet, but my mind says "sqrt == expensive", so I want > > to avoid that. > > > > -- > > Tim Wescott > > Control system and signal processing consulting > > www.wescottdesign.comTim, Check out this thread http://compgroups.net/comp.dsp/magnitude-of-a-3d-vector/1191 Clay
Reply by ●April 9, 20142014-04-09
On 2014-04-09 22:15, Tim Wescott wrote:> Subject line says it: I need a quick, approximate (+/- 1%) 3D vector > length given its Cartesean components. > > Processor is a nuthin-special ARM m4, without the coprocessor. The > vector is in floating point at the moment, but it could be in integers if > that would speed things up. > > I haven't tested it yet, but my mind says "sqrt == expensive", so I want > to avoid that.I would say it also depends on what to do with these distances. For example, if two of those have to be compared, then comparing the square root or the square is the same and you can avoid the square root operation. bye, -- piergiorgio
Reply by ●April 9, 20142014-04-09
On Wed, 09 Apr 2014 15:15:00 -0500, Tim Wescott <tim@seemywebsite.please> wrote:>Subject line says it: I need a quick, approximate (+/- 1%) 3D vector >length given its Cartesean components. > >Processor is a nuthin-special ARM m4, without the coprocessor. The >vector is in floating point at the moment, but it could be in integers if >that would speed things up. > >I haven't tested it yet, but my mind says "sqrt == expensive", so I want >to avoid that.Jack Crenshaw had a series of articles on implementing a square root, 'way back in the dark ages. Sadly, a quick 'net search turned up mostly broken links or partial pages. If you can get hold of his "Math Toolkit for Real-Time Programming" there's an entire chapter on the topic.
Reply by ●April 9, 20142014-04-09
On Wed, 09 Apr 2014 16:48:58 -0400, robert bristow-johnson wrote:> On 4/9/14 4:29 PM, Rob Gaddi wrote: >> >> Is http://en.wikipedia.org/wiki/Fast_inverse_square_root at all handy? >> >> > sqrt(x) = x * (1/sqrt(x))I was about to tell Rob "no, how could the _inverse_ possibly be useful". Thanks for heading me off! -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●April 9, 20142014-04-09
On Wed, 09 Apr 2014 13:49:37 -0700, clay wrote:> On Wednesday, April 9, 2014 4:15:00 PM UTC-4, Tim Wescott wrote: >> Subject line says it: I need a quick, approximate (+/- 1%) 3D vector >> >> length given its Cartesean components. >> >> >> >> Processor is a nuthin-special ARM m4, without the coprocessor. The >> >> vector is in floating point at the moment, but it could be in integers >> if >> >> that would speed things up. >> >> >> >> I haven't tested it yet, but my mind says "sqrt == expensive", so I >> want >> >> to avoid that. >> >> >> >> -- >> >> Tim Wescott >> >> Control system and signal processing consulting >> >> www.wescottdesign.com > > Tim, > > Check out this thread > > http://compgroups.net/comp.dsp/magnitude-of-a-3d-vector/1191Thanks Clay -- I was vaguely remembering something like that, and that thread may be what I had remembered. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
Reply by ●April 9, 20142014-04-09
On 4/9/14 5:13 PM, Tim Wescott wrote:> On Wed, 09 Apr 2014 16:48:58 -0400, robert bristow-johnson wrote: > >> On 4/9/14 4:29 PM, Rob Gaddi wrote: >>> >>> Is http://en.wikipedia.org/wiki/Fast_inverse_square_root at all handy? >>> >>> >> sqrt(x) = x * (1/sqrt(x)) > > I was about to tell Rob "no, how could the _inverse_ possibly be useful". > > Thanks for heading me off! >when the SHArC first came out, they had an instruction that's a primitive iteration for 1/sqrt(x) and i wondered *why* an iterative for that instead of for sqrt(x). the fact that a simply multiplication turns the one into the other was pointed out early, but it wasn't until years later that the implementation of Newton's Method (to solve for the inverse of f(x) = 1/(x^2)) came out to be so clean. then it all made sense to me. -- r b-j rbj@audioimagination.com "Imagination is more important than knowledge."
Reply by ●April 9, 20142014-04-09
On Wed, 09 Apr 2014 22:49:49 +0200, Piergiorgio Sartor wrote:> On 2014-04-09 22:15, Tim Wescott wrote: >> Subject line says it: I need a quick, approximate (+/- 1%) 3D vector >> length given its Cartesean components. >> >> Processor is a nuthin-special ARM m4, without the coprocessor. The >> vector is in floating point at the moment, but it could be in integers >> if that would speed things up. >> >> I haven't tested it yet, but my mind says "sqrt == expensive", so I >> want to avoid that. > > I would say it also depends on what to do with these distances. > > For example, if two of those have to be compared, then comparing the > square root or the square is the same and you can avoid the square root > operation.There's a deficiency on my code base that rules out comparing norm^2 to norm^2. I can actually get away with it in one spot, but not another. Hey wait -- unless I adjust my thinking a bit. I was having the thing do a "cough up a value" step, then later a "compare two values" step -- I could make a "compare value with value" thingie instead. I knew there was a reason to ask here, and (as is often the case) not because my original question would get answered! -- Tim Wescott Wescott Design Services http://www.wescottdesign.com
