足し算と掛け算だけを含む計算をするとします。
(a+b)*(c+d)
これは、他の多くの方法で実行できます。
a*(c+d) + b*(c+d)
a*c + a*d + b*c + b*d
加算と乗算に関しては、示されている 3 つの例のそれぞれに必要な演算の数は、それぞれ (2,1) (3,2) (3,4) です。明らかに、目標が操作の総数を減らすことである場合、最初の操作が優れています。最小数の操作を必要とする計算順序を見つけるための任意の式が与えられた場合、方法はありますか?
注: この質問は、CS クラウドの洞察と視点のために SE.math から再質問されています。
必要なのは、可能なすべての同等の代数式を効果的に生成し、最もコストのかからないステップ数を選択することです (ほとんどのマシンでは、X を 3 倍するよりも、X を 3 回加算する方が安価です)。
「同等の」式の数は無限であるため、これを行うのは実際的ではありません。
しかし、Pelegrí-Llopart は、 "BURS" (bottom-up rewrite system)と呼ばれる、一定数の代数的書き換え規則が与えられた場合に最適なコードを生成するスキームを見つけました。これは、一部のコード ジェネレーターに実装されています。
本質的に、彼は、可能な適用された書き換えのセットを追跡する状態を持つ大きなオートマトンをオフラインで構築します。各状態は、発生時に何を生成するかを知っているため、コード生成のためのオンライン時間は安価です。
変数の累乗と整数係数を無視すると、これはカルノー マップの問題になります。
K-Map は積和形式と積和形式で表すことができ、それぞれが 2 進回路を表します。「最小操作」形式は、最適化されたバイナリ回路を表しますよね?
単項式の多項式を効率的に評価するためのホーナーの規則があります。それによると、与えられた次数 n の多項式
p(x) = n x n + n-1 x n-1 + ... + a 1 x 1 + a 0
n 回の乗算のみが必要です (一見すると、n+(n-1)+(n-2)+...+1 = n(n+1)/2 ではありません)。これは、多項式が次のように書き換えられるためです。
p(x) = (((a n x + a n-1 )x + a n-2 )x + ... a 1 )x + a 0
1 つのアイデア - 変数をブール値と見なし、maxterm フォームの リンク テキストを書きましょう。
一般的なケースについてはわかりませんが、多項式を因数分解するとパフォーマンスが向上するようです。遠いコンプ科学コースからの例:
a * x^2 + b * x + c
x を因数分解することで改善されます。
x * (a * x + b) + c