多倍長演算

要点：$c_i\le1$ なら $s_i\le2B-1$ なので $c_{i+1}\le1$ であり、1 桁ずつ繰り上げても値が変わらないことは 整数の筆算の仕組み の命題「足し算の筆算の正しさ」の $10$ を $B$ に替えた主張である。

要点：各 $i$ の段の前に、数字 $c$ の表す数が $\bigl(\sum_{i'< i}a_{i'}B^{i'}\bigr)b$ に等しいことを保つ。

$x< Bb$ なので $q\le B-1$ である。$x=(x_lB+x_{l-1})B^{l-1}+s$（$0\le s< B^{l-1}$）と書く（$l=1$ なら $s=0$）。
段 1（$q\le\hat q$）。$\hat q=B-1$ なら $q\le B-1=\hat q$ である。そうでなければ $\hat q=\tilde q$ である。$x_lB+x_{l-1}-\tilde qb_{l-1}$ は $x_lB+x_{l-1}$ を $b_{l-1}$ で割った余りなので $b_{l-1}-1$ 以下である。$b\ge b_{l-1}B^{l-1}$ を使うと
$$ x-\tilde q\,b\le x-\tilde q\,b_{l-1}B^{l-1}=(x_lB+x_{l-1}-\tilde qb_{l-1})B^{l-1}+s\le(b_{l-1}-1)B^{l-1}+B^{l-1}-1< b_{l-1}B^{l-1}\le b $$
となる。よって $x<(\tilde q+1)b$ であり、$q=\lfloor x/b\rfloor\le\tilde q=\hat q$ である。
段 2（$\hat q\le q+2$ の準備）。$b$ の下の $l-1$ 桁がすべて $0$、すなわち $b=b_{l-1}B^{l-1}$ なら、整数の筆算の仕組み の補題「商の数字は上の桁だけで決まる」（$10$ を $B$ に替えたもの）により $q=\lfloor x/(B^{l-1}b_{l-1})\rfloor=\lfloor(x_lB+x_{l-1})/b_{l-1}\rfloor=\tilde q$ なので、$\hat q\le\tilde q=q$ である。以下 $b> b_{l-1}B^{l-1}$ とする。このとき $b> B^{l-1}$ であり、$b<(b_{l-1}+1)B^{l-1}$ から $b_{l-1}B^{l-1}> b-B^{l-1}>0$ である。よって
$$ \tilde q\le\frac{x_lB+x_{l-1}}{b_{l-1}}=\frac{(x_lB+x_{l-1})B^{l-1}}{b_{l-1}B^{l-1}}\le\frac{x}{b_{l-1}B^{l-1}}<\frac{x}{b-B^{l-1}} $$
である。
段 3（$\hat q\le q+2$）。$\hat q\ge q+3$ と仮定して矛盾を導く。$q> x/b-1$ と段 2 から
$$ 3\le\hat q-q\le\tilde q-q<\frac{x}{b-B^{l-1}}-\frac{x}{b}+1=\frac{x\,B^{l-1}}{b\,(b-B^{l-1})}+1 $$
なので、$\dfrac{x}{b}>\dfrac{2(b-B^{l-1})}{B^{l-1}}\ge2(b_{l-1}-1)$ である（最後は $b\ge b_{l-1}B^{l-1}$ による）。すると $q> x/b-1> 2b_{l-1}-3$ であり、$q$ は整数なので $q\ge2b_{l-1}-2$ である。一方 $q\le\hat q-3\le B-4$ なので $2b_{l-1}-2\le B-4$、すなわち $b_{l-1}\le B/2-1<\lfloor B/2\rfloor$ となり、$b$ が正規化されていることに反する。$\square$

要点：$d(v+1)\le B$ から桁数が増えず、$v<\lfloor B/2\rfloor$ のときは $dv\ge(B-1)/2$ を示す。

lem-mp-normalize の $d$ で $a'=da$、$b'=db$ とする。$1$ 桁の数を掛けるだけなので $O(k)$ 回で済み、商は変わらない。$m:=k-l+1$ とおくと、$a'< dB^k$ と $b'\ge dB^{l-1}$ から $a'< B^mb'$ である。
$r^{(m)}:=a'$ とし、$i=m-1,\dots,0$ の順に次を行う。$r^{(i+1)}< B^{i+1}b'$ が保たれるので、$x:=\lfloor r^{(i+1)}/B^i\rfloor$（$r^{(i+1)}$ の位 $i$ から上の数字の並び）は $x< Bb'$ を満たし、$l+1$ 桁で表せる。thm-mp-trial-quotient の $\hat q$ を 1 回の 1 桁演算で求め、$y:=x-\hat qb'$ を prop-mp-schoolbook・prop-mp-add で $O(l)$ 回で計算する。$y<0$ の間は $y$ に $b'$ を足して $\hat q$ を $1$ 減らす。定理によりこれは $2$ 回以下で終わり、終わったとき $\hat q=\lfloor x/b'\rfloor$、$0\le y< b'$ である。この $\hat q$ を商の数字 $q_i$ とし、$r^{(i+1)}$ の位 $i$ から上を $y$ に置き換えたものを $r^{(i)}$ とする。整数の筆算の仕組み の補題「商の数字は上の桁だけで決まる」により $q_i=\lfloor r^{(i+1)}/(B^ib')\rfloor$、$r^{(i)}=r^{(i+1)}-B^ib'q_i$ であり、これは同じ記事の定理「割り算の筆算の正しさ」の手順そのものなので、$q=\sum_iq_iB^i$ が商、$r^{(0)}$ が $a'$ を $b'$ で割った余りである。余り $a-bq=r^{(0)}/d$ は 1 桁の数での割り算なので $O(l)$ 回で求まる。
各段の手間は $O(l)$ で段は $m$ 個あり、ほかの手間は $O(k)$ である。$(l-1)(m-1)\ge0$ から $k=l+m-1\le lm$ なので、全体は $O(lm)=O\bigl(l(k-l+1)\bigr)$ である。$\square$

段 1（手順）。$n=2^k$ のとき、$0\le a,b< B^n$ の積を求める手順 $K_k$ を帰納的に定める。$K_0$ は 1 桁の掛け算 1 回と、積を 2 桁の数字に分ける割り算 1 回である。$k\ge1$ なら $m:=2^{k-1}$ とし、$a=a_1B^m+a_0$、$b=b_1B^m+b_0$（$0\le a_0,a_1,b_0,b_1< B^m$）と分ける（数字の並びを上下に分けるだけである）。

1. $p_0:=a_0b_0$、$p_2:=a_1b_1$ を $K_{k-1}$ で求める。
2. $\lvert a_0-a_1\rvert$、$\lvert b_0-b_1\rvert$ とその符号を prop-mp-add で求め、$p_1:=(a_0-a_1)(b_0-b_1)$ を、絶対値の積を $K_{k-1}$ で求めて符号を付けて得る。
3. $ab=p_2B^{2m}+(p_0+p_2-p_1)B^m+p_0$ を足し算・引き算で組み立てる。
   正しさは上の等式と $ab=a_1b_1B^{2m}+(a_0b_1+a_1b_0)B^m+a_0b_0$ による。
   段 2（漸化式）。2 と 3 の足し算・引き算・比較は、どれも $4m+1$ 桁以下の数についてのもので、回数も一定である。よって $k,B$ によらない定数 $c\ge1$ があって、手順 $K_k$ の手間 $T(k)$ は
   $$ T(0)=2,\qquad T(k)\le3\,T(k-1)+c\,2^k\quad(k\ge1) $$
   を満たす。
   段 3（漸化式を解く）。$T(k)\le(2+2c)3^k-2c\,2^k$ を $k$ についての帰納法で示す。$k=0$ では右辺は $2$ である。$k-1$ で成り立てば
   $$ T(k)\le3\bigl((2+2c)3^{k-1}-2c\,2^{k-1}\bigr)+c\,2^k=(2+2c)3^k-2c\,2^k $$
   である。とくに $T(k)\le(2+2c)3^k$ である。
   段 4（一般の $n$）。$n\ge1$ 桁以下の数は、上に $0$ を補って $2^k$ 桁の数と見なせる。ここで $k:=\lceil\log_2n\rceil$ とすると $2^k< 2n$ なので
   $$ 3^k=(2^k)^{\log_23}<(2n)^{\log_23}=3\,n^{\log_23} $$
   であり、手間は $3(2+2c)\,n^{\log_23}$ 以下である（$0$ を補う手間は数えなくてよい）。$C:=3(2+2c)$ とすればよい。$\square$

要点：$0\le c_k\le n(B-1)^2< p$ なので、$c_k$ は $p$ で割った余りから決まる。