広義の記数法

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

1. 標準的な記数法
----------

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

書き方は位取り記数法と同じく、底が //K// であれば、数

を

のように仮数を書き並べることで表記できる。この記法では、//n// を自然数とすると

が成り立つ。一般的に位取り記数法と呼ばれるものは、0 から //N// − 1 までの //N// 個の整数を仮数にもつ底が //N// の表記法のことである。これは任意の 0 以上の実数を無限に近似できるが、その他の数を表記するには演算子が必要となる。

中には底が自然数でないものも考えられている。コンピュータでは二進法を用いている場合がほとんどだが、符号の扱いが難しい。そこで、底を −2 とした記法が考えられた。この方法では、0 と 1 を用いてすべての整数を表すことが出来る。その他に複素数を表記するため、−1 + //i// を底としたものも考えられている。これらはドナルド・クヌースにより考案されたが、演算が複雑なため実際に用いられることは稀である。

1.1. 自然数を表記するもの
---------------

仮数が //N// 通りであるものの、0 を含まずに 1 から //N// までを使用するのがenである。この表記法で整数の 0 を表そうとすると空文字列になってしまう。また、途中の桁を 0 にすることはできない。//N//=26 である A, B, ..., Z, AA, AB, ... のような形式が、表計算ソフトの列名などで用いられている。//N//=1 とすると一進法となる。

1.2. 実数を表記するもの
--------------

仮数が //N// 通りであれば、底は ±//N// となる。

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



1.3. 複素数を表記するもの
---------------

//i// は虚数単位とする。仮数が //n// 通りであれば、底の絶対値はとなる。

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

注釈

2. 冗長な記数法
---------

ここでは、小数点から上に数えて n番目の位を n-1番位と呼ぶことにする。 例えば二進法では、n番位の重みは 2n である。

次に例を挙げる。

冗長二進法  とは、符号付二進法  の一種で、 -1, 0, 1 を仮数に持ち、底を 2 とした記数法である。任意の実数はこの表現を無限に持つ。
非隣接形式  [F] とは、冗長二進法において隣接する二つの位の少なくとも一方の仮数を 0 としたものであり、符号付二進法の一種である。この記法による表現は任意の整数に対して一つだけ存在する。この表記方法は通常の二進法と比較して、仮数が 0 の位が多く乗法や指数演算の処理速度が速い。応用例としては、楕円曲線上のスカラー倍算を効率的に計算する方法が知られている。
相互交代形式  [G] とは、冗長二進法において、0 を除くと 1 と -1 が交互に並び最上位が 1 で最下位が -1 としたものであり、符号付二進法の一種である。この記法による表現は任意の自然数に対して一つだけ存在する。 2004 年 8 月 23 日に、日立製作所により発表された。
0, 1 を仮数に持ち、底を黄金比 φ とし、隣り合う二つの位の少なくとも一方の仮数を 0 とした記数法  [K] がある。この記法では各位で、11 = 100 および 1 + 1 = 10.01 が成り立つ。また十進法で表記された数は、この記法では 10.1 と表記できることにも注意したい。

3. 複数の底の混在
----------

表記法の内部で底 //N// が一定であれば各桁の重みは //N// の冪乗となるが、ここではそれに限定しない表記法を述べる。

桁数が制限された二進法の、最上位の一つ下の位の底を -2 とした表記法 [H] による表記は2の補数表記と一致する。
二五進法 [I] とは、偶数番位は仮数が 0, 1, 2, 3, 4 で底が 5 、奇数番位は仮数が 0, 1 で底が 2 である記数法である。これは十進法の一つの位を二つに分割した形となっており、そろばんではこれが使用されている。
階乗進法  [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 の階乗の逆数となる。
時間の表記法の各単位を桁とみなすと、例えば32週5日7時間45分の各桁の重みは、週: 10080 分、日: 1440 分、時間: 60 分と言うことができる。

4. 対応表
------

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



5. 演算
-----

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

5.1. 加法、減法、乗法
-------------

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

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



5.2. 除法
-------

底を K とした K進法の上で R を D で割る手順を説明する。 記数法によって決まる、一桁の商を示す二変数関数 QK が分かっているとし、 十分に大きな整数 n をとり、次の計算を行う。 rn=R cn=QK rn-1= rn-cnDKn cn-1=QK rn-2=rn-1-cn-1DKn-1 cn-2=QK rn-3=rn-2-cn-2DKn-2

......

c0=QK r-1= r0-c0D

商は K進法で cncn-1…c0 となり、 余りは r-1 となる。 ただし記数法によっては、 0.XXX... の形で表記できる範囲がフラクタルを描くため QK が作れなくなり、除算が不可能となる。 またこの操作をさらに続けると、循環小数が商として得られる。Q の例を次に示す。

十進法d≦0 または r＜0 または 10d≦r は禁止で、
0≦r＜d ならば Q=0
d≦r＜2d ならば Q=1
2d≦r＜3d ならば Q=2
......
8d≦r＜9d ならば Q=8
9d≦r＜10d ならば Q=9 となる。

底が -2 で仮数に 0, 1 を持つ記数法d=0 または  または  は禁止で、
d/3＜r≦4d/3 または 4d/3≦r＜d/3 ならば Q=1
-2d/3≦r≦d/3 または d/3≦r≦-2d/3 ならば Q=0 となる。

平衡三進法d=0 または  または  は禁止で、
d/2＜r≦3d/2 または 3d/2≦r＜d/2 ならば Q=1
-d/2≦r≦d/2 または d/2≦r≦-d/2 ならば Q=0
-3d/2≦r＜-d/2 または -d/2＜r≦-3d/2 ならば Q=-1 となる。

6. 記法の変換方法
----------

標準的な記数法に対しての、数の表記法を変換する方法を説明する。

6.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 から平衡三進法では 10001 と表記できる。

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

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

の 2 式が得られる。 x+y が奇数なら -x+y, -x-y も奇数なので p, q が整数であることに注意すると、 x+y が奇数のとき c=1 、偶数のとき c=0 がわかる。

6.2. 十進法からの変換
-------------

上にある除法の節の QK を利用し、次の計算を行う。 変換前の十進数を R とする。 r0=R c0=QK r1=K× c1=QK r2=K× c2=QK r3=K× ...... これにより、 R は K進法で c0.c1c2c3... と表記できる。

6.3. 十進法への変換
------------

上位より仮数を足してから底を掛けていく方法がある。

例えば 0, 1 を仮数に持ち、底を -2 とした記数法で表記された数 1101101 を十進法に変換すると、 0+1= 1 1×= -2 -2+1= -1 -1×= 2 2+0= 2 2×= -4 -4+1= -3 -3×= 6 6+1= 7 7×=-14 -14+0=-14 -14×= 28 28+1= 29 から十進法では 29 と表記できる。

6.4. 十進法への変換
------------

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

6.5. 十進法への変換
------------

次の式を利用して変換できる。 　　　　　

6.6. 位の統合と分割
------------

二つの記数法があるとし、それぞれの底が n, nk となっており、 底が n の方で k桁で表される全ての数が、底が nk の方では 1桁で表される時、 その対応により、各位を変換するだけで任意の数を変換することができる。 例えば、0, 1 を仮数に持つ底が -2 の記数法 [A] と、 -2, -1, 0, 1 を仮数に持つ底が 4 の記数法 [B] は、 10 と 、11と 、00 と 0 、01 と 1 が対応しているので、 例えば [A] で表記された 100011011 の二つの位を一つに統合すると、 101 となり [B] での表記が得られる。

7. 詳しい定義
--------

各用語の詳しい定義を紹介する。

0 を含む連続した整数の集合 z をとり、その元を位と呼ぶ。 特定の位をさしたいときには、0番位や 1番位と単位をつけることにする。 そして、任意の n∈z に対して空でない実数の有限集合 mn をとり、 その元を n番位の仮数と呼ぶ。そして、任意の n∈z に対して実数 Kn を定め、 この Kn を n番位の重みと呼び、 Kn+1/Kn を n番位の底と呼ぶ。 これらをもとに数を表す方法を記数法という 。 この z, mn, Kn による記数法をK進法とする。

集合 MK={|Ci∈mi, i∈z} をとったとき、任意の ε＞0 に対して |X-Y|＜ε となる Y∈MK が存在することを、 K進法で X を表記できるという。

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

ある記数法において、ある整数について表記法が複数あるような場合を、冗長であるという。

8. 関連項目
-------

位取り記数法
p進数
命数法

9. 注・参考文献
---------

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