N進数展開の一般化と分解について
ｺﾝﾊﾞﾝﾊｰ(´∀｀∩
十進法を一般化した記数法を定義してMinecraft計算機に使ったCORDICアルゴリズムの１０進数化の解説に繋げたいと思って書きました。
まず初めに使用する記号の定義をまとめて書いておく。
意味は具体例を通して考察する。
(用語は独自です。先行研究は具体例で述べた部分以外は独力でやったものなのであるかどうか知りません。)
実数全体の集合$\r$,整数全体の集合$\z$,
$\z \ni N \geqq 2,k=1,2,\ldots ,N,\omega \in \Omega$
$[A,B)=\{z|A\leqq z < B,z\in \r\}$(半開区間)
$[基底]\v \beta =(\beta_1,\beta_2,\ldots,\beta_N)\ \ \ (\beta_1>\beta_2>\cdots>\beta_N>0) $
$[表示]\v \lambda =(\lambda_1,\lambda_2,\ldots,\lambda_N)\ \ \ (\lambda_k\in \Lambda\subset \z)$
$[分解]\omega= \v \beta \cdot \v \lambda +\epsilon=\displaystyle \sum_{k=1}^N \beta_k \lambda _k\ +\epsilon \ \ \ (\epsilon \in E )$
$M=\max(\Lambda)-\min(\Lambda)$
$m=\sup(E)-\inf(E)$($E=[A,B)$のとき、$\sup(E)=B,\inf(E)=A$)
$定義域\Omega,変数\omega,基底\v \beta,表示\v \lambda ,表示の集合\Lambda$
$誤差\epsilon ,誤差の範囲E,誤差の幅m,$
$\Omega,E$は半開区間のみを考えることにする。
$(\v \beta,\Lambda) $が与えられた状態で変数$\omega$から分解$(\v\lambda,\epsilon) $を求める操作を「$(\v \beta,\Lambda)による$分解」と呼ぷ。
任意の$\omega \in \Omega $に対して$(\v \lambda ,\epsilon)$が唯一つだけ存在するとき「分解は一意的である」と呼ぷ。
一方で分解が唯一つに定まらないときは「分解は冗長である」と呼ぷ。
任意の$\omega \in \Omega$に対し分解$(\v\lambda,\epsilon) $が存在するとき「分解は完全である」と呼ぷ。
まずはこれがb進法を抽象化し、一般化したものであることを確認する。
$\z\ni b\geqq 2,\ \Omega=[0,b^N),\ \beta_k=b^{N-k},\ \Lambda=[0,b) \cap\z=\{0,1,\ldots,b-1\},\ E=[0,1)$
一応例示すると、10進数の場合
$N=3,b=10,\v\beta=(100,10,1),\omega=137.035=(1,3,7)\cdot\v \beta +0.035,\epsilon=0.035$
で、分解は$(\v \lambda,\epsilon)=((1,3,7),0.035)$である。$\beta$は倍率の数列である。$M$は$\Lambda$の最大元から最小元を引いた数だが、今回の場合は$b-1$である。
また、N桁以下の非負実数全体は$[0,b^N)$であることから自明に分解(b進数展開の整数部)は一意的かつ完全であることがわかる。
$\beta$は単調減少数列であるとしたが、このようにこの記事ではほぼ指数関数的な減少をするものばかりを扱う。
また$\Omega$も連続した区間を考える。
別の例について見る。
$\beta_k=3^{N-k},\ \ \Omega=\left[-\dfrac{3^N}2,\dfrac{3^N}2\right),\ \ \Lambda=\{-1,0,1\},\ \ E=\left[-\dfrac12,\dfrac12\right)$
3進法と似ているが、表示の集合$\Lambda$が違う。例として$N=3,\omega=8$を考えるとこの分解は$8=1×3^2+0×3^1+\bar{1}×3^0$より
$(\v\beta,\epsilon=((1,0,\bar1),0)$となる。ただし、$\bar1=-1$などと表したりする。この分解は完全かつ一意的であることは実験すればわかる。
$\beta_k=2^{N-k},\ \ \Omega=\left[1-2^N,2^N\right),\ \ \Lambda=\{-1,0,1\},\ \ E=\left[0,1\right)$
２進数と似ているが、この場合は冗長性がある。例示すると$\omega=3$の場合、$\v\lambda=(1,0,\bar1),(0,1,1)$という2通りの場合が存在する。すなわち分解は冗長的である。しかし、完全ではある。
今までは$\lambda_k\in\Lambda\subset \z$と考えてきたが、$\lambda_k\in\Lambda_k\subset \z$というように、桁ごとに表示の集合が異なるような例を今だけ考えてみる。
$\beta_k=(N+1-k)!,\ \Lambda_k=\{0,1,\ldots,N+1-k\},\ \Omega=[0,(N+1)!),\ E=[0,1)$
例えば$37=1×4!+2×3!+1×1!$より$\v\lambda=(1,2,0,1)$
ググれば多分情報は出るので詳しくは省略するが、これも面白い数の表現方法である。
(思い付いた時は感動しました。）
分解は完全かつ一意的である。(確か一意性の証明が東大の過去問にあったっけな)
ここまでは全て完全なものを考えてきたが、不完全な例も簡単に作ることができる。
$N=3,\ \v\beta=(1000,100,1),\ \Omega=[0,10^4),\ \Lambda=[0,10)\cap\z, E=[0,1)$
実際、99などの分解は10の位が欠損していることから集合の範囲内で実行できない。また分解は一意的である。
次も不完全な例である。
$N=3,\ \v\beta=(100,10,1),\ \Omega=[0,10^3),\ \Lambda=\{0,1,\ldots,8\}, \ E=[0,1)$
例1,2,3,6を踏まえて一般化すると次のようなことがわかる。
$\beta$は公比$b^{-1}$の等比数列で$\Lambda$は連続したb個の整数の集合とする。$M=b-1$ならば完全かつ一意的に表すことができる。$M> b-1$であれば冗長性が生まれる。また$M< b-1$であれば完全でなくなる。
次も興味深い例である。
Fibonacci数列を$F_1=F_2=1,F_{n+1}=F_n+F_{n-1}$と定めると、黄金比$\phi=\dfrac{1+\sqrt5}2$で
$F_n=\dfrac{\phi^n-(-\phi)^{-n}}{\sqrt5}$と表すことができる。
$\beta_k=F_{N+2-k},\ \Lambda=\{0,1\},\ \Omega=[0,F_{N+2}),\ E=[0,1)$
$F_n$は公比$\phi\approx 1.6$の等比数列と近似できるので、形式的に$b=\phi$として例５の説明に当てはめてみると$M=1>b-1$となることからこの分解は冗長であることが予想できるだろう。これは漸化式を見ると当たり前で、$F_4=\beta_{N-2}=\beta_{N-1}+\beta_{N}$と２通りに分解できている。しかし、表示$\v\lambda$に、以下のような条件を課すと表示は一意的となる：
任意のkに対し$\lambda_k=0 \ or \ \lambda_{k+1}=0$.
ただし$\lambda_{N+1}=0$.
これをZeckendorf表示と呼び、分解は完全でかつ条件付きで一意的であるという著しい性質を持つ。ググると証明がある。
具体例を通して性質を見てきたところで、分解が完全であるかどうかを基底から判別する方法について考察する。
幾つかの仮定をする。
$\beta_N\dfrac M{|\Lambda|-1}\leqq m$
$E=[\inf(E),\sup(E))$
$\displaystyle\Omega\subset\left[\inf(E)+\sum_{k=1}^N\min(\Lambda)\beta_k,\sup(E)+\sum_{k=1}^N\max(\Lambda)\beta_k\right)$
$E,\Omega$は連続した区間
$\Lambda$は等差数列（2元の場合も)からなる集合
$\beta$はほぼ指数関数的減少
任意の$n\in \z(1\leqq n\leqq N-1)$に対して以下の条件が満たされるとき基底は完全である。
$$\dfrac{\beta_nM}{|\Lambda|-1}\leqq M\sum_{k=n+1}^N \beta_k+m$$
例１のb進数で考えると、仮定と命題2の条件は満たされていることがわかる。$M=b-1,m=1$より
$$M\sum_{k=n+1}^N \beta_k+m=(b-1)\sum_{k=n+1}^Nb^{N-k}+1=b^{N-n}=\beta_n$$
となるので命題はこの場合正しいことがわかる。次に補題1の状況で考えると$M\geqq b-1$と
基底の分解が完全であることは同値なので上の命題は十分条件になると捉えられる。
$N$に関する帰納法で証明する。
$N=0$の場合、$E=\Omega$とすれば完全である(うまく定義を拡張すれば)。
次に$\lambda_1=\min(\Lambda)$で固定するとき、$\omega$が動きうる範囲を$\Omega'$として、$\Omega'$が仮定を満たしてかつ命題２の条件を満たしているとする。このとき帰納法の仮定から、$(\v {\beta'} =(\beta_2,\beta_3,\ldots,\beta_N),\Lambda)$による分解は$\Omega'$の範囲で完全であることがわかる。
$\Lambda$は公差$\dfrac M{|\Lambda|-1}$の等差数列であるから非負整数$X$が存在して
$\beta_1\lambda_1=\beta_1\min(\Lambda)+X\beta_1\dfrac M{|\Lambda|-1}$である。
ここで$\Omega'$の長さは
$\displaystyle|\Omega'|=\sup(\Omega')-\inf(\Omega')=M\sum_{k=2}^N \beta_k+m$
で命題2より
$$\dfrac{\beta_1M}{|\Lambda|-1}\leqq M\sum_{k=2}^N \beta_k+m=|\Omega'|$$
となる。集合
$ \widetilde{\Omega} =\left\{\omega'+X\beta_1\dfrac M{|\Lambda|-1}\middle|\omega'\in\Omega',X=0,1,\ldots,|\Lambda|-1\right\}$
は$(\v\beta,\Lambda)$による分解のもとで完全である。$\Omega\subset \widetilde{\Omega} $だから$\Omega$において基底は完全である。
CORDICアルゴリズム導入部分に話をつなげる。
$\arctan(x)$は関数$\tan(x)$の逆関数である。
$\beta_k=\arctan \left(\dfrac 1{2^{k-1}}\right),\ \Omega=\left[0,\dfrac \pi 2\right),\ \Lambda=\{-1,1\},\ E=[0,2\beta_N)$
これが命題2の条件を満たすことを証明しよう。
$M=2,m=2\beta_N,|\Lambda|=2$である。
加法定理より
$\arctan(u)+\arctan(v)=\arctan\left(\dfrac{u+v}{1-uv}\right)\geqq \arctan(u+v)$
であることを何回か使うと
任意の$n\in \z(1\leqq n\leqq N-1)$に対して
$$\begin{align}
&M\sum_{k=n+1}^N \beta_k+m\\
=&2\sum_{k=n+1}^N\arctan \left(\dfrac 1{2^{k-1}}\right)+2\arctan \left(\dfrac 1{2^{N-1}}\right)\\
\geqq &2\arctan \left(\sum_{k=n+1}^N\dfrac 1 {2^{k-1}}+\dfrac 1 {2^{N-1}}\right)\\
=&2\arctan \left(\dfrac 1 {2^{n-1}}\right) \\
=&\dfrac{\beta_nM}{|\Lambda|-1}
\end{align}$$
なので命題の条件は満たされる。
$$\sup(E)+\sum_{k=1}^N\max(\Lambda)\beta_k\\
=\beta_N+\beta_1+\left(\sum_{k=2}^N\beta_k+\beta_N\right)\\
\geqq \beta_N+\beta_1+\beta_1\\
> \dfrac \pi 2$$
なので仮定を満たすことがわかる。これで命題２より基底は完全であることが証明された。$N$を大きくすると$\beta_N→0$、つまり誤差幅$m→0$であるからCORDICアルゴリズムの収束性は保証される。
最後に十進CORDICアルゴリズムの収束性について同様の考察をする。
$\z\ni D\geqq 2,\ N=4D,\ k=4s+t,\ t\in\{1,2,3,4\}$
$(c_1,c_2,c_3,c_4)=(4,2,2,1)$
$\beta_0=\arctan \left(1\right)$
$\beta_k=\arctan \left(\dfrac {c_t}{10^{s+1}}\right)$
$\Omega=\left[0,\dfrac \pi 2\right),\ \Lambda=\{-1,1\},\ E=[0,2\beta_N)$
(便宜上$\beta_0$を追加しなければならない...。)
基底の完全性の証明は二進CORDICと同様に行う。
$n=4S+T,\ (T\in\{1,2,3,4\})$とする。
$$\begin{align}
&M\sum_{k=n+1}^N \beta_k+m\\
=&2\sum_{s=S+1}^{D-1}\sum_{t=1}^4\arctan \left(\dfrac {c_t}{10^{s+1}}\right)+2\arctan \left(\dfrac 1{10^{D}}\right)+2\sum_{t=T+1}^4\arctan \left(\dfrac {c_t}{10^{S+1}}\right)\\
\geqq &2\arctan\left(\sum_{s=S+1}^{D-1}\sum_{t=1}^4\dfrac {c_t} {10^{s+1}}+\dfrac 1 {10^{D}}+\sum_{t=T+1}^4\dfrac {c_t}{10^{S+1}}\right)\\
= &2\arctan\left(\sum_{s=S+1}^{D-1}\dfrac {9} {10^{s+1}}+\dfrac 1 {10^{D}}+\sum_{t=T+1}^4\dfrac {c_t}{10^{S+1}}\right)\\
=&2\arctan \left(\dfrac 1 {10^{S+1}}\left(1+\sum_{t=T+1}^4 {c_t} \right)\right) \\
\geqq &2\arctan\left(\dfrac{c_T}{10^{S+1}}\right)\\
=&\dfrac{\beta_nM}{|\Lambda|-1}
\end{align}$$
ただし、$\displaystyle \sum_{j=v+1}^vA_j=0$と定める。
命題２よりこの基底は完全である。
$$\sum_{s=S+1}^{D-1}\sum_{t=1}^4\dfrac {c_t} {10^{s+1}}+\dfrac 1 {10^{D}}+\sum_{t=T+1}^4\dfrac {c_t}{10^{S+1}}$$
の部分を見ると$c_1+c_2+c_3+c_4=9$が重要であることがわかる。$c_1+c_2+c_3+c_4\leqq 8$のとき、命題2を証明することはできず、基底は不完全となってしまう。完全となるためには$c_1+c_2+c_3+c_4\geqq 9$が必要である。また、$\beta$がほぼ等比数列で減少することを合わせると、$c$は$(c_1,c_2,c_3,c_4)=(4,2,2,1)$が最適であるとわかる。
この話を用いて次の記事ではMinecraftのために少し変更した十進CORDICアルゴリズムを解説したい。