広義の記数法

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

次に例を挙げる。

• 冗長二進法 (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 日に、日立製作所により発表された^[1]。
• 0, 1 を仮数に持ち、底を黄金比 φ とし、隣り合う二つの位の少なくとも一方の仮数を 0 とした記数法 (golden ratio base, 黄金進法) [K] がある。この記法では各位で、11 = 100 および 1 + 1 = 10.01 が成り立つ。また十進法で表記された数${\displaystyle {\sqrt {5}}}$は、この記法では 10.1 と表記できることにも注意したい。

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

• 桁数が制限された二進法の、最上位の一つ下の位の底を -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 の階乗の逆数となる。
• 時間の表記法の各単位を桁とみなすと、例えば32週5日7時間45分の各桁の重みは、週: 10080 分、日: 1440 分、時間: 60 分と言うことができる。

Summarize Timeline Top Qs Fact Check

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

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

Summarize Timeline Top Qs Fact Check

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

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

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

加算 + ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {1}}}$ 0 1 ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {1}}}$0 ${\displaystyle {\bar {1}}}$1 ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {1}}}$ ${\displaystyle {\bar {1}}}$ ${\displaystyle {\bar {1}}}$1 ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {1}}}$ 0 0 ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {1}}}$ 0 1 1 ${\displaystyle {\bar {1}}}$ 0 1 1${\displaystyle {\bar {2}}}$

減算 (左－上) － ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {1}}}$ 0 1 ${\displaystyle {\bar {2}}}$ 0 ${\displaystyle {\bar {1}}}$ ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {1}}}$1 ${\displaystyle {\bar {1}}}$ 1 0 ${\displaystyle {\bar {1}}}$ ${\displaystyle {\bar {2}}}$ 0 1${\displaystyle {\bar {2}}}$ 1 0 ${\displaystyle {\bar {1}}}$ 1 1${\displaystyle {\bar {1}}}$ 1${\displaystyle {\bar {2}}}$ 1 0

乗算 × ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {1}}}$ 0 1 ${\displaystyle {\bar {2}}}$ 10 1${\displaystyle {\bar {2}}}$ 0 ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {1}}}$ 1${\displaystyle {\bar {2}}}$ 1 0 ${\displaystyle {\bar {1}}}$ 0 0 0 0 0 1 ${\displaystyle {\bar {2}}}$ ${\displaystyle {\bar {1}}}$ 0 1

底を K とした K進法の上で R を D で割る手順を説明する。 記数法によって決まる、一桁の商を示す二変数関数 Q_K が分かっているとし、 十分に大きな整数 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進法で c_nc_n-1…c₀ となり、 余りは r_-1 となる。 ただし記数法によっては、 0.XXX... の形で表記できる範囲がフラクタルを描くため Q_K が作れなくなり、除算が不可能となる。 またこの操作をさらに続けると、循環小数が商として得られる。

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 となる。

Summarize Timeline Fact Check

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

余りが仮数に含まれるように底で割っていく方法がある。この方法では下位の仮数から求まる。

例えば十進法で表記された数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${\displaystyle {\bar {1}}}$${\displaystyle {\bar {1}}}$00${\displaystyle {\bar {1}}}$01${\displaystyle {\bar {1}}}$ と表記できる。

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

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

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

${\displaystyle {\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 がわかる。

上にある除法の節の Q_K を利用し、次の計算を行う。 変換前の十進数を 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進法で c₀.c₁c₂c₃... と表記できる。

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

例えば 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 と表記できる。

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

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

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