35

2つの2進数の乗算にはn^2の時間がかかりますが、数値の2乗はどういうわけかより効率的に行うことができます。（nはビット数です）どうしてそれができるでしょうか？

それとも不可能ですか？これは狂気です！

4

14 に答える 14

70

  1. O(N^2) よりも効率的に 2 つの数値を乗算するアルゴリズムが存在します (カラツバ、ポラード、シェーンハーゲ シュトラッセンなどを参照)。

  2. 「2 つの任意の N ビット数を乗算する」と「任意の N ビット数を 2 乗する」という 2 つの問題は、同じ複雑さを持ちます。

我々は持っています

4*x*y = (x+y)^2 - (x-y)^2

したがって、N ビット整数の 2 乗に O(f(N)) 時間がかかる場合、2 つの任意の N ビット整数の積も O(f(N)) で取得できます。(つまり、2x N ビット合計、2x N ビット平方、1x 2N ビット合計、および 1x 2N ビット シフト)

そして明らかに私たちは持っています

x^2 = x * x

したがって、2 つの N ビット整数の乗算に O(f(N)) かかる場合、N ビット整数の 2 乗は O(f(N)) で実行できます。

積 (平方に対して) を計算するアルゴリズムは、同じ漸近コストで平方 (積に対して) を計算するアルゴリズムを提供します。

他の回答で述べたように、高速乗算に使用されるアルゴリズムは、二乗の場合に単純化できます。ゲインは、f(N) 自体ではなく、f(N) の前の定数になります。

于 2009-09-04T09:49:27.410 に答える
15

n桁の数値を二乗する方が、2つのランダムなn桁の数値を乗算するよりも高速な場合があります。グーグル私はこの記事を見つけました。それは任意精度の算術についてですが、それはあなたの求めていることに関連しているかもしれません。その中で著者はこれを言います：

大きな整数、つまりX ^ 2 =（xn-1、xn-2、...、x1、x0）^ 2を二乗する場合、xi*xjおよびxj*xiの形式の多くの外積項は同等です。それらを2倍にするには、1回だけ計算してから、左にシフトする必要があります。n桁の二乗演算は、（n ^ 2 + n）/2個の単精度乗算のみを使用して実行されます。

于 2009-09-04T07:41:39.667 に答える
7

他の人が指摘したように、二乗は、任意の数値間の通常の乗算​​よりも約 1.5 倍または 2 倍高速です。計算上の利点はどこから来るのですか? 対称性です。の二乗を計算して、1011悪用できるパターンを見つけてみましょう。u0:u3最上位から最下位までの数のビットを表します。

    1011 //                               u3 * u0 : u3 * u1 : u3 * u2 : u3 * u3
   1011  //                     u2 * u0 : u2 * u1 : u2 * u2 : u2 * u3       
  0000   //           u1 * u0 : u1 * u1 : u1 * u2 : u1 * u3                 
 1011    // u0 * u0 : u0 * u1 : u0 * u2 : u0 * u3

ui * uiの要素を考慮して対角線を形成し、それらを無視すると、 の要素が 2 回繰り返されi=0, 1, ..., 4ていることがわかります。ui * uji ≠ j

したがって、対角線より下の要素の積和を計算し、それを左シフトして 2 倍にするだけです。最後に対角要素を追加します。これで、2 倍の速度アップがどこから来たのかがわかります。実際には、対角線と余分な操作により、速度は約 1.5 倍になります。

于 2013-05-05T20:01:50.800 に答える
6

二乗によるべき乗について言及している可能性があると思います。この手法は乗算には使用されませんが、n が大きくなる可能性がある x^n の累乗に使用されます。x 自体を N 回乗算するのではなく、N の 2 進数表現にマッピングできる一連の 2 乗および加算演算を実行します。乗算演算の数 (大きな数の加算よりもコストがかかります) は、N からlog(N) は、素朴なべき乗アルゴリズムに関するものです。

于 2009-09-04T06:23:24.113 に答える
4

数値に 2 のべき乗を掛けることを意味しますか? 結果は単純なビット シフトで計算できるため、これは通常、任意の 2 つの乱数を乗算するよりも高速です。ただし、最新のマイクロプロセッサは、これらのタイプの計算に多くのブルート フォース シリコンを使用しており、ほとんどの演算は古いマイクロプロセッサに比べて目がくらむほどの速度で実行されることに注意してください。

于 2009-09-04T06:03:03.173 に答える
3

私はそれを持ってます！

2 * 2

よりも高価です

2 << 1

(1 つのケースでしか機能しないことに注意してください。)

于 2009-09-04T06:26:33.857 に答える
3

乗算を展開したいとします(a+b)×(c+d)。これは、4 つの個別の乗算に分割されますa×c + a×d + b×c + b×d。

しかし、 を展開したい場合は(a+b)²、3 つの乗算 (および 2 倍) だけが必要ですa² + 2ab + b²。

(2 つの乗算自体が平方であることに注意してください。)

願わくば、これが、通常の乗算​​よりも 2 乗を実行する場合に可能なスピードアップのいくつかについての洞察を与え始めることを願っています。

于 2016-05-20T11:11:57.373 に答える
1

まず第一に素晴らしい質問です！このような質問がもっとあればいいのにと思います。

したがって、私が思いついた方法は、算術複雑さのみの一般的な乗算の O(n log n) であることがわかりました。任意の数 X を次のように表すことができます。

X = x_{n-1} 2^{n-1} + ... + x_1 2^1 + x_0 2^0
Y = y_{m-1} 2^{m-1} + ... + y_1 2^1 + y_0 2^0

どこ

x_i, y_i \in {0,1}

それから

XY = sum _ {k=0} ^ m+n r_k 2^k

どこ

r_k = sum _ {i=0} ^ k x_i y_{k-i}

これは、(n + m) log( n + m) 時間で各 k の r_k の値を見つけるための FFT の単純なアプリケーションです。

次に、各 r_k について、オーバーフローの大きさを判断し、それに応じて合計する必要があります。数値を二乗する場合、これは O(n log n)算術演算を意味します。

Schönhage-Strassen アルゴリズムを使用して r_k 値をより効率的に合計し、O(n log n log log n) ビット操作の範囲を取得できます。

あなたの質問に対する正確な回答は、すでに Eric Bainville によって投稿されています。

ただし、整数の乗算にははるかに優れた境界が存在するため、数値の 2 乗では O(n^2) よりもはるかに優れた境界を取得できます。

于 2009-09-04T17:45:23.227 に答える
0

マシンのワード サイズが固定長であり、2 乗する数値がメモリ内にあると仮定すると、2 乗演算はメモリから 1 回の読み込みで済むため、高速になる可能性があります。

任意の長さの整数の場合、乗算は通常 O(N²) ですが、大きな整数の場合はこれを減らすアルゴリズムがあります。

aをbで乗算する単純な O(N²) アプローチを想定する場合、 aの各ビットに対して、bをシフトし、そのビットが 1 の場合はアキュムレータに追加する必要があります。a のビットごとに、 3N 回のシフトと追加が必要です。

ご了承ください

( x - y )² = x² - 2 xy + y²

したがって

x² = ( x - y )² + 2 xy - y²

各yが x よりも大きくない最大の 2 のべき乗である場合、これにより、下の 2 乗、2 つのシフト、および 2 つの加算が得られます。各反復でNが減少すると、効率が向上する可能性があります (対称性は、長方形ではなく三角形の各点を訪問することを意味します) が、それでも O(N²) です。

利用する別のより良い対称性があるかもしれません。

于 2009-09-04T09:09:06.463 に答える
-1

2 進数 A を持っている場合、それは (熱心な読者に証明を残します) として (2^n + B) として表すことができます。これは 2^2n + 2^(n+1)B + B として 2 乗できます。 ^2. 次に、B がゼロに等しくなるような点まで展開を繰り返すことができます。私はあまり詳しく見ていませんが、直感的には、2 乗関数を汎用の乗算よりもアルゴリズムのステップを少なくすることができるはずだと感じています。

于 2009-09-04T08:02:26.490 に答える
-1

2 nの平方根は 2 n / 2または 2 n >> 1であるため、数値が 2 の累乗である場合、累乗がわかればすべてが完全に単純になります。乗算はさらに簡単です: 2 4 * 2 8は 2 4+8です。あなたが行ったこの声明には意味がありません。

于 2009-09-04T06:08:46.170 に答える
-4

あなたの発言は完全に間違っていると思います

2 つの 2 進数の乗算には n^2 の時間がかかります

2 つの 32 ビット数の乗算には、正確に 1 クロック サイクルかかります。64 ビット プロセッサでは、2 つの 64 ビット数を乗算するには、正確に 1 クロック サイクルかかると想定します。32 ビット プロセッサが 1 クロック サイクルで 2 つの 64 ビット数を乗算できることは、私にとって驚くべきことではありません。

yet squaring a number can be done more efficiently somehow.

数を 2 乗することは、その数をそれ自体で乗算するだけなので、単純な乗算にすぎません。CPUには「二乗」演算はありません。

「二乗」と「2 のべき乗」を混同している可能性があります。2 の乗算は、すべてのビットを 1 桁分「左」にシフトすることで実装できます。4 を掛けると、すべてのビットが 2 桁分「左」にシフトします。8で、3ポジション。しかし、このトリックは 2 の累乗にしか適用できません。

于 2009-09-04T06:35:25.963 に答える