[JASS] Alternative to SquareRoot?

[Trigger.edge]

Hi guys!

I wanted to know if there an alternative to SquareRoot?

 

[DracoL1ch]

Fast inverse square root - Wikipedia, the free encyclopedia

 

[Trigger.edge]

So... The formula to apply this in jass is?

 

[IcemanBo]

What is the problem with sqrt? Is there a specific situation which should not use it?

 

[Wietlol]

If you want to avoid it because of its required processing time, you could do the calculations on the squared values instead.

Aka:
MaxDistance = 600
DistanceX = 400
DistanceY = 300

IsInRange = MaxDistance >= sqrt(DistanceX*DistanceX + DistanceY*DistanceY)
Or
IsInRange = MaxDistance*MaxDistance >= DistanceX*DistanceX + DistanceY*DistanceY

 

[Pyrogasm]

So... The formula to apply this in jass is?

What is the problem with sqrt()? Is there a specific situation which should not use it?

If you're doing a lot of sqrt() calls in a short time (physic engine, for example) it could potentially be beneficial to optimize a lot and use something like the fast inverse sqrt trick DracoL1ch posted. However, for most WC3 code sqrt() is fine and if it really matters you can achieve an acceptable increase in speed/efficiency by working with the square of the number you want to compute the sqrt of exactly as Wietlol said.

The answers to these questions depend a lot on why you don't want to use sqrt() in the first place.

 

[IcemanBo]

The answers to these questions depend a lot on why you don't want to use sqrt() in the first place.

Exactly. What Wietlol explained is a nice trick to avoid the sqrt function call, but it only should be used privatly by a system, and only works if you have a reference value, so like MaxDistance for example.

There can be done other approaches in other cases, like caching sqrt values onInit + a table lookup later, or just to use other maths forumlas maybe if it is for certain calculations.
So it's really hard to say anything how to genealy "avoid" sqrt, because by itself as standalone, it is a very useful function.

 

[LeP]

Fast inverse square root - Wikipedia, the free encyclopedia

in my tests fast inverse square root was slower in jass.

 

[Zwiebelchen]

That's to be expected. Native code is almost always faster than the manually implemented JASS equivalent. There are only few exceptions, like FoG loop vs. ForGroup.

 

[Trigger.edge]

What is the problem with sqrt? Is there a specific situation which should not use it?

The problem is the processing timer as wietlol said, but neither is it a serious problem. I just wanted to know if there is another way to calculate the sqrt().

in my tests fast inverse square root was slower in jass.

You can post a test code?

 

[Deleted member 219079]

I think Wietlol's answer is the solution.

 

[LeP]

You can post a test code?

function rsqrt takes real r returns real
   local real x = r * 0.5
   set r = i2r(0x5f3759df - ( r2i(r) / 2 ))
   return r * ( 1.5 - ( x * r * r ) )
endfunction

Go wild. Needs an r2i /i2r return-bug function of some sort.
The performance killer here is ofc the r2i/i2r calls.

 

[Wietlol]

I assume that i2r() and r2i() are I2R() and R2I().
Or are they typecasts (without changing the bytedata behind the screen)?

 

[LeP]

I assume that i2r() and r2i() are I2R() and R2I().
Or are they typecasts (without changing the bytedata behind the screen)?

Typecasts like here or here.

I took crigges approach.
Here's the full script i guess.

//# +nosemanticerror
private function indexToReal takes integer i returns real
  return i
endfunction

//# +nosemanticerror
private function realToIndex takes real i returns integer
  return i
endfunction

private function cleanR takes real r returns real
  return r
  return 0.0 // dont let jh inlines this
endfunction

private function cleanI takes integer i returns integer
  return i
  return 0 // dont let jh inlines this
endfunction

function i2r takes integer i returns real
  return cleanR(indexToReal(i)) // this gets inlined
endfunction

function r2i takes real i returns integer
  return cleanI(realToIndex(i)) // this gets inlined
endfunction

function rsqrt takes real r returns real
   local real x = r * 0.5
   set r = i2r(0x5f3759df - ( r2i(r) / 2 ))
   return r * ( 1.5 - ( x * r * r ) )
endfunction

 

[Deleted member 219079]

And you're confident it's the most efficient with 2 casts?

 

[LeP]

And you're confident it's the most efficient with 2 casts?

again, in my tests SquareRoot was faster. I just posted it because op was interested in it.
You are free to benchmark/improve it.

 

[DracoL1ch]

why would you need typecasting? you know int and float are totally different values and cannot be converted any faster than I2R() ?

 

[Deleted member 219079]

I2R < *1.

I think the hexadecimal number is there to make it look cooler.

 

[Wietlol]

Because there is no bitshifting in JASS.
Dividing an integer by 2 is the same as shifting the bits one place to the right.
This cannot be done to reals (floats) as the float values/bits are not in line.

 

[Trigger.edge]

function rsqrt takes real r returns real
   local real x = r * 0.5
   set r = i2r(0x5f3759df - ( r2i(r) / 2 ))
   return r * ( 1.5 - ( x * r * r ) )
endfunction

Go wild. Needs an r2i /i2r return-bug function of some sort.
The performance killer here is ofc the r2i/i2r calls.

Thanks... you say that it is slow that SquareRoot however I find it interesting.

If you want to avoid it because of its required processing time, you could do the calculations on the squared values instead.

Aka:
MaxDistance = 600
DistanceX = 400
DistanceY = 300

IsInRange = MaxDistance >= sqrt(DistanceX*DistanceX + DistanceY*DistanceY)
Or
IsInRange = MaxDistance*MaxDistance >= DistanceX*DistanceX + DistanceY*DistanceY

I think Wietlol's answer is the solution.

I agree with you.

 

[Dr Super Good]

To clarify, SquareRoot function is not slow. Most of its execution time is the JASS overhead of making a function call (name lookup + stack stuff including new local hashtable). This is why a faster solution cannot exist because such a solution would need to be written in JASS and as such the JASS overhead already makes it slower than SquareRoot. This is also why there is as good as no speed difference between using integer and real types in JASS, despite most processors having integer throughput several times larger than their floating point throughput.

Every named element in a JASS script is looked up at run time using a hash table mapping element name string to element data. Even doing something as simple as "set i = i + i" performs 3 name lookups. Trying to write any sort of optimized mathematical code will end up executing painfully slowly when compared with native code.

Why they did not static link variables I do not know. That alone would make JASS an order of magnitude or more faster.

 

[DracoL1ch]

also Pow(x,0.5)