Faster Alternative to Math.sqrt()

Question

Are there any alternatives to using Math.sqrt() to get the square root of an unknown value?

For example:

var random  = (Math.random() * (999 - 1)) + 1;
var sqrt = Math.sqrt(random);

I've heard that using Math.sqrt() to get the square root of a number is a very slow operation, I'm just wondering if there are any faster ways I can get the square root of a random number. Any help with this would be greatly appreciated.

Smokeless

as with many math operations, you may use the domain knowledge, if applicable and, for example, pre-calculated it into a hash-table. However, it is only applicable if you have a limited set of possible inputs (i.e. 0-1000 real numbers) – Delwyn

I'm pretty sure that if there was a known faster algorithm to calculate square root, it would have already been implemented as Math.sqrt – Prynne

@yarons while you are correct, still domain knowledge may allow to use less then exact solution or be applicable to limited range of number space, hence allowing some performance boosts. – Delwyn

@VladimirM, you are right, but I understood that the OP was asking about a general solution (random number) – Prynne

That's very slow only in the sense of if you're calling it thousands of times. Otherwise it's unlikely to be a noticeable bottleneck. – Quartet

Of the two operations in the question, I'd guess that generating the random number is the slower one. The square root is essentially loading the argument on the FPU stack, performing the FPU instruction and storing the result back into memory. Using a hash-table implies computing hash values and using possibly non-cached memory, which seems slower. - The obvious exception being that there is no FPU or comparable present. – Comptom

Answer 1

You can be sure that the fastest algorithm you will write your self is already implemented within Math.sqrt if not better .

There is an algorithm to go through the numbers till the middle (with some simply calculation) : Writing your own square root function

but as I said, it's probably implemented if not better.

You can try to look for some specific business/domain logic in order to reduce numbers range .

Lillie

Depends on their needs. They may only need an approximation, for which there are faster algorithms. – Seminary

Answer 2

Do not know how your sqrt is implemented (not a javascript coder) so what is faster I can only speculate but there are few fast methods out there using "magic numbers" for IEEE 754 float/double formats and also for integers for example like in Quake3. That works more or less precise with just few ops on defined intervals and are most likely faster then your sqrt but usable only on specific intervals.

Usual sqrt implementations are done by:

1. approximation polynomial

   usually Taylor series, Chebyshev, etc expansions are used and the number of therms is dependent on target accuracy. Not all math functions can be computed like this.

2. iterative approximation

   there are few methods like Newton, Babylonian, etc which usually converge fast enough so no need to use too much therms. My bet is your sqrt use Newtonian approximation.

   There are also binary search based computations

   • Power by squaring for negative exponents

   Binary search requires the same count of iterations then used bits of number result which is usually more then therms used in approximation methods mentioned above. But binary search for sqrt has one huge advantage and that is it can be done without multiplication (which is significant for bignums...)

   • How to get a square root for 32 bit input in one clock cycle only?

   There are also other search approximations like:

   • How approximation search works

3. algebraically using log2,exp2

   you can compute pow from log2,exp2 directly and sqrt(x)=pow(x,0.5) so see

   • How Math.Pow (and so on) actually works

4. LUT

   You can use piecewise interpolation with precomputed look up tables.

5. hybrid methods

   You can combine more methods together like estimate result with low accuracy approximation polynomial and then search around it (just few bits) with binary search ... But this is meaningful only for "big" numbers (in manner of bits)...

6. some math operations and constants can be computed with PCA

   but I see no point to use it in your case...

Also for more info take a look at related QA:

• How is the square root function implemented?

Do not know what are you computing but fastest sqrt is when you do not compute it at all. Many computations and algorithms can be rewritten so they do not need to use sqrt at all or at least not that often (like comparing distances^2 etc...).

For examle if you want to do:

x = Random();
y = sqrt(x);

You can rewrite it to:

y= Random();
x = y*y;

but beware the randomness properties are not the same !!!

Nadia

Answer 3

If the code you have there is the same code you are using you do not need the square root at all

var random  = (Math.random() * (999 - 1)) + 1;
var sqrt = Math.sqrt(random);

Could be

var sqrt  = (Math.random() * ( 31.6069612586)) + 1;
var random  = sqrt * sqrt ;

Multiplication is much faster than sqrt so the code should be similar

Note the square root of 998 can be pre calculated like above to make it a one time operation rather than each run

Homovec

The second variant will not give the same distribution of random values as the first one. - What is the right way is of course dependent on what distribution was originally aimed for. – Comptom

Answer 4

Mathematics dictate that:

var sqrt = Math.sqrt(random);

is equivalent to:

var sqrt = random**.5;

Probably not any faster, but definitely shorter.

Chew

Answer 5

Your distribution with sqrt is not equal, as you see with the count. For getting the same distribution, you would need a factor which changes the distribution. The factor is dependent to the random number. There is no short cut.

function getRandom() {
    return Math.sqrt((Math.random() * (999 - 1)) + 1);
}

var i, r,
    o = {};

for (i = 0; i < 32; i++) {
    o[i] = 0;
}

for (i = 0; i < 100000; i++) {
    o[Math.floor(getRandom())]++;
}

console.log(o);

.as-console-wrapper { max-height: 100% !important; top: 0; }

Corium

Answer 6

I don't think you can get any faster than the built in pre-compiled code yet for your information below you can find the algorithm on how you might get the square root of a number with pure JS.

It's pretty fast but since it's recursive it will most probably do somewhat slower than it's iterative version. Iterative implementation is up to you.

var sqrt = (n, u = n, d = n-1 ? n/u : 1) => n ? (u === (u+d)/2) && (d === n/u) ? d : sqrt(n,(u+d)/2, n/u) : 0,
       s = 0;
console.time("sqrt");
var s = sqrt(9876543210*9876543210);
console.timeEnd("sqrt");
console.log(s);

console.time("sqrt");
var s = sqrt(98765.4321*98765.4321);
console.timeEnd("sqrt");
console.log(s);

It utilizes the Babylonian method.

Stans

Answer 7

There is an alternative way to do inverse square roots in JS.

const m = 0x5F375A86,
  // Creating the buffer and view outside the function
  // for performance, but this is not thread safe like so:
  buffer = new ArrayBuffer(4),
  view = new DataView(buffer)
  function fastInvSqrt (n) {
    var f, n2 = n * 0.5, th = 1.5
    view.setFloat32(0, n)
    view.setUint32(0, m - (view.getUint32(0) >> 1))
    f = view.getFloat32(0)
    f *= (th - (n2 * f * f))
    f *= (th - (n2 * f * f))
  return f
}

// Test execution time
let start = Date.now()
for (let i = 0; i < 1000000; i++) {
  fastInvSqrt(i**2)
}
console.log('fastInvSqrt', Date.now() - start, 'millieconds')

// compare with Math.sqrt
start = Date.now()
for (let i = 0; i < 1000000; i++) {
  Math.sqrt(i**2)
}
console.log('Math.sqrt', Date.now() - start, 'millieconds')

This was discovered and originally use in a Quake III game!

Millen

fastInvSqrt says it takes longer in the console when running the code snippet. – Estus