平衡三進法

>> Home >> 記数法 >> 平衡三進法

A. 通常のシンボル  |  【B. 符号付きのシンボル】  |  C. 零を含まないシンボル
B1.  平衡三進法
B2.  天秤の問題

通常の三進法

通常の三進法では,任意の数が非負のシンボル 0,1,2 からなる列によって表現される。 十進法で N=38 と表される数を三進法に変換しよう。 \[ \begin{array}{cccl} 38 &&& (38=3 \times 12+2) \\ 12 & \cdots & 2 & (12=3 \times 4+0) \\ 4 & \cdots & 0 & (4=3 \times 1+1) \\ 1 & \cdots & 1 & (1=3 \times 0+1) \\ 0 & \cdots & 1 \end{array} \] N=38 を3で割って商と剰余を書きとめておき,前の除算で得られた商をさらに3で割って商と剰余を書きとめる。 この作業を商が0になるまで続けて,書きとめておいた剰余を逆順に並べるとNの三進法表記が得られる。 \[ N=38_{(10)}=1102_{(3)} \] 上で求めた商の部分を繰り返し代入していくと \begin{align} 38 &= ((1 \times 3+1) \times 3+0) \times 3+2 \\ 38 &= 1 \times 3^3+1 \times 3^2+0 \times 3+2 \end{align} となるから,三進法の 1102 という文字列で表される数は,確かに十進法の38に等しい。

最小非負剰余

ここで用いた除法はいつもの使いなれた除法で,3で割った剰余が 0,1,2 のいずれかになる。 整数aを正の整数bで割ったときの商を q = ⌊a/b⌋ で求めると,剰余の範囲が 0 ≤ r < b になる。 このような剰余を最小非負剰余という。 \begin{align} & q=\left\lfloor \frac{a}{b} \right\rfloor & & 0 \le r < b \end{align}

平衡三進法

平衡三進法とは,任意の数を3つの値 −1,0,1 をもつシンボルの列によって表現する方法のことである。 ここでは −1,0,1 のかわりに A,0,1 を平衡三進法のシンボルとして用いることにする。 すると 111A という列で表される数は十進法で 38 である。 \[ 1 \times 3^3+1 \times 3^2+1 \times 3+(-1) = 38 \] シンボルの値 −1,0,1 を得るためには絶対値最小剰余を利用すればよい。

絶対値最小剰余

絶対値最小剰余とは,剰余の絶対値が除数の絶対値の半分以下になるように定めた剰余のことである。 除数がbのとき絶対値最小剰余の範囲は −b/2 ≤ r < b/2 または −b/2 < r ≤ b/2 になる。 ここでは前者を用いよう(被除数が整数だけならどちらの範囲でも違いはない)。 \[ -\frac{b}{2} \le r < \frac{b}{2} \] 商qが r = a−bq を満たすことから, \begin{align} -\frac{b}{2} \le a-bq < \frac{b}{2} \\ \frac{a}{b}-\frac{1}{2} < q \le \frac{a}{b}+\frac{1}{2} \end{align} 絶対値最小剰余を得るための商qは \[ q=\left\lfloor \frac{a}{b}+\frac{1}{2} \right\rfloor \] で求めればよい。 3で割るときはこの形 ⌊a/3+1/2⌋ のまま用いるか, 整数だけしか扱わないなら ⌊(a+1)/3⌋ でもよい。 \begin{align} q &= \left\lfloor \frac{a}{3}+\frac{1}{2} \right\rfloor & q &= \left\lfloor \frac{a+1}{3} \right\rfloor \end{align} ここでは整数しか扱わないから後者が簡単である。 \begin{align} & q=\left\lfloor \frac{a+1}{3} \right\rfloor & & -1 \le r \le 1 \end{align}

十進法から平衡三進法に変換する

十進法で N=38 と表される数を平衡三進法で表そう。 剰余が −1,0,1 となるように商を ⌊(a+1)/3⌋ で求めればよい。 38+1=39 を3で割り,通常の方法で商と剰余を求める。 その結果から1を引けば,38を3で割ったときの絶対値最小剰余になる。 \begin{align} & 38+1=3 \times 13+0 & & 38=3 \times 13-1 \end{align} その商 13 を3で割って絶対値最小剰余を求める。 \begin{align} & 13+1=3 \times 4+2 & & 13=3 \times 4+1 \end{align} もう一度その商 4 を3で割って絶対値最小剰余を求める。 \begin{align} & 4+1=3 \times 1+2 & & 4=3 \times 1+1 \end{align} 次のような表を書くと見やすくなる。 \[ \begin{array}{cccl} 38 &&& (38=3 \times 13-1) \\ 13 & \cdots & -1 & (13=3 \times 4+1) \\ 4 & \cdots & 1 & (4=3 \times 1+1) \\ 1 & \cdots & 1 & (1=3 \times 0+1) \\ 0 & \cdots & 1 \end{array} \] 剰余を逆順に並べるとNの平衡三進法表記が得られる。 この際,−1はシンボルAに置き換えておく。 \[ N=38_{(10)}=111\text{A}_{[3]} \] この 111A[3] は通常の三進法ではなく,平衡三進法を表している。 なお,上で求めた商の部分を繰り返し代入していくと \begin{align} 38 &= ((1 \times 3+1) \times 3+1) \times 3-1 \\ 38 &= 1 \times 3^3+1 \times 3^2+1 \times 3+(-1) \end{align} となるから,平衡三進法の 111A という文字列で表される数は,確かに十進法の38に等しい。

2015.11.26 作成 / 2015.11.26 更新

1 2 Next Home

>> Home >> 記数法 >> 平衡三進法