広義の記数法
この項では基本的な位取り記数法を除く、負の数や虚数を含む記数法等について述べる。 ここでは仮数とは、その位に記された数のこととし、 底（てい）とは、その位の一つ上の位の値が持つ、その位に対する重みの倍率とする。
Contents
標準的な記数法
この節では、底が一定で冗長でない記数法について説明する。
書き方は位取り記数法と同じく、底が K であれば、数
- [math]\cdots+c_2K^2+c_1K^1+c_0K^0+c_{-1}K^{-1}+c_{-2}K^{-2}+\cdots[/math]
を
- [math]\cdots c_2c_1c_0c_{-1}c_{-2}\cdots[/math]
のように仮数を書き並べることで表記できる。この記法では、n を自然数とすると
- [math]10^n=1\overbrace{0 \cdots 0}^{n}[/math]
が成り立つ。一般的に位取り記数法と呼ばれるものは、0 から N − 1 までの N 個の整数を仮数にもつ底が N の表記法のことである。これは任意の 0 以上の実数を無限に近似できるが、その他の数を表記するには演算子が必要となる。
中には底が自然数でないものも考えられている。コンピュータでは二進法を用いている場合がほとんどだが、符号の扱いが難しい。そこで、底を −2 とした記法が考えられた。この方法では、0 と 1 を用いてすべての整数を表すことが出来る。その他に複素数を表記するため、−1 + i を底としたものも考えられている（i は虚数単位）。これらはドナルド・クヌースにより考案されたが、演算が複雑なため実際に用いられることは稀である。
実数を表記するもの
仮数が n 通りであれば、底は ±n となる。
任意の実数を表記できるものとして、次の例が考えられる。
| 名前 | 仮数 | 底 | 一桁の演算で繰り上がる確率 | 除算 | ||
|---|---|---|---|---|---|---|
| 加算 | 乗算 | |||||
| なし (negabinary) [A] | 0, 1 | −2 | 1/4 | 0/4 | 可 | |
| なし[B] | −2, −1, 0, 1 | 4 | 4/16 | 3/16 | 可 | |
| 平衡三進法 (balanced ternary) [C] | −1, 0, 1 | 3 | 2/9 | 0/9 | 可 | |
| なし (negaternary) [D] | 0, 1, 2 | −3 | 3/9 | 1/9 | 可 | |
| なし [E] | −3, −1, 0, 1, 3 | 5 | 12/25 | 4/25 | 不可 | |
複素数を表記するもの
i は虚数単位とする。仮数が n 通りであれば、底の絶対値は[math]\sqrt{n}[/math]となる。
任意の複素数を表記できるものとして、次の例が考えられる。
| 名前 | 仮数 | 底 | 一桁の演算で繰り上がる確率 | 除算 | ||
|---|---|---|---|---|---|---|
| 加算 | 乗算 | |||||
| なし | 0, 1 | −1+i | 1/4 | 0/4 | 不可 | |
| なし | 0, 1 | [math]\sqrt{2}\,i[/math] | 1/4 | 0/4 | 可 | |
| なし[A'] | 0, 1, [math]\textstyle -\frac{1}{2}+\frac{\sqrt{3}}{2}i[/math], [math]\textstyle -\frac{1}{2}-\frac{\sqrt{3}}{2}i[/math] | −2 | 9/16 | 0/16 | 不可 | |
| なし[C'] | −1+i, i, 1+i, −1, 0, 1, −1−i, −'i, 1−i | 3 | 32/81 | 16/81 | 可 | |
| なし(quater-imaginary base) | 0, 1, 2, 3 | 2i | 6/16 | 4/16 | 可 | |
| なし | i, −1, 0, 1, −i | 2+i | 12/25 | 0/25 | 不可 | |
なお、[A]と[A']、[C]と[C']は、実数の表記が一致する。
特異な記数法
ここでは、小数点から上に数えて n番目の位を n-1番位と呼ぶことにする。 例えば二進法では、n番位の重みは 2n である。
次に例を挙げる。
- 冗長二進法 (redundant binary representation, RB) とは、符号付二進法 (signed-digit, SD) の一種で、 -1, 0, 1 を仮数に持ち、底を 2 とした記数法である。任意の実数はこの表現を無限に持つ。
- 非隣接形式 (non-adjacent form, NAF) [F] とは、冗長二進法において隣接する二つの位の少なくとも一方の仮数を 0 としたものであり、符号付二進法の一種である。この記法による表現は任意の整数に対して一つだけ存在する。この表記方法は通常の二進法と比較して、仮数が 0 の位が多く乗法や指数演算の処理速度が速い。応用例としては、楕円曲線上のスカラー倍算を効率的に計算する方法が知られている。
- 相互交代形式 (mutual opposite form, MOF) [G] とは、冗長二進法において、0 を除くと 1 と -1 が交互に並び最上位が 1 で最下位が -1 としたものであり、符号付二進法の一種である。この記法による表現は任意の自然数に対して一つだけ存在する。 2004 年 8 月 23 日に、日立製作所により発表された。MOF page
- 桁数が制限された二進法の、最上位の一つ下の位の底を -2 とした表記法 [H] による表記は2の補数表記と一致する。
- 二五進法 [I] とは、偶数番位は仮数が 0, 1, 2, 3, 4 で底が 5 、奇数番位は仮数が 0, 1 で底が 2 である記数法である。これは十進法の一つの位を二つに分割した形となっており、そろばんではこれが使用されている。
- 階乗進法 (factoradic) [J] とは、0番位は仮数が 0 で底が 1 、 1番位は仮数が 0, 1 で底が 2 、 2番位は仮数が 0, 1, 2 で底が 3 、 3番位は仮数が 0, 1, 2, 3 で底が 4 、…とした記数法である。また、この記法の拡張として、 -1番位は仮数が 0, 1 で底が 2 、 -2番位は仮数が 0, 1, 2 で底が 3 、…とした記数法があり、これには任意の有理数を有限小数で表記できるという特徴がある。なお n番位の重みは、 n≧0 ならば n の階乗、 n＜0 ならば -n+1 の階乗の逆数となる。
- 0, 1 を仮数に持ち、底を黄金比 φ とし、隣り合う二つの位の少なくとも一方の仮数を 0 とした記数法 (golden ratio base, 黄金進法) [K] がある。この記法では各位で、11 = 100 および 1 + 1 = 10.01 が成り立つ。また十進法で表記された数[math]\sqrt{5}[/math]は、この記法では 10.1 と表記できることにも注意したい。
対応表
ここでは -n を[math]\bar{n}[/math]と表記する。 他には、WWW との適合性のため -n を n と書いたり、 [math]\bar{1}[/math]を単に T と書く手法もある。
| 十進法 | [A] | [B] | [C] | [D] | [E] | [F] | [G] | [H] | [I] | [J] | [K] |
|---|---|---|---|---|---|---|---|---|---|---|---|
| -16 | 110000 | [math]\bar{1}[/math]00 | [math]\bar{1}[/math]11[math]\bar{1}[/math] | 1102 | [math]\bar{3}[/math][math]\bar{1}[/math] | [math]\bar{1}[/math]0000 | 10000 | ||||
| -15 | 110001 | [math]\bar{1}[/math]01 | [math]\bar{1}[/math]110 | 1220 | [math]\bar{3}[/math]0 | [math]\bar{1}[/math]0001 | 10001 | ||||
| -14 | 110110 | [math]\bar{1}[/math]1[math]\bar{2}[/math] | [math]\bar{1}[/math]111 | 1221 | [math]\bar{3}[/math]1 | [math]\bar{1}[/math]0010 | 10010 | ||||
| -13 | 110111 | [math]\bar{1}[/math]1[math]\bar{1}[/math] | [math]\bar{1}[/math][math]\bar{1}[/math][math]\bar{1}[/math] | 1222 | [math]\bar{1}[/math]3[math]\bar{3}[/math] | [math]\bar{1}[/math]010[math]\bar{1}[/math] | 10011 | ||||
| -12 | 110100 | [math]\bar{1}[/math]10 | [math]\bar{1}[/math][math]\bar{1}[/math]0 | 1210 | [math]\bar{3}[/math]3 | [math]\bar{1}[/math]0100 | 10100 | ||||
| -11 | 110101 | [math]\bar{1}[/math]11 | [math]\bar{1}[/math][math]\bar{1}[/math]1 | 1211 | [math]\bar{1}[/math]3[math]\bar{1}[/math] | [math]\bar{1}[/math]0101 | 10101 | ||||
| -10 | 1010 | [math]\bar{2}[/math][math]\bar{2}[/math] | [math]\bar{1}[/math]0[math]\bar{1}[/math] | 1212 | [math]\bar{1}[/math]30 | [math]\bar{1}[/math]0[math]\bar{1}[/math]0 | 10110 | ||||
| -9 | 1011 | [math]\bar{2}[/math][math]\bar{1}[/math] | [math]\bar{1}[/math]00 | 1200 | [math]\bar{1}[/math]31 | [math]\bar{1}[/math]00[math]\bar{1}[/math] | 10111 | ||||
| -8 | 1000 | [math]\bar{2}[/math]0 | [math]\bar{1}[/math]01 | 1201 | [math]\bar{1}[/math][math]\bar{3}[/math] | [math]\bar{1}[/math]000 | 11000 | ||||
| -7 | 1001 | [math]\bar{2}[/math]1 | [math]\bar{1}[/math]1[math]\bar{1}[/math] | 1202 | [math]\bar{1}[/math]33 | [math]\bar{1}[/math]001 | 11001 | ||||
| -6 | 1110 | [math]\bar{1}[/math][math]\bar{2}[/math] | [math]\bar{1}[/math]10 | 20 | [math]\bar{1}[/math][math]\bar{1}[/math] | [math]\bar{1}[/math]010 | 11010 | ||||
| -5 | 1111 | [math]\bar{1}[/math][math]\bar{1}[/math] | [math]\bar{1}[/math]11 | 21 | [math]\bar{1}[/math]0 | [math]\bar{1}[/math]0[math]\bar{1}[/math] | 11011 | ||||
| -4 | 1100 | [math]\bar{1}[/math]0 | [math]\bar{1}[/math][math]\bar{1}[/math] | 22 | [math]\bar{1}[/math]1 | [math]\bar{1}[/math]00 | 11100 | ||||
| -3 | 1101 | [math]\bar{1}[/math]1 | [math]\bar{1}[/math]0 | 10 | [math]\bar{3}[/math] | [math]\bar{1}[/math]01 | 11101 | ||||
| -2 | 10 | [math]\bar{2}[/math] | [math]\bar{1}[/math]1 | 11 | [math]\bar{1}[/math]3 | [math]\bar{1}[/math]0 | 11110 | ||||
| -1 | 11 | [math]\bar{1}[/math] | [math]\bar{1}[/math] | 12 | [math]\bar{1}[/math] | [math]\bar{1}[/math] | 11111 | ||||
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 00000 | 0 | 0 | 0 | |
| 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1[math]\bar{1}[/math] | 00001 | 1 | 10 | 1 |
| 2 | 110 | 1[math]\bar{2}[/math] | 1[math]\bar{1}[/math] | 2 | 1[math]\bar{3}[/math] | 10 | 1[math]\bar{1}[/math]0 | 00010 | 2 | 100 | 10.01 |
| 3 | 111 | 1[math]\bar{1}[/math] | 10 | 120 | 3 | 10[math]\bar{1}[/math] | 10[math]\bar{1}[/math] | 00011 | 3 | 110 | 100.01 |
| 4 | 100 | 10 | 11 | 121 | 1[math]\bar{1}[/math] | 100 | 1[math]\bar{1}[/math]00 | 00100 | 4 | 200 | 101.01 |
| 5 | 101 | 11 | 1[math]\bar{1}[/math][math]\bar{1}[/math] | 122 | 10 | 101 | 1[math]\bar{1}[/math]1[math]\bar{1}[/math] | 00101 | 10 | 210 | 1000.1001 |
| 6 | 11010 | 1[math]\bar{2}[/math][math]\bar{2}[/math] | 1[math]\bar{1}[/math]0 | 110 | 11 | 10[math]\bar{1}[/math]0 | 10[math]\bar{1}[/math]0 | 00110 | 11 | 1000 | 1010.0001 |
| 7 | 11011 | 1[math]\bar{2}[/math][math]\bar{1}[/math] | 1[math]\bar{1}[/math]1 | 111 | 1[math]\bar{3}[/math][math]\bar{3}[/math] | 100[math]\bar{1}[/math] | 100[math]\bar{1}[/math] | 00111 | 12 | 1010 | 10000.0001 |
| 8 | 11000 | 1[math]\bar{2}[/math]0 | 10[math]\bar{1}[/math] | 112 | 13 | 1000 | 1[math]\bar{1}[/math]000 | 01000 | 13 | 1100 | 10001.0001 |
| 9 | 11001 | 1[math]\bar{2}[/math]1 | 100 | 100 | 1[math]\bar{3}[/math][math]\bar{1}[/math] | 1001 | 1[math]\bar{1}[/math]01[math]\bar{1}[/math] | 01001 | 14 | 1110 | 10010.0101 |
| 10 | 11110 | 1[math]\bar{1}[/math][math]\bar{2}[/math] | 101 | 101 | 1[math]\bar{3}[/math]0 | 1010 | 1[math]\bar{1}[/math]1[math]\bar{1}[/math]0 | 01010 | 100 | 1200 | 10100.0101 |
| 11 | 11111 | 1[math]\bar{1}[/math][math]\bar{1}[/math] | 11[math]\bar{1}[/math] | 102 | 1[math]\bar{3}[/math]1 | 10[math]\bar{1}[/math]0[math]\bar{1}[/math] | 1[math]\bar{1}[/math]10[math]\bar{1}[/math] | 01011 | 101 | 1210 | 10101.0101 |
| 12 | 11100 | 1[math]\bar{1}[/math]0 | 110 | 220 | 3[math]\bar{3}[/math] | 10[math]\bar{1}[/math]00 | 10[math]\bar{1}[/math]00 | 01100 | 102 | 2000 | 100000.101001 |
| 13 | 11101 | 1[math]\bar{1}[/math]1 | 111 | 221 | 1[math]\bar{3}[/math]3 | 10[math]\bar{1}[/math]01 | 10[math]\bar{1}[/math]1[math]\bar{1}[/math] | 01101 | 103 | 2010 | 100010.001001 |
| 14 | 10010 | 10[math]\bar{2}[/math] | 1[math]\bar{1}[/math][math]\bar{1}[/math][math]\bar{1}[/math] | 222 | 3[math]\bar{1}[/math] | 100[math]\bar{1}[/math]0 | 100[math]\bar{1}[/math]0 | 01110 | 104 | 2100 | 100100.001001 |
| 15 | 10011 | 10[math]\bar{1}[/math] | 1[math]\bar{1}[/math][math]\bar{1}[/math]0 | 210 | 30 | 1000[math]\bar{1}[/math] | 1000[math]\bar{1}[/math] | 01111 | 110 | 2110 | 100101.001001 |
演算
標準的な記数法の上での、加法、減法、乗法、除法の算法について説明する。
加法、減法、乗法
加法と乗法については、あらかじめ各仮数同士の計算結果を表にしておき、それを見ながら計算すればよい。 加算時の繰り上がりは上の位にさらに足すことや、二桁以上の乗算については、 [math]10^n=1\overbrace{0\cdots 0}^{n}[/math]が成り立つことに注意して計算を実行していく。 減法については表を作ってもよいが、 引く数に -1 を掛けてから引かれる数に足すという方法も考えられる。
例として、底が 4 で仮数に -2, -1, 0, 1 を持つ記数法の、加算と減算と乗算の表を次に示す。
|
|
|
除法
底を K とした K進法の上で R を D で割る手順を説明する。 記数法によって決まる、一桁の商を示す二変数関数 QK が分かっているとし、 十分に大きな整数 n をとり、次の計算を行う。
rn=R cn=QK(rn , DKn ) rn-1= rn-cnDKn cn-1=QK(rn-1, DKn-1) rn-2=rn-1-cn-1DKn-1 cn-2=QK(rn-2, DKn-2) rn-3=rn-2-cn-2DKn-2 ...... c0=QK(r0 , D ) r-1= r0-c0D
商は K進法で cncn-1…c0 となり、 余りは r-1 となる。 ただし記数法によっては、 0.XXX... の形で表記できる範囲がフラクタルを描くため QK が作れなくなり、除算が不可能となる。 またこの操作をさらに続けると、循環小数が商として得られる。
Q(r, d) の例を次に示す。
- 十進法
d≦0 または r＜0 または 10d≦r は禁止で、
0≦r＜d ならば Q(r, d)=0
d≦r＜2d ならば Q(r, d)=1
2d≦r＜3d ならば Q(r, d)=2
......
8d≦r＜9d ならば Q(r, d)=8
9d≦r＜10d ならば Q(r, d)=9 となる。
- 底が -2 で仮数に 0, 1 を持つ記数法
d=0 または (r＜-2d/3 かつ r＜4d/3) または (-2d/3＜r かつ 4d/3＜r) は禁止で、
d/3＜r≦4d/3 または 4d/3≦r＜d/3 ならば Q(r, d)=1
-2d/3≦r≦d/3 または d/3≦r≦-2d/3 ならば Q(r, d)=0 となる。
- 平衡三進法
d=0 または (r＜-3d/2 かつ r＜3d/2) または (-3d/2＜r かつ 3d/2＜r) は禁止で、
d/2＜r≦3d/2 または 3d/2≦r＜d/2 ならば Q(r, d)=1
-d/2≦r≦d/2 または d/2≦r≦-d/2 ならば Q(r, d)=0
-3d/2≦r＜-d/2 または -d/2＜r≦-3d/2 ならば Q(r, d)=-1 となる。
記法の変換方法
標準的な記数法に対しての、数の表記法を変換する方法を説明する。
十進法からの変換（整数部分）
余りが仮数に含まれるように底で割っていく方法がある。この方法では下位の仮数から求まる。
例えば十進法で表記された数3620を平衡三進法に変換すると、
3620 ÷ 3 = 1207 . . . -1 1207 ÷ 3 = 402 . . . 1 402 ÷ 3 = 134 . . . 0 134 ÷ 3 = 45 . . . -1 45 ÷ 3 = 15 . . . 0 15 ÷ 3 = 5 . . . 0 5 ÷ 3 = 2 . . . -1 2 ÷ 3 = 1 . . . -1 1 ÷ 3 = 0 . . . 1
から平衡三進法では 1[math]\bar{1}[/math][math]\bar{1}[/math]00[math]\bar{1}[/math]01[math]\bar{1}[/math] と表記できる。
また、基本的には複素数を表記する記数法ではこの変換は難しいが、 底が -1+i で仮数に 0, 1 を持つ記数法では、比較的簡単に計算できる。 ある複素数 x+yi に対して (x, y は整数) 、
- (x + yi) ÷ (-1 + i) = p + qi . . . c
となる整数 p, q と仮数 c を求める。この式を変形すると、
- [math]\frac{-x+y+c}{2}=p\qquad\frac{-x-y+c}{2}=q[/math]
の 2 式が得られる。 x+y が奇数なら -x+y, -x-y も奇数なので p, q が整数であることに注意すると、 x+y が奇数のとき c=1 、偶数のとき c=0 がわかる。
十進法からの変換（小数部分）
上にある除法の節の QK を利用し、次の計算を行う。 変換前の十進数を R とする。
r0=R c0=QK(r0, 1) r1=K×(r0-c0) c1=QK(r1, 1) r2=K×(r1-c1) c2=QK(r2, 1) r3=K×(r2-c2) ......
これにより、 R は K進法で c0.c1c2c3... と表記できる。
十進法への変換（整数部分）
上位より仮数を足してから底を掛けていく方法がある。
例えば 0, 1 を仮数に持ち、底を -2 とした記数法で表記された数 1101101 を十進法に変換すると、
0+1= 1 1×(-2)= -2 -2+1= -1 -1×(-2)= 2 2+0= 2 2×(-2)= -4 -4+1= -3 -3×(-2)= 6 6+1= 7 7×(-2)=-14 -14+0=-14 -14×(-2)= 28 28+1= 29
から十進法では 29 と表記できる。
十進法への変換（有限小数部分）
上位より仮数を足してから底を掛けていき、最下位の仮数を足したら、 それに最下位の重みを掛けるという方法がある。
十進法への変換（循環小数部分）
次の式を利用して変換できる。 [math]\frac{1}{e}+\frac{1}{e^2}+\frac{1}{e^3}+\cdots =\frac{1}{e-1}[/math] (|e|＞1)
位の統合と分割
二つの記数法があるとし、それぞれの底が n, nk となっており、 底が n の方で k桁で表される全ての数が、底が nk の方では 1桁で表される時、 その対応により、各位を変換するだけで任意の数を変換することができる。 例えば、0, 1 を仮数に持つ底が -2 の記数法 [A] と、 -2, -1, 0, 1 を仮数に持つ底が 4 の記数法 [B] は、 10 と[math]\bar{2}[/math] 、11と[math]\bar{1}[/math] 、00 と 0 、01 と 1 が対応しているので、 例えば [A] で表記された 100011011 の二つの位を一つに統合すると、 101[math]\bar{2}[/math][math]\bar{1}[/math] となり [B] での表記が得られる。
詳しい定義
各用語の詳しい定義を紹介する。
0 を含む連続した整数の集合 z をとり、その元を位(あるいは桁)と呼ぶ。 特定の位をさしたいときには、0番位や 1番位と単位をつけることにする。 そして、任意の n∈z に対して空でない実数の有限集合 mn をとり、 その元を n番位の仮数と呼ぶ。そして、任意の n∈z に対して実数 Kn を定め、 この Kn を n番位の重み(あるいは意味)と呼び、 Kn+1/Kn を n番位の底(あるいは基数)と呼ぶ。 これらをもとに数を表す方法を記数法(あるいは位取り記数法)という ( mn の元や Kn は複素数でもよい)。 この z, mn, Kn による記数法をK進法(あるいは K進記数法)とする。
集合 MK={[math]\sum_{n\in z}C_nK_n[/math]|Ci∈mi, i∈z} をとったとき、任意の ε＞0 に対して |X-Y|＜ε となる Y∈MK が存在することを、 K進法で X を表記できるという。
ε を 0 に近づけたときの、 MK の元の極限 [math]\sum_{n\in z}C_nK_n[/math]を X の K進展開 と呼び、これを ...C2C1C0.C-1C-2... と書いたものを X の K進表記(あるいは X の K進表現、あるいは X を意味する K進数)と呼ぶ。 このとき、0番位以外で仮数が 0 の位が無限に続く部分は省略するが、 省略されずに残った位の個数を桁数と呼ぶ(助数詞は桁)。
ある記数法において、ある（あるいは、全ての）整数について[1]表記法が複数あるような場合を、冗長であるという。
関連項目
注・参考文献
- ↑ 実数の場合、1.0 = 0.999... であるように、記数法ではなく数そのものの性質に由来する、表記の冗長性がある。
- 伊東規之『マイクロコンピュータの基礎』日本理工出版会 ISBN 9784890194322