13

製品を計算するための最も効率的な方法は何ですか

a 1 b 2 c 3 d 4 e5 ..。_

二乗のコストが乗算の約半分であると仮定しますか？オペランドの数が100未満です。

乗算時間がオペランドの長さの2乗に比例する場合にも（のようにjava.math.BigInteger）簡単なアルゴリズムはありますか？

最初の（そして唯一の）答えは、操作の数に対して完璧です。

おかしなことに、かなりBigIntegerのサイズに適用すると、この部分はまったく問題になりません。最適化なしでabbcccddddeeeeeを計算する場合でも、ほぼ同じ時間がかかります。

ほとんどの時間は最終的な乗算に費やされます（BigIntegerカラツバ、トゥームクック、FFTなどのよりスマートなアルゴリズムは実装されていないため、時間は2次式です）。重要なのは、中間被乗数がほぼ同じサイズであることを保証することです。つまり、ほぼ同じサイズの数p、q、r、sが与えられた場合、 （pq）（rs）の計算は通常（（pq）r）sよりも高速です。速度比は、数十のオペランドで約1：2のようです。

アップデート

Java 8では、にカラツバ法とToom-Cook法の両方の乗算がありBigIntegerます。

4

2 に答える 2

8

これが最適なアプローチであるかどうかは絶対にわかりませんが（漸近的に最適だと思いますが）、すべてをO(N)乗算で行うことができます。a * b^2 * c^3次のように引数をグループ化しますc * (c*b) * (c*b*a)。擬似コードの場合：

result = 1
accum = 1
for i in 0 .. arguments:
  accum = accum * arg[n-i]
  result = result * accum

入力引数N-1を乗算するためだけに乗算を使用する必要があるため、漸近的に最適だと思います。N

于 2012-10-25T22:01:38.200 に答える
1

2012年10月26日の編集で述べたように、オペランドのサイズが超線形の
乗算時間であるため、長い操作のオペランドのサイズを同じように保つと便利です（特に、使用可能なToom-Cookがtoom-2のみの場合）。 （からつば））。完全な最適化を行わない場合は、オペランドをキューに入れて、（重要な）長さの順にポップできるようにすることで、ヒップから適切なショットに見えます。
次に、特殊なケースがあります。0、2の累乗、1つの因子が（そうでない場合）「自明」である乗算（「1桁の長さの乗算」、因子の長さの合計で線形）。
そして、二乗は一般的な乗算よりも単純/高速です（質問は½を仮定することを示唆しています）。これは次の戦略を示唆します。


  • 前処理ステップで、 0に遭遇した場合 、指数結果0で重み付けされた後続ゼロをカウントします。

  • 末尾のゼロを削除し、値が残っていない場合は結果1 の結果値を破棄します
  • 複数回発生する値を見つけて組み合わせる
  • 「最短」の番号を抽出できるようにキューを設定します。各ペア（数、指数）について、2乗によるべき乗が乗算される因子を挿入します
  • オプション：「些細な要素」（上記を参照）を組み合わせて、再挿入
    します。これについてはどうすればよいかわかりません。自明な長さ12の因数を言い、初期の因数は長さ1、2、…、10、11、12、…、nです。最適には、12から7つの些細な要素に対して1 + 10、2 + 9、…を組み合わせます。最短を組み合わせると、12から8に対して3、6、9、12が得られます。
  • 因子の最短のペアを抽出し、数値が1つだけになったら乗算して再挿入する
    と、最初のステップのゼロが追加されます。

（因数分解が安価である場合、安価な二乗を最大限に活用するには、かなり早い段階で実行する必要があります。）

于 2019-11-21T07:12:20.133 に答える