先日、このアルゴリズムに対処する必要がありましたが、グーグルでのクイック検索では何の価値もありませんでした。 Habréで見つかった記事は1つだけでしたが、それは実際には役に立ちませんでした。 理解したので、アクセス可能な形式で一般と共有しようとします。

アルゴリズム

Karatsubaアルゴリズムは、計算量n ^{log ₂ 3の}高速乗算法です。 素朴なアルゴリズムですが、列による乗算にはn ^2回の演算が必要です。 数字の長さが数十文字より短い場合（より正確には、実験的に決定された場合）、通常の乗算​​はより速く機能することに注意してください。

ある数体系BASEに長さnの2つの数AとBがあると想像してください。

A = a _n-1 a _n-2 ... a ₀

B = b _n-1 a _n-2 ... a ₀ 、ここでa _？ b _？ -値acc。 放電桁。

それらはそれぞれ、長さm = n / 2の半分の2つの部分の合計として表すことができます（nが奇数の場合、一方の部分はもう一方よりも1桁短くなります。

A ₀ = a _m-1 a _m-2 ... a ₀

A ₁ = a _n-1 a _n-2 ... a _m

A = A ₀ + A ₁ * BASE ^m



B ₀ = b _m-1 b _m-2 ... b ₀

B ₁ = b _n-1 b _n-2 ... b _m

B = B ₀ + B ₁ * BASE ^m



次に：A * B = （A ₀ + A ₁ * BASE ^m ）*（B ₀ + B ₁ * BASE ^m ）= A ₀ * B ₀ + A ₀ * B ₁ * BASE ^m + A ₁ * B ₀ * BASE ^m + A ₁ * B ₁ * BASE ^{2 * m} = A ₀ * B ₀ +（ A ₀ * B ₁ + A ₁ * B ₀ ）* BASE ^m + A ₁ * B ₁ * BASE ^{2 * m}

ここでは、4つの乗算演算が必要です（式の一部* BASE ^{？* M}は乗算ではなく、実際に結果を記録する場所、放電を示します）。 しかし、一方で：

（A ₀ + A ₁ ）*（B ₀ + B ₁ ）= A ₀ * B ₀ + A ₀ * B ₁ + A ₁ * B ₀ + A ₁ * B ₁

両方の式で強調表示されている部分を確認します。 単純な変換の後、乗算演算の数を3に減らすことができます。2つの乗算を1つおよびいくつかの加算および減算演算で置き換えます。実行時間は1桁少なくなります。

A ₀ * B ₁ + A ₁ * B ₀ = （A ₀ + A ₁ ）*（B ₀ + B ₁ ） -A ₀ * B ₀ - A ₁ * B ₁



式の最終形式：

A * B = A ₀ * B ₀ +（（A ₀ + A ₁ ）*（B ₀ + B ₁ ）-A ₀ * B ₀ -A ₁ * B ₁ ）* BASE ^m + A ₁ * B ₁ * BASE ^{2 * m}



グラフィカル表現：

例

たとえば、10進数の12345と98765の2つの8桁の数値を乗算します。



アルゴリズムの再帰的な性質は、画像からはっきりと見えます。 4桁未満の数値の場合、単純な乗算が使用されました。

C ++実装

おそらく、数字が保存されている期間から始めるべきです。 長い数字を配列の形式で表すのが便利です。各要素は数字に対応し、下位の数字は低いインデックスの要素に保存されます（つまり、背中合わせに）-このように処理すると便利です。 例：

int long_value[] = { 9, 8, 7, 6, 5, 4} // 456789





パフォーマンスを向上させるために、ベースシステム内の最大数を番号システムの基礎として選択することをお勧めします。 ただし、同時に次の条件が課されます。

1. 選択した数体系の最大数の二乗は、選択した基本型に収まる必要があります。 これは、中間計算で1つのカテゴリの製品を別のカテゴリに格納するために必要です。
2. 選択したベースタイプのサインを取ることをお勧めします。 これにより、いくつかの中間正規化を取り除くことができます。
3. 最大数のいくつかの平方の合計を放電に配置することをお勧めします。 これにより、いくつかの中間的な正規化が取り除かれます。

以下は、必要なすべてのサポート宣言と関数を備えたコメント付きの作業乗算関数です。 より高いパフォーマンスを得るには、数値システムの基数、数字を格納するタイプを変更し、単純な乗算を行う場所で小さなコードのコメントを解除する必要があります。

1. #include <cstring>
3. #define BASE 10 //番号体系
4. #define MIN_LENGTH_FOR_KARATSUBA 4 //短い数字には2次アルゴリズムが乗算されます
5. typedef int digit; //数値の数字に対してのみ使用されます
6. typedef unsigned long int size_length; //長い数字を入力します
8. 名前空間 std を使用し ます 。
10. struct long_value { //長い数値のタイプ
11. 数字*値; //数字の数字が逆順に書かれた配列
12. size_length length; //数が長い
13. };
15. long_value sum（long_value a、long_value b）{
16. / * 2つの長い数字を追加する関数。 異なる長さの数字が合計される場合
17. *その後、長い方が最初の引数として渡されます。 新しい返品
18. *非正規化数。
19. * /
20. long_value s;
21. s.length = a.length + 1;
22. s.values = 新しい数字[s.length];
24. s.values [a.length-1] = a.values [a.length-1];
25. s.values [a.length] = 0;
26. for （size_length i = 0; i <b.length; ++ i）
27. s.values [i] = a.values [i] + b.values [i];
28. return s;
29. }
31. long_value＆sub（long_value＆a、long_value b）{
32. / * 1つの長い数値を別の数値から減算する関数。 最初の内容を変更します
33. *数字。 最初の番号への参照を返します。 結果は正規化されません。
34. * /
35. for （size_length i = 0; i <b.length; ++ i）
36. a.values [i]-= b.values [i];
37. を返します;
38. }
40. void normalize（long_value l）{
41. / *番号の正規化-番号体系に従って各桁を表示します。
42. *
43. * /
44. for （size_length i = 0; i <l.length-1; ++ i）{
45. if （l.values [i]> = BASE）{ //数値が最大値より大きい場合、転送は整理されます
46. 桁上げ= l.values [i] / BASE;
47. l.values [i + 1] + =キャリーオーバー;
48. l.values [i]-=キャリーオーバー* BASE;
49. } else if （l.values [i] <0）{ //少ない場合はローン
50. 桁上げ=（l.values [i] + 1）/ BASE-1;
51. l.values [i + 1] + =キャリーオーバー;
52. l.values [i]-=キャリーオーバー* BASE;
53. }
54. }
55. }
57. long_value karatsuba（long_value a、long_value b）{
58. long_value製品; //結果の製品
59. product.length = a.length + b.length;
60. product.values = 新しい数字[product.length];
62. if （a.length <MIN_LENGTH_FOR_KARATSUBA）{ //数値が短い場合、単純乗算を適用します
63. memset（product.values、0、 sizeof （digit）* product.length）;
64. for （size_length i = 0; i <a.length; ++ i）
65. for （size_length j = 0; j <b.length; ++ j）{
66. product.values [i + j] + = a.values [i] * b.values [j];
67. / * MIN_LENGTH_FOR_KARATSUBAまたはBASEを変更する場合は、次のコメントを外します
68. *ラインとピックアップacc。 ビットのオーバーフローを避けるための値。
69. *たとえば、10進法の場合、100という数字は整理されていることを意味します
70. * 1回の排出で1を転送、200-1回の排出で2を転送、2回後に5000-5。
71. * if（product.values [i + j]> = 100）{
72. * product.values [i + j]-= 100;
73. * product.values [i + j + 2] + = 1;
74. *}
75. * /
76. }
77. } else { //唐atsu掛け
78. long_value a_part1; //の下部
79. a_part1.values = a.values;
80. a_part1.length =（a.length + 1）/ 2;
82. long_value a_part2; //の高い部分
83. a_part2.values = a.values + a_part1.length;
84. a_part2.length = a.length / 2;
86. long_value b_part1; // bの下部
87. b_part1.values = b.values;
88. b_part1.length =（b.length + 1）/ 2;
90. long_value b_part2; // bの高い部分
91. b_part2.values = b.values + b_part1.length;
92. b_part2.length = b.length / 2;
94. long_value sum_of_a_parts = sum（a_part1、a_part2）; // aの部分の合計
95. ノーマライズ（sum_of_a_parts）;
96. long_value sum_of_b_parts = sum（b_part1、b_part2）; //数bの部分の合計
97. ノーマライズ（sum_of_b_parts）;
98. long_value product_of_sums_of_parts = karatsuba（sum_of_a_parts、sum_of_b_parts）;
99. //部品の合計の積
101. long_value product_of_first_parts = karatsuba（a_part1、b_part1）; //ジュニアメンバー
102. long_value product_of_second_parts = karatsuba（a_part2、b_part2）; //シニアメンバー
103. long_value sum_of_middle_terms = sub（sub（product_of_sums_of_parts、product_of_first_parts）、product_of_second_parts）;
104. //中間のメンバーの合計を見つける
106. / *
107. *多項式の合計
108. * /
109. memcpy（product.values、product_of_first_parts.values、
110. product_of_first_parts.length * sizeof （digit））;
111. memcpy（product.values + product_of_first_parts.length、
112. product_of_second_parts.values、product_of_second_parts.length
113. * sizeof （数字））;
114. for （size_length i = 0; i <sum_of_middle_terms.length; ++ i）
115. product.values [a_part1.length + i] + = sum_of_middle_terms.values [i];
117. / *
118. *ストリッピング
119. * /
120. delete [] sum_of_a_parts.values;
121. delete [] sum_of_b_parts.values;
122. delete [] product_of_sums_of_parts.values;
123. 削除[] product_of_first_parts.values;
124. delete [] product_of_second_parts.values;
125. }
127. 正規化（製品）; //数値の最終的な正規化
129. 返品 ;
130. }

*このソースコードは、 ソースコードハイライターで強調表示されました。