アルゴリズム
13 x 19 -> 0 6 38 19 3 76 -> 1 152 -> 95 0 304 247 ^^^
2つの乗算された数値を並べて書き込みます-それらは2つの列の見出しになります。 3番目の列には、増加する量が含まれます。
左の列の数値が奇数の場合、右の列の数値を増加する量に追加します。 最初はゼロになります。
次に、下の左の列に、ヘッダーの数値を半分に分割して書き込みます（残りは破棄されます）。 13/2 =6。2番目の列には、列見出しを2倍にした数19 * 2 = 38を書き込みます。
左の列の数値は偶数であるため、増分量は増加しません。
次に、2で割って倍にするプロセスを繰り返します。 左の列には3があり、この数は奇数です。したがって、19 76に加算して95を取得します。
手順を繰り返すと、結果として247が得られます。
検証：
13〜19の平均は16
16 ^ 2 = 256
16-13 = 3
3 ^ 2 = 9
256-9 = 247
アルゴリズムを終了しない場合、左の列にゼロがあり、0は偶数であるため、増加する合計に何も追加する必要はありません。 したがって、左の列に1つが表示されるとすぐに、3番目の列に答えが表示されます。
証明
なぜ機能するのですか？ これは、通常のバイナリの長い乗算であると言えます。 しかし、より長い説明を行いますが、それは同時により一般的なものになります。
左の列Aの数、2番目の列-B、増加する合計-R、および答え-Pを示します。したがって、
（A * B）+ R = P
次に、Aが偶数の場合、つまりA = 2kのkです。 方程式を書き換えます。
（2k * B）+ R = P
または、同じこと：
（k * 2B）+ R = P
Aをその値の半分に、Bをdouble値に置き換え、それらをA 'およびB'と呼ぶと、次のようになります。
（A '* B'）+ R = P
つまり、Aが偶数の場合、最初の数値が半分になり、2番目の数値が2倍になり、方程式は真になります。 そして、それが奇妙な場合は？ その後、A = 2k + 1
A * B + R = P
（2k + 1）* B + R = P
2k * B + B + R = P
2k * B +（B + R）= P
K * 2B +（B + R）= P
A '* B' +（B + R）= P
また、AからAの半分をマークし、BからBを2倍にしました。
私たちの方程式は、次の場合に当てはまります。
- 2番目の列の数値を増加量に追加しました
- 最初の列を半分にした
- 二倍に
アルゴリズムのステップを実行するとき、方程式はバランスが保たれていることがわかります。
ゼロになると、次のようになります。
0 * B + R = P
またはR =P。 私たちの成長量は望ましい結果に等しいです。
一般化1：べき乗
2 13を数えてみましょう。 累乗する場合、加算ではなく数値を乗算するため、アルゴリズムを改善します。
乗算で加算を置き換えます
二乗して二倍に置き換えます
====== ==== 13 2 -> 1 6 4 2 3 16 -> 1 256 -> 32 0 65546 8192 ^^^^
増分積は1から始まります。13は奇数なので、2番目の列に増分積を掛けて2を取得します。13と2を半分にします。
6-さらに、増分積を乗算しません。 6と4を半分にし、16を取得します。
3-奇数。成長する製品に16を掛けると、32になります。最初の列を半分にし、2番目の列を2乗します。
最終ステップ：1-奇数、256に32を掛けると、8192が得られます。これが答えです。
このアルゴリズムの証明は過去のものと同じですが、ちょうど今私たちの方程式は次のようになります。
B A * R = E
一般化2：行列
しかし、このアルゴリズムは、数値を累乗するだけでなく、行列にも使用できます。 成長する製品は単一のマトリックスから始まり、2列目には次数を取得する必要のあるマトリックスが書き込まれます。 そしてそれは動作します。
次は、Pythonで書かれた関数です。 負でない次数、および連想乗算をサポートする任意のタイプの「ベース」に対して機能します。 つまり、乗算がモノイドであるすべてのコレクションに対して機能します。
def fast_exp(b,e,I=1): # b^e, e – . # I, # , result = I while e > 0: if is_odd(e): result *= b b *= b e = e / 2 return result
これを理解する必要すらありません。行列に対して機能することを知るだけで十分です。
参照資料