掛け算の筆算と畳み込み

同義語：long multiplication as convolution

概要

前提知識: 整数の筆算の仕組み, 多項式の筆算と組立除法, 分配法則, 二項係数

掛け算の筆算では、1 段ごとに繰り上げながら計算する。しかし、繰り上げを最後まで後回しにしても同じ答えになる。後回しにすると、積の各位に集まる数は「位の番号の和が一定になる積を全部足したもの」になる。この形の和を 畳み込み という。この記事では、掛け算の筆算を畳み込みとして見直し、そこから分かることを 3 つ紹介する。$11^4=14641$ のように積に二項係数がそのまま現れる理由、多項式の積を整数の掛け算 1 回で求める方法（Kronecker の置き換え）、そして数を半分ずつに分けて掛け算の回数を減らす方法（Karatsuba の方法）である。

高校での出発点：繰り上げずに掛ける

$234\times567$ を繰り上げずに計算する

$234\times567$ で、1 桁どうしの積 $9$ 個をすべて書き、同じ位に入るものどうしを足す（図 1）。$234=2\cdot10^2+3\cdot10+4$、$567=5\cdot10^2+6\cdot10+7$ なので、$2\times5$ は $10^2\cdot10^2=10^4$ の位、$3\times5$ と $2\times6$ は $10^3$ の位、……に入る。

$10^4$ の位：$2\cdot5=10$
$10^3$ の位：$3\cdot5+2\cdot6=15+12=27$
$10^2$ の位：$4\cdot5+3\cdot6+2\cdot7=20+18+14=52$
$10^1$ の位：$4\cdot6+3\cdot7=24+21=45$
$10^0$ の位：$4\cdot7=28$
ここで初めて、下の位から繰り上げる。$28$ は数字 $8$・繰り上がり $2$。$45+2=47$ は数字 $7$・繰り上がり $4$。$52+4=56$ は数字 $6$・繰り上がり $5$。$27+5=32$ は数字 $2$・繰り上がり $3$。$10+3=13$。よって $234\times567=132678$ で、ふつうの筆算の答えと一致する。

234×567 の 9 個の積。同じ色の積が同じ位に入り、その和が 10, 27, 52, 45, 28 になる

11 の累乗とパスカルの三角形

$11^2=121$、$11^3=1331$、$11^4=14641$ である。数字の並び $1,2,1$、$1,3,3,1$、$1,4,6,4,1$ は、パスカルの三角形の段（二項係数）と同じである。ところが $11^5=161051$ は、二項係数 $1,5,10,10,5,1$ とは違って見える。

2 つの例から、次の問いが出てくる。

繰り上げを最後まで後回しにしても同じ答えになるのはなぜか。→ thm-mcv-conv
$11^4$ の数字が二項係数になるのはなぜか。$11^5$ で崩れるのはなぜか。→ cor-mcv-nocarry、ex-mcv-eleven-n
多項式の積を、整数の掛け算 1 回で求められるか。→ prop-mcv-kronecker

係数の個数が $n$ の多項式どうしの掛け算で、係数どうしの掛け算を $n^2$ 回より少なくできるか。整数ではどうか。→ thm-mcv-karatsuba、prop-mcv-count、rem-mcv-integer

筆算の見方	この記事の言葉
同じ位に入る積を集めて足す	数列の畳み込み
繰り上がりを最後に 1 回だけする	畳み込みのあと繰り上げる
繰り上がりが起きない掛け算	数字がそのまま畳み込みになる
係数を大きな位に入れて掛ける	Kronecker の置き換え
数を上と下の半分に分けて、掛け算を 4 回から 3 回にする	Karatsuba の方法

数列の畳み込み

整数の数字や多項式の係数を、下の位から 番号をつけて並べる。$234$ なら $(a_0,a_1,a_2)=(4,3,2)$ である（$a_i$ は $10^i$ の位の数字）。

数列の畳み込み

有限個の数の並び $a=(a_0,a_1,\dots,a_m)$ と $b=(b_0,b_1,\dots,b_n)$ に対して、
$$ (a*b)_k=\sum_{i+j=k}a_ib_j\qquad(k=0,1,\dots,m+n) $$
で定まる並び $a*b=\bigl((a*b)_0,\dots,(a*b)_{m+n}\bigr)$ を、$a$ と $b$ の 畳み込み という。和は $0\le i\le m$、$0\le j\le n$、$i+j=k$ を満たすすべての組 $(i,j)$ についてとる。

番号の和 $i+j$ が一定の積を集める、というのが畳み込みの意味である。$b$ を逆向きに並べて $a$ の下にずらしながら重ね、重なったところの積を足す、と見ることもできる。$b$ を逆向きに並べて重ねる様子は、紙を折り返して重ねることにたとえられる。

畳み込みを計算する

$(1,1)*(1,1)$：$k=0$ は $1\cdot1=1$、$k=1$ は $1\cdot1+1\cdot1=2$、$k=2$ は $1\cdot1=1$。よって $(1,2,1)$ である。
$(1,2,3)*(1,1)$：$k=0$ は $1$、$k=1$ は $2+1=3$、$k=2$ は $3+2=5$、$k=3$ は $3$。よって $(1,3,5,3)$ である。
$234$ と $567$ の数字の並び $(4,3,2)*(7,6,5)$：$k=0$ は $4\cdot7=28$、$k=1$ は $4\cdot6+3\cdot7=45$、$k=2$ は $4\cdot5+3\cdot6+2\cdot7=52$、$k=3$ は $3\cdot5+2\cdot6=27$、$k=4$ は $2\cdot5=10$。よって $(28,45,52,27,10)$ で、ex-mcv-start の各位の和である。

畳み込みは、多項式の積の係数そのものである。多項式の筆算と組立除法で見たように、$f(x)=\sum_ia_ix^i$ と $g(x)=\sum_jb_jx^j$ の積の $x^k$ の係数は、畳み込み $(a*b)_k$ である。番号を $n$ で割った余りで数える「巡回的な畳み込み」が、離散 Fourier 変換で成分ごとの掛け算に変わることは離散Fourier変換と反転公式で扱う。

主定理：積の各位は畳み込み、繰り上がりは後回しにできる

積の各位は畳み込みで与えられる

$0$ 以上の整数 $a=\sum_{i=0}^{m}a_i10^i$、$b=\sum_{j=0}^{n}b_j10^j$（$a_i,b_j$ は数字）について、
$$ ab=\sum_{k=0}^{m+n}(a*b)_k\,10^k $$
が成り立つ。$c_k=(a*b)_k$ に整数の筆算の仕組みの繰り上がりの補題の手順を使うと、$ab$ の数字が得られる。とくに、筆算のように段ごとに繰り上げても、畳み込みを全部計算してから最後に繰り上げても、得られる数字は同じである。

分配法則で展開し、一意性を使う

方針：積を分配法則で $(m+1)(n+1)$ 個の積に分け、位ごとにまとめる。答えが同じになることは、10 進法の表し方の一意性から出る。
段 1（展開）。分配法則により
$$ ab=\Bigl(\sum_{i=0}^{m}a_i10^i\Bigr)\Bigl(\sum_{j=0}^{n}b_j10^j\Bigr)=\sum_{i=0}^{m}\sum_{j=0}^{n}a_ib_j\,10^{i+j} $$
である（$10^i\cdot10^j=10^{i+j}$）。
段 2（位ごとにまとめる）。段 1 の和の項を $k=i+j$ ごとにまとめ、分配法則で $10^k$ をくくり出すと、$10^k$ の係数は $\sum_{i+j=k}a_ib_j=(a*b)_k$ になる。よって $ab=\sum_k(a*b)_k10^k$ である。
段 3（繰り上げ）。各 $(a*b)_k$ は数字の積の和なので $0$ 以上の整数である。繰り上がりの補題により、$(a*b)_k$ を下から繰り上げると $ab=\sum_kd_k10^k$（$0\le d_k\le9$）となり、10 進法の表し方の一意性により、$d_k$ は $ab$ の数字である。
段 4（どの順に繰り上げても同じ）。筆算のように段ごとに繰り上げても、計算の途中で数を変えない操作（位ごとの和、$10$ 個の $10^k$ を $1$ 個の $10^{k+1}$ に替えること）しかしていないので、最後に得る数字の並びは $ab$ の 10 進法の表し方である。表し方はただ 1 通りなので、繰り上げ方によらず同じ数字の並びになる。$\square$

畳み込みのあとで繰り上げる

$234\times567$：ex-mcv-conv の $(28,45,52,27,10)$ を繰り上げると $132678$ である（ex-mcv-start）。
$99\times99$：$(9,9)*(9,9)=(81,162,81)$。繰り上げると、$81$ は数字 $1$・繰り上がり $8$、$162+8=170$ は数字 $0$・繰り上がり $17$、$81+17=98$ は数字 $8$・繰り上がり $9$、最後に $9$。よって $99\times99=9801$ である。繰り上がり $17$ のように、後回しにすると繰り上がりは $1$ 桁に収まらないことがある。

畳み込みの各項の大きさ

$(a*b)_k$ は、$i+j=k$ を満たす組 $(i,j)$ の個数だけの、数字どうしの積の和である。組の個数は $m+1$ と $n+1$ の小さいほう以下で、各積は $81$ 以下なので、
$$ (a*b)_k\le81\cdot\min(m+1,\,n+1) $$
である。$99\times99$ では $81\cdot2=162$ で、$k=1$ の項 $162$ はちょうどこの上限に等しい。

繰り上がりが起きないとき

畳み込みの項がどれも $9$ 以下なら、繰り上げる必要がない。そのとき積の数字は畳み込みそのものになる。

繰り上がりが起きない積

thm-mcv-conv の記号で、すべての $k$ について $(a*b)_k\le9$ ならば、$ab$ の $10^k$ の位の数字は $(a*b)_k$ である。

繰り上がりが 0 のまま進む

方針：繰り上がりの補題の手順で、繰り上がりがずっと $0$ であることを帰納法で示す。
$c_k=(a*b)_k$ とおく。繰り上がりの補題では $t_0=0$ から始め、$c_k+t_k$ を $10$ で割った商を $t_{k+1}$、余りを $d_k$ とする。$t_k=0$ と仮定すると、$c_k+t_k=c_k\le9$ なので、商 $t_{k+1}=0$、余り $d_k=c_k$ である。数学的帰納法（数学的帰納法と整列性）により、すべての $k$ で $t_k=0$、$d_k=c_k$ である。thm-mcv-conv により $d_k$ が $ab$ の数字なので、数字は $(a*b)_k$ である。$\square$

$11^n$ は、$n$ 個の $(1,1)$ を次々に畳み込んだ並びを繰り上げたものである。この並びは、$(1+x)^n$ の係数、つまり二項係数 $\binom n0,\binom n1,\dots,\binom nn$ である（二項定理と組合せの恒等式）。

11 の累乗が二項係数になる範囲

$n\le4$ では二項係数はすべて $9$ 以下なので（$n=4$ で最大の $\binom42=6$）、cor-mcv-nocarry により $11^n$ の数字は二項係数そのものである。$11^4=14641$。
$n=5$ では二項係数は $1,5,10,10,5,1$ で、$10$ が $9$ を超える。下の位から繰り上げると、$1$；$5$；$10$ は数字 $0$・繰り上がり $1$；$10+1=11$ は数字 $1$・繰り上がり $1$；$5+1=6$；$1$。上の位から読んで $161051$ となり、$11^5=161051$ と一致する。

1 が並んだ数の 2 乗

$111111111$（$1$ が $9$ 個）の 2 乗。$(1,\dots,1)*(1,\dots,1)$（$1$ が $9$ 個ずつ）の $k$ 番目の項は、$i+j=k$、$0\le i,j\le8$ を満たす組の個数で、$k=0,1,\dots,16$ に対して $1,2,\dots,8,9,8,\dots,2,1$ である。すべて $9$ 以下なので、$111111111^2=12345678987654321$ である。
$1$ が $10$ 個の $1111111111$ では、真ん中の項が $10$ になる。繰り上がりが起きて、$1111111111^2=1234567900987654321$ となり、数字は $1,2,\dots$ の並びにならない。

101 と 1001 の累乗

$101=10^2+1$ は、$x^2+1$ に $x=10$ を入れたものである。$(x^2+1)^5=x^{10}+5x^8+10x^6+10x^4+5x^2+1$ なので、
$$ 101^5=10^{10}+5\cdot10^8+10\cdot10^6+10\cdot10^4+5\cdot10^2+1=10510100501 $$
である。$2$ 桁ずつ区切ると $1|05|10|10|05|01$ で、二項係数 $1,5,10,10,5,1$ が $2$ 桁ずつ並ぶ。$100$ を 1 つの位と見ると（100 進法）、どの係数も $99$ 以下なので繰り上がりが起きない。同じ理由で $1001^5=1005010010005001$ は、$3$ 桁ずつ区切ると $1|005|010|010|005|001$ である。

Kronecker の置き換え：多項式の積を整数の掛け算 1 回で

ex-mcv-101 の考え方を逆に使うと、係数が $0$ 以上の整数の多項式の積を、整数の掛け算 1 回で求められる。$x$ に十分大きな数 $B$ を入れて掛け、答えを $B$ 進法で読めばよい。

大きな底に代入して積の係数を読む

$f,g$ を、係数が $0$ 以上の整数の多項式とし、整数 $B\ge2$ は「$fg$ の係数がすべて $B$ 未満」を満たすとする。このとき、整数 $f(B)\,g(B)$ を $B$ 進法で表したときの $B^k$ の位の数字は、$fg$ の $x^k$ の係数に等しい。
とくに、$f$ と $g$ の係数がすべて $M$ 以下で、$f$ の項が $m+1$ 個以下、$g$ の項が $n+1$ 個以下（次数がそれぞれ $m$ 以下、$n$ 以下）のとき、$B>M^2\cdot\min(m+1,\,n+1)$ ならこの条件が成り立つ。

代入と $B$ 進法の一意性

方針：多項式の筆算と組立除法の「代入は積を保つ」ことと、$B$ 進法の表し方の一意性を使う。後半は rem-mcv-size と同じ評価である。
段 1。$fg=\sum_kc_kx^k$ とする。代入は積を保つので $f(B)g(B)=(fg)(B)=\sum_kc_kB^k$ である。
段 2。仮定より $0\le c_k\le B-1$ なので、$\sum_kc_kB^k$ は $f(B)g(B)$ の $B$ 進法の表し方（上の位の $0$ を除く）である。$B$ 進法の表し方はただ 1 通りなので（整数の筆算の仕組み。$10$ を $B$ に取りかえても同じ証明が通る）、$B^k$ の位の数字は $c_k$ である。
段 3（十分条件）。$c_k=\sum_{i+j=k}a_ib_j$ の項の個数は $\min(m+1,n+1)$ 以下で、各項は $M\cdot M=M^2$ 以下なので、$c_k\le M^2\min(m+1,n+1)< B$ である。$\square$

多項式に大きな数を代入して整数の掛け算 1 回に直すこの方法は、Kronecker の置き換え（Kronecker substitution）と呼ばれる（Sho08 §17.6、Exercise 17.20。そこでは底を $2$ の累乗にとっている）。

100 進法と 1000 進法で読む

$(3x^2+2x+5)(4x^2+x+7)$ を求める。

$B=1000$：係数は $7$ 以下、項は $3$ 個ずつなので、$7^2\cdot3=147<1000$ で条件を満たす。$f(1000)=3002005$、$g(1000)=4001007$ で、
$$ 3002005\times4001007=12011043019035 $$
である。$3$ 桁ずつ区切ると $12|011|043|019|035$ なので、積は $12x^4+11x^3+43x^2+19x+35$ である。
$B=100$：$f(100)=30205$、$g(100)=40107$ で、$30205\times40107=1211431935$、$2$ 桁ずつ区切ると $12|11|43|19|35$ で同じ係数が読める。$147>100$ なので段 3 の十分条件は満たさないが、prop-mcv-kronecker の前半の条件（積の係数がすべて $100$ 未満）は満たしている。実際の係数が $43$ 以下なので読めている。
展開して確かめると、$x^3$ の係数は $3\cdot1+2\cdot4=11$、$x^2$ の係数は $3\cdot7+2\cdot1+5\cdot4=43$ である。

多倍長計算：大きな位でまとめて掛ける

コンピュータは、決まった大きさまでの整数の掛け算しか一度にできない。それより大きい数は、$10^4$ や $2^{32}$ などを 1 つの位と見て数字（ブロック）に区切り、ブロックどうしの積の畳み込みを計算してから繰り上げる。これは thm-mcv-conv を $10$ の代わりに大きな底 $B$ で使ったものである（Sho08 §3.3）。

1 万進法で掛ける

$123456789\times987654321$ を、$B=10^4$ の位（$4$ 桁ずつ）で計算する。下の位から $123456789=(6789,2345,1)$、$987654321=(4321,8765,9)$ と区切る。畳み込みの各項は

$k=0$：$6789\cdot4321=29335269$
$k=1$：$6789\cdot8765+2345\cdot4321=59505585+10132745=69638330$
$k=2$：$6789\cdot9+2345\cdot8765+1\cdot4321=61101+20553925+4321=20619347$
$k=3$：$2345\cdot9+1\cdot8765=21105+8765=29870$
$k=4$：$1\cdot9=9$
である。$10^4$ で割って繰り上げると、$29335269$ は数字 $5269$・繰り上がり $2933$；$69638330+2933=69641263$ は数字 $1263$・繰り上がり $6964$；$20619347+6964=20626311$ は数字 $6311$・繰り上がり $2062$；$29870+2062=31932$ は数字 $1932$・繰り上がり $3$；$9+3=12$。上の位から並べて
$$ 123456789\times987654321=121932631112635269 $$
である。1 桁ずつなら $9\times9=81$ 回の掛け算が、$3\times3=9$ 回のブロックの掛け算で済んでいる。

Karatsuba の方法：掛け算を 4 回から 3 回へ

2 桁どうしの掛け算 $(a_1X+a_0)(b_1X+b_0)$（$X=10$）の筆算では、$a_1b_1$、$a_1b_0$、$a_0b_1$、$a_0b_0$ の $4$ 回の掛け算をする。ところが、次の等式を使うと $3$ 回で済む。

$47\times36$ を 3 回の掛け算で

$47\times36$ で、$a_1=4$、$a_0=7$、$b_1=3$、$b_0=6$ とする。

$a_1b_1=4\cdot3=12$
$a_0b_0=7\cdot6=42$
$(a_1+a_0)(b_1+b_0)=11\cdot9=99$
真ん中の位の数は $99-12-42=45$ で、これは $a_1b_0+a_0b_1=4\cdot6+7\cdot3=24+21=45$ に等しい。よって $47\times36=12\cdot100+45\cdot10+42=1200+450+42=1692$ である。掛け算は $3$ 回しかしていない。ただし 3 つ目の $11\cdot9$ は 1 桁どうしの積（九九）ではない（rem-mcv-integer）。

Karatsuba の等式

どんな数 $a_0,a_1,b_0,b_1,X$ についても
$$ (a_1X+a_0)(b_1X+b_0)=a_1b_1X^2+\bigl((a_1+a_0)(b_1+b_0)-a_1b_1-a_0b_0\bigr)X+a_0b_0 $$
が成り立つ。右辺で使う掛け算は $a_1b_1$、$a_0b_0$、$(a_1+a_0)(b_1+b_0)$ の $3$ 回である（$X$ 倍・$X^2$ 倍は、位をずらすだけなので数えない）。

両辺を展開する

方針：両辺を分配法則で展開して比べる。
段 1（左辺）。分配法則により
$$ (a_1X+a_0)(b_1X+b_0)=a_1b_1X^2+(a_1b_0+a_0b_1)X+a_0b_0 $$
である。
段 2（右辺の真ん中）。分配法則により
$$ (a_1+a_0)(b_1+b_0)=a_1b_1+a_1b_0+a_0b_1+a_0b_0 $$
なので、
$$ (a_1+a_0)(b_1+b_0)-a_1b_1-a_0b_0=a_1b_0+a_0b_1 $$
である。
段 3。段 2 の式を右辺に入れると、段 1 の式の右辺と同じになる。$\square$

4 桁どうしを 2 桁ずつに分ける

$1234\times5678$ で、$X=100$、$a_1=12$、$a_0=34$、$b_1=56$、$b_0=78$ とする。

$a_1b_1=12\cdot56=672$
$a_0b_0=34\cdot78=2652$
$(a_1+a_0)(b_1+b_0)=46\cdot134=6164$、真ん中は $6164-672-2652=2840$
よって $1234\times5678=672\cdot10^4+2840\cdot10^2+2652=6720000+284000+2652=7006652$ である。

Karatsuba の等式を、分けた半分どうしの掛け算にもくり返し使う。係数の個数が $2^k$ の多項式の場合に、掛け算の回数を数える。

Karatsuba の方法の掛け算の回数

係数の個数がどちらも $2^k$ 個（次数が $2^k-1$ 以下）の 2 つの多項式の積を、Karatsuba の等式を半分ずつにくり返し使って計算すると、係数どうしの掛け算はちょうど $3^k$ 回である。筆算（すべての $a_ib_j$ を計算する）では $4^k$ 回である。ここで足し算・引き算の回数は数えない。

半分に分けて帰納法

方針：$T(k)$ を「係数の個数 $2^k$ どうしの積に必要な掛け算の回数」とし、$T(k)=3\,T(k-1)$ を示す。
段 1（$k=0$）。係数が $1$ 個ずつ（定数どうし）なら、掛け算は $1$ 回で、$T(0)=1=3^0$ である。
段 2（半分に分ける）。$k\ge1$ とし、$h=2^{k-1}$、$X=x^h$ とおく。係数の個数が $2^k=2h$ 個の多項式 $f$ は、下の $h$ 個の係数からなる $f_0$ と上の $h$ 個からなる $f_1$ を使って $f=f_1X+f_0$ と書ける。$g=g_1X+g_0$ も同様である。
段 3（3 回の積）。thm-mcv-karatsuba により、$fg$ は $f_1g_1$、$f_0g_0$、$(f_1+f_0)(g_1+g_0)$ から、足し算・引き算と $X$ 倍だけで求まる。$f_1+f_0$ と $g_1+g_0$ の係数の個数も $h=2^{k-1}$ 個以下なので、3 つの積はどれも係数の個数 $2^{k-1}$ どうしの積で、それぞれ $T(k-1)$ 回の掛け算で求まる。よって $T(k)=3\,T(k-1)$ である。
段 4。段 1 と段 3 から、数学的帰納法（数学的帰納法と整列性）により $T(k)=3^k$ である。筆算の回数は、$2^k$ 個の係数と $2^k$ 個の係数の組の数 $2^k\cdot2^k=4^k$ である。$\square$

掛け算の回数を比べる

$k$	係数の個数 $2^k$	筆算 $4^k$	Karatsuba $3^k$
$1$	$2$	$4$	$3$
$2$	$4$	$16$	$9$
$3$	$8$	$64$	$27$
$4$	$16$	$256$	$81$
$5$	$32$	$1024$	$243$
$10$	$1024$	$1048576$	$59049$

$k=10$ では、筆算の $\frac1{17}$ より少ない回数で済む（$1048576\mathbin{÷}59049=17.7\cdots$）。係数の個数を $n=2^k$ とすると、$4^k=n^2$、$3^k=n^{\log_23}$ で、$\log_23=1.584\cdots$ である（図 2）。

係数 2^k 個の多項式どうしの積での、係数どうしの掛け算の回数。筆算は 4^k 回、Karatsuba の方法は 3^k 回で、k が大きいほど差が開く
図 2 の回数は多項式の場合である。整数に使うと、回数はちょうどこの値になるとは限らない（rem-mcv-integer）。

整数に使うときの注意

整数では、$a_1+a_0$ の桁が $a_1$、$a_0$ より 1 つ増えることがある。ex-mcv-kara でも $b_1+b_0=56+78=134$ は $3$ 桁である。ex-mcv-kara-small の $(4+7)(3+6)=11\cdot9$ のように、3 つ目の積は 1 桁どうしの積（九九）にならないこともある。そのため、整数の場合は 1 桁どうしの掛け算の回数が $3^k$ ちょうどになるとは限らない（和が桁上がりしなければちょうど $3^k$ 回で済み、たとえば $12\times12$ は $1\cdot1$、$2\cdot2$、$3\cdot3$ の $3$ 回、$1111\times1111$ は $11\cdot11$、$11\cdot11$、$22\cdot22$ をそれぞれ $3$ 回で計算して $9$ 回である）。それでも、桁数 $n$ の整数どうしの掛け算を、$n^{\log_23}$（$\log_23=1.584\cdots$）の定数倍以下の手間でできることが知られている（この記事では証明しない。Sho08 Exercise 3.41）。和の代わりに差 $(a_0-a_1)(b_0-b_1)$ を使って桁が増えないようにする方法もある（Sho08 Exercise 3.41）。この方法は Karatsuba によるもので、1963 年の論文で発表された（Sho08 §3.6 と文献表）。

例と反例：どの条件が効いているか

外した条件	崩れる主張	ボックス
畳み込みの項がすべて $9$ 以下	積の数字が畳み込みそのもの（cor-mcv-nocarry）	ex-mcv-eleven-n、ex-mcv-repunit
Kronecker の置き換えで積の係数が $B$ 未満	$B$ 進法の数字が係数	ex-mcv-kron-small
Kronecker の置き換えで係数が $0$ 以上	$B$ 進法の数字が係数	ex-mcv-kron-neg

反例：底が小さすぎると係数が混ざる

ex-mcv-kronecker と同じ積を $B=10$ で計算すると、$f(10)=325$、$g(10)=417$、$325\times417=135525$ である。数字 $1,3,5,5,2,5$ は係数 $12,11,43,19,35$ と違う。係数が $10$ 以上なので繰り上がりが起き、隣の位と混ざったからである。値としては $12\cdot10^4+11\cdot10^3+43\cdot10^2+19\cdot10+35=135525$ で正しいが、係数は読み取れない。

反例：負の係数があると読み取れない

$(x-1)(x+1)=x^2-1$ の係数は $1,0,-1$ である。$B=100$ を入れると $99\times101=9999$ で、$2$ 桁ずつ区切ると $99|99$ となり、係数 $1,0,-1$ は読めない。$100^2-1=9999$ なので値は正しいが、$-1$ という係数を表すために上の位から借りた結果、数字が変わってしまう。

さらに先へ

畳み込みは、並びを無限に延ばしても定義できる。形式的冪級数の積の係数も畳み込みで、母関数の計算の基本になる（形式的冪級数の積と逆数。母関数の全体の案内は母関数：数列を関数として扱う）。関数どうしの積分による畳み込み（畳み込み）は、この和を積分に置きかえたものである。
1 の冪根を使った離散 Fourier 変換は、畳み込みを「成分ごとの積」に変える（1の冪根で数を振り分ける、離散Fourier変換と反転公式）。これを高速に計算する高速 Fourier 変換を使うと、Karatsuba の方法よりさらに速く大きな整数や多項式を掛けられることが知られている（この記事では証明しない。Sho08 §3.6、§17.6）。
数列の差と和も畳み込みで書ける。並び $(1,-1)$ との畳み込みの $k$ 番目の項は差 $a_k-a_{k-1}$、$1$ が並んだ $(1,1,\dots,1)$ との畳み込みの $k$ 番目の項は和 $a_0+a_1+\dots+a_k$ である（$a_{-1}=0$ とする。和のほうは、$1$ の並びの長さが $k+1$ 以上のとき）。差と和の関係は数列の和と差分で扱う。
Kronecker の置き換えは、2 変数の多項式の積を 1 変数の多項式の積に直すのにも使われる（Sho08 §17.6 の Exercise 17.19）。