広義の記数法

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

この項では基本的な位取り記数法を除く、負の数や虚数を含む記数法等について述べる。 ここでは仮数とは、その位に記された数のこととし、 底(てい)とは、その位の一つ上の位の値が持つ、その位に対する重みの倍率とする。

標準的な記数法[編集]

この節では、底が一定で冗長でない記数法について説明する。

書き方は位取り記数法と同じく、底が K であれば、数 …+c2K2+c1K1+c0K0 +c-1K-1+c-2K-2+… を …c2c1c0.c-1c-2… のように仮数を書き並べることで表記できる。 この記法では、n を自然数とすると10^n=1\overbrace{0\cdots 0}^{n}が成り立つ。 一般的に位取り記数法と呼ばれるものは、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 通りであれば、 底の絶対値は\sqrt{n}となる。

任意の複素数を表記できるものとして、次の例が考えられる。

名前 仮数 一桁の演算で繰り上がる確率 除算
加算 乗算
なし 0, 1 -1+i 1/4 0/4 不可
なし 0, 1 \sqrt{2}i 1/4 0/4
なし[A'] 0, 1, -\frac{1}{2}+\frac{\sqrt{3}}{2}i, -\frac{1}{2}\frac{\sqrt{3}}{2}i -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 が成り立つ。また十進法で表記された数\sqrt{5}は、この記法では 10.1 と表記できることにも注意したい。

対応表[編集]

ここでは -n を\bar{n}と表記する。 他には、WWW との適合性のため -n を n と書いたり、 \bar{1}を単に T と書く手法もある。

十進法 [A] [B] [C] [D] [E] [F] [G] [H] [I] [J] [K]
-16 110000 \bar{1}00 \bar{1}11\bar{1} 1102 \bar{3}\bar{1} \bar{1}0000 10000
-15 110001 \bar{1}01 \bar{1}110 1220 \bar{3}0 \bar{1}0001 10001
-14 110110 \bar{1}1\bar{2} \bar{1}111 1221 \bar{3}1 \bar{1}0010 10010
-13 110111 \bar{1}1\bar{1} \bar{1}\bar{1}\bar{1} 1222 \bar{1}3\bar{3} \bar{1}010\bar{1} 10011
-12 110100 \bar{1}10 \bar{1}\bar{1}0 1210 \bar{3}3 \bar{1}0100 10100
-11 110101 \bar{1}11 \bar{1}\bar{1}1 1211 \bar{1}3\bar{1} \bar{1}0101 10101
-10 1010 \bar{2}\bar{2} \bar{1}0\bar{1} 1212 \bar{1}30 \bar{1}0\bar{1}0 10110
-9 1011 \bar{2}\bar{1} \bar{1}00 1200 \bar{1}31 \bar{1}00\bar{1} 10111
-8 1000 \bar{2}0 \bar{1}01 1201 \bar{1}\bar{3} \bar{1}000 11000
-7 1001 \bar{2}1 \bar{1}1\bar{1} 1202 \bar{1}33 \bar{1}001 11001
-6 1110 \bar{1}\bar{2} \bar{1}10 20 \bar{1}\bar{1} \bar{1}010 11010
-5 1111 \bar{1}\bar{1} \bar{1}11 21 \bar{1}0 \bar{1}0\bar{1} 11011
-4 1100 \bar{1}0 \bar{1}\bar{1} 22 \bar{1}1 \bar{1}00 11100
-3 1101 \bar{1}1 \bar{1}0 10 \bar{3} \bar{1}01 11101
-2 10 \bar{2} \bar{1}1 11 \bar{1}3 \bar{1}0 11110
-1 11 \bar{1} \bar{1} 12 \bar{1} \bar{1} 11111
0 0 0 0 0 0 0 00000 0 0 0
1 1 1 1 1 1 1 1\bar{1} 00001 1 10 1
2 110 1\bar{2} 1\bar{1} 2 1\bar{3} 10 1\bar{1}0 00010 2 100 10.01
3 111 1\bar{1} 10 120 3 10\bar{1} 10\bar{1} 00011 3 110 100.01
4 100 10 11 121 1\bar{1} 100 1\bar{1}00 00100 4 200 101.01
5 101 11 1\bar{1}\bar{1} 122 10 101 1\bar{1}1\bar{1} 00101 10 210 1000.1001
6 11010 1\bar{2}\bar{2} 1\bar{1}0 110 11 10\bar{1}0 10\bar{1}0 00110 11 1000 1010.0001
7 11011 1\bar{2}\bar{1} 1\bar{1}1 111 1\bar{3}\bar{3} 100\bar{1} 100\bar{1} 00111 12 1010 10000.0001
8 11000 1\bar{2}0 10\bar{1} 112 13 1000 1\bar{1}000 01000 13 1100 10001.0001
9 11001 1\bar{2}1 100 100 1\bar{3}\bar{1} 1001 1\bar{1}01\bar{1} 01001 14 1110 10010.0101
10 11110 1\bar{1}\bar{2} 101 101 1\bar{3}0 1010 1\bar{1}1\bar{1}0 01010 100 1200 10100.0101
11 11111 1\bar{1}\bar{1} 11\bar{1} 102 1\bar{3}1 10\bar{1}0\bar{1} 1\bar{1}10\bar{1} 01011 101 1210 10101.0101
12 11100 1\bar{1}0 110 220 3\bar{3} 10\bar{1}00 10\bar{1}00 01100 102 2000 100000.101001
13 11101 1\bar{1}1 111 221 1\bar{3}3 10\bar{1}01 10\bar{1}1\bar{1} 01101 103 2010 100010.001001
14 10010 10\bar{2} 1\bar{1}\bar{1}\bar{1} 222 3\bar{1} 100\bar{1}0 100\bar{1}0 01110 104 2100 100100.001001
15 10011 10\bar{1} 1\bar{1}\bar{1}0 210 30 1000\bar{1} 1000\bar{1} 01111 110 2110 100101.001001

演算[編集]

標準的な記数法の上での、加法減法乗法除法算法について説明する。

加法、減法、乗法[編集]

加法と乗法については、あらかじめ各仮数同士の計算結果を表にしておき、それを見ながら計算すればよい。 加算時の繰り上がりは上の位にさらに足すことや、二桁以上の乗算については、 10^n=1\overbrace{0\cdots 0}^{n}が成り立つことに注意して計算を実行していく。 減法については表を作ってもよいが、 引く数に -1 を掛けてから引かれる数に足すという方法も考えられる。

例として、底が 4 で仮数に -2, -1, 0, 1 を持つ記数法の、加算と減算と乗算の表を次に示す。

加算
+ \bar{2} \bar{1} 0 1
\bar{2} \bar{1}0 \bar{1}1 \bar{2} \bar{1}
\bar{1} \bar{1}1 \bar{2} \bar{1} 0
0 \bar{2} \bar{1} 0 1
1 \bar{1} 0 1 1\bar{2}
減算 (左-上)
\bar{2} \bar{1} 0 1
\bar{2} 0 \bar{1} \bar{2} \bar{1}1
\bar{1} 1 0 \bar{1} \bar{2}
0 1\bar{2} 1 0 \bar{1}
1 1\bar{1} 1\bar{2} 1 0
乗算
× \bar{2} \bar{1} 0 1
\bar{2} 10 1\bar{2} 0 \bar{2}
\bar{1} 1\bar{2} 1 0 \bar{1}
0 0 0 0 0
1 \bar{2} \bar{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
底が -1+i で 0, 1 を仮数に持つ記数法により 0.XXX... の形で表記できる範囲。ツインドラゴン曲線と酷似する。

商は 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\bar{1}\bar{1}00\bar{1}01\bar{1} と表記できる。

また、基本的には複素数を表記する記数法ではこの変換は難しいが、 底が -1+i で仮数に 0, 1 を持つ記数法では、比較的簡単に計算できる。 ある複素数 x+yi に対して (x, y は整数) 、

(x + yi) ÷ (-1 + i) = p + qi . . . c

となる整数 p, q と仮数 c を求める。この式を変形すると、

\frac{-x+y+c}{2}=p\qquad\frac{-x-y+c}{2}=q

の 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 と表記できる。

十進法への変換(有限小数部分)[編集]

上位より仮数を足してから底を掛けていき、最下位の仮数を足したら、 それに最下位の重みを掛けるという方法がある。

十進法への変換(循環小数部分)[編集]

次の式を利用して変換できる。 \frac{1}{e}+\frac{1}{e^2}+\frac{1}{e^3}+\cdots =\frac{1}{e-1}      (|e|>1)

位の統合と分割[編集]

二つの記数法があるとし、それぞれの底が n, nk となっており、 底が n の方で k桁で表される全ての数が、底が nk の方では 1桁で表される時、 その対応により、各位を変換するだけで任意の数を変換することができる。 例えば、0, 1 を仮数に持つ底が -2 の記数法 [A] と、 -2, -1, 0, 1 を仮数に持つ底が 4 の記数法 [B] は、 10 と\bar{2} 、11と\bar{1} 、00 と 0 、01 と 1 が対応しているので、 例えば [A] で表記された 100011011 の二つの位を一つに統合すると、 101\bar{2}\bar{1} となり [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={\sum_{n\in z}C_nK_n|Ci∈mi, i∈z} をとったとき、任意の ε>0 に対して |X-Y|<ε となる Y∈MK が存在することを、 K進法で X を表記できるという。

ε を 0 に近づけたときの、 MK の元の極限 \sum_{n\in z}C_nK_nを X の K進展開 と呼び、これを ...C2C1C0.C-1C-2... と書いたものを X の K進表記(あるいは X の K進表現、あるいは X を意味する K進数)と呼ぶ。 このとき、0番位以外で仮数が 0 の位が無限に続く部分は省略するが、 省略されずに残った位の個数を桁数と呼ぶ(単位は桁)。

また、表記を無限に持つ数が存在する記数法を、冗長であるという。

関連項目[編集]

参考文献[編集]

  • 伊東規之『マイクロコンピュータの基礎』日本理工出版会 ISBN 9784890194322