カラツバ法 - ノリの悪い日記

大きな数のかけ算は, 基本的に筆算などしないことにしているが, 計算機科学のカラツバ法はときどき遊びでやってみることがある.

たとえば,

$956 \times 832=(950+6)(830+2)$

を計算するのに

$\begin{eqnarray} z_2 &=& 95\times 83 \\ &=& (100-5)(100-17)\\ &=& 100(100-22) + 5 \times 17\\ &=& 7885 \end{eqnarray}$

$\begin{eqnarray} z_0 &=& 6\times 2\\ &=& 12 \end{eqnarray}$

$\begin{eqnarray} z_1 &=& z_0 + z_2 - (95-6)(83-2)\\ &=& 7897- 89 \times 81\\ &=& 7897 - 7209\\ &=& 688\\ \end{eqnarray}$

したがって,

$\begin{eqnarray} 956 \times 832 &=& z_2 \times 100 +z_1 \times 10 + z_0\\ &=& 788500 + 6880 + 12\\ &=& 795380 + 12\\ &=& 795392 \end{eqnarray}$

かけ算の結果を使いまわして, かけ算を $3$ 回だけ実行すれば良いのがポイントなのだ. これくらいのかけ算だと有難みはあまりないが, 桁数がもっと増えてくると $4$ 回のかけ算が $3$ 回ですむ差は大きい (計算にあらわれる乗算は再帰的に行える). なんと, 1960 年になるまで, このかけ算のやり方を人類が思いつくことはなかったのである.

$2$ つ前の記事の $11^5 \times 19$ のかけ算のような場合は特に簡単で, 本当は力任せにやったって大して時間はかからない. この計算は基本的にかけ算はいらず, $0$ をつけるのと足し算だけである.

$11 \times 19 = 209$

$\begin{eqnarray} 209 \times 11 &=& 20 \times 100 + 10(20+9)+9\\ &=& 2299\\ \end{eqnarray}$

$\begin{eqnarray} 2299 \times 11 &=& 229 \times 100 + 10(229+9)+9\\ &=& 22900 + 2380 + 9\\ &=& 25289 \end{eqnarray}$

$\begin{eqnarray} 25289 \times 11 &=& 2528 \times 100 \\ && \quad+ 10(2528+9)+9\\ &=& 252800+ 25370 + 9\\ &=& 278179 \end{eqnarray}$

$\begin{eqnarray} 278179 \times 11 &=& 27817 \times 100 \\ && \quad + 10(27817+9)+9\\ &=& 2781700+ 278260+ 9\\ &=& 3059969 \end{eqnarray}$

ちなみに, 最初の $956 \times 832$ という計算だが, 次のようにして乗算を $2$ 回にすることは可能である. カラツバ法のかけ算の結果を使いまわすという考え方は計算の工夫のヒントになる.

$\begin{eqnarray} 956 \times 832 &=&956 \times (800 + 4 \times 8)\\ \end{eqnarray}$

と見て,

$\begin{eqnarray} 956 \times 8 &=& (1000-44)\times 8\\ &=& 8000- 352\\ &=& 7648\\ \end{eqnarray}$

したがって,

$\begin{eqnarray} 956 \times 832 &=&956 \times (800 + 4 \times 8)\\ &=& 764800 + 4 \times 7648\\ &=& 764800 + 30592\\ &=& 795392\\ \end{eqnarray}$