5

Math.sqrt()未知の値の平方根を取得するために使用する代替手段はありますか?

例えば：

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

を使用して数値の平方根を取得するのは非常に遅い操作だと聞いたことMath.sqrt()があります。乱数の平方根を取得できるより高速な方法があるかどうか疑問に思っています。これについての助けをいただければ幸いです。

4

7 に答える 7

11

自分で作成する最速のアルゴリズムは、Math.sqrt 内に既に実装されていると確信できます。

途中まで数値を調べるアルゴリズムがあります（いくつかの単純な計算があります）：独自の平方根関数を書く

しかし、私が言ったように、より良くはないにしても、おそらく実装されています。

数値範囲を減らすために、特定のビジネス/ドメイン ロジックを探すことができます。

于 2017-01-01T09:35:12.627 に答える
8

あなたがどのように実装されているのかわからない(javascript コーダーではない) ので、より速いものは推測することしかできませんが、 IEEE 754形式や、たとえばQuake3sqrtのように「マジック ナンバー」を使用する高速な方法はほとんどありません。これは、定義された間隔でわずかな操作で多かれ少なかれ正確に機能し、おそらくsqrtよりも高速ですが、特定の間隔でのみ使用できます。float/doubleintegers

通常sqrtの実装は次の方法で行われます。

  1. 近似多項式

    通常、テイラー級数、チェビシェフなどの展開が使用され、サームの数はターゲットの精度に依存します。すべての数学関数がこのように計算できるわけではありません。

  2. 反復近似

    ニュートン、バビロニアンなど、通常は十分に速く収束するため、あまり多くのサームを使用する必要がない方法はほとんどありません。私の賭けは、sqrtニュートン近似を使用することです。

    二分探索ベースの計算もあります

    バイナリ検索では、同じ反復回数が必要であり、その後、数値結果のビットが使用されます。これは、通常、上記の近似方法で使用される therms よりも多くなります。しかし、sqrt の二分探索には大きな利点が 1 つあります。それは、乗算なしで実行できることです (bignum では重要です...)。

    次のような他の検索近似もあります。

  3. 代数的に使用するlog2,exp2

    powからlog2,exp2直接計算できるsqrt(x)=pow(x,0.5)ので、参照してください

  4. LUT

    事前計算されたルックアップ テーブルで区分内挿を使用できます。

  5. ハイブリッド方式

    低精度の近似多項式を使用して結果を推定するなど、より多くの方法を組み合わせることができます。その後、二分探索を使用してその周囲 (ほんの数ビット) を検索します。

  6. 一部の数学演算と定数は PCA で計算できます

    しかし、あなたの場合はそれを使用する意味がありません...

また、詳細については、関連するQAをご覧ください。

何を計算しているのかわかりませんが、sqrtまったく計算しないときが最速です。多くの計算とアルゴリズムは書き直すことができるため、sqrtまったく使用する必要がないか、少なくともそれほど頻繁に使用する必要はありません (距離^2の比較など...)。

たとえば、次のようにします。

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

次のように書き換えることができます。

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

ただし、ランダム性のプロパティが同じではないことに注意してください!!!

于 2017-01-01T11:08:51.297 に答える
1

組み込みのコンパイル済みコードよりも高速に取得できるとは思いませんが、以下の情報については、純粋な JS を使用して数値の平方根を取得する方法に関するアルゴリズムを見つけることができます。

かなり高速ですが、再帰的であるため、反復バージョンよりも多少遅くなる可能性があります。反復的な実装はあなた次第です。

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

バビロニア方式を採用。

于 2017-01-01T22:44:27.360 に答える
1

sqrtカウントでわかるように、あなたの分布は等しくありません。同じ分布を得るには、分布を変更する要因が必要です。係数は乱数に依存します。ショートカットはありません。

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

于 2017-01-01T10:10:51.917 に答える
0

数学は次のことを示しています。

var sqrt = Math.sqrt(random);

次と同等です。

var sqrt = random**.5;

おそらくそれ以上速くはありませんが、間違いなく短くなります。

于 2019-11-07T04:41:11.337 に答える