Faster Alternative to Math.sqrt()

问题:

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.

回答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 .

回答2:

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

回答3:

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; }

回答4:

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 !!!

回答5:

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.