記数法のさまざまな拡張
~2進数からButchi数まで~

面白法人カヤック 岩淵勇樹

自己紹介

10進法(decimal)

既知
人間が普段使っている記数法
base
10
digit
0, 1, 2, 3, 4, 5, 6, 7, 8, 9
例: 1984=1×103+9×102+8×101+4×100

用語説明

base
radix、基数、底。仮数に掛け合わせる数(重みの倍率)
digit
仮数。その位に記される数

16進法(Hexadecimal)

既知
コンピューターでよく使われている
HTMLのカラーコードは16進数を3つ並べて表記する(#ffffffなど)
base
16
digit
0, 1, 2, 3, 4, 5, 6, 7, 8, 9, a, b, c, d, e, f
例: 2d=2×161+13×160=45

2進法(binary)

既知
base
2
digit
0, 1
例: 1011=1×23+0×22+1×21+1×20=13
8421
00000
00011
00102
00113
01004
01015
01106
01117
8421
10008
10019
101010
101111
110012
110113
111014
111115

3進法(ternary)

既知
base
3
digit
0, 1, 2
931
0000
0011
0022
0103
0114
0125
931
0206
0217
0228
1009
10110
10211

N進法(まとめ)

既知
base
N
digit
0~N-1
k = 1 n a k N k

黄金進法(φ進法)(phinary, golden ratio base)

既知
base
1 2 ( 1 + 5 ) (=φ)
digit
0, 1
自然数全体に加えて一部の無理数も表現できる(10=φなど)

黄金進法(φ進法)(phinary, golden ratio base)

既知
φ4φ3φ2φ1φ0φ-1φ-2φ-3φ-4
0000000000
0000100001
0001001002
0010001003
0010101004
0100010015
0101000016
1000000017
1000100018
1001001019
10100010110

フィボナッチ記数法(フィボナッチ符号)

既知
base
フィボナッチ数
digit
0, 1
自然数全体を表現できる

フィボナッチ記数法(フィボナッチ符号)

既知
85321
000000
000011
000102
001003
001014
010005
010016
010107
100008
100019
1001010

ゼッケンドルフの定理

既知
自然数は隣り合わないフィボナッチ数の和で表せる

二五進法

既知
そろばんで用いられる
十進数 二五進法 二進数
0 0 000 0000
1 0 001 0001
2 0 010 0010
3 0 011 0011
4 0 100 0100
5 1 000 0101
6 1 001 0110
7 1 010 0111
8 1 011 1000
9 1 100 1001

グレイコード

既知
00000
00011
00112
00103
01104
01115
01016
01007
11008
11019
111110
111011
101012
101113
100114
100015

(蛇足)グレイコードの歌

独自
グレイコードカウンタの歌

符号付き2進法

既知
base
2
digit
-1, 0, 1
NAF表記(0でないdigitが連続しない)によって一意性が保たれる

符号付き2進法

既知
8421
0-10-1-5
0-100-4
0-101-3
00-10-2
000-1-1
00000
00011
00102
010-13
01004
01015
10-106
100-17
10008
10019
101010

平衡3進法

既知
base
3
digit
-1, 0, 1
コンピューターで計算がしやすい

平衡3進法

既知
931
0000
0011
01-12
0103
0114
1-1-15
1-106
1-117
10-18
1009
10110

Bijective numeration

既知
k-adicの場合:
base
k
digit
1~k
0を使わない記数法

Bijective numeration (1-adic)

既知
11111
ε
1
11
111
1111
11111

Bijective numeration (2-adic)

既知
421
ε0
11
22
113
124
215
226
1117
1128
1219
12210

-2進法(negabinary)

既知
base
-2
digit
0, 1
整数全体を表せる記数法

-2進法(negabinary)

既知
16-84-21
01111-5
01100-4
01101-3
00010-2
00011-1
000000
000011
001102
001113
001004
001015
110106
110117
110008
110019
1111010

-1+i進法

既知
base
-1+i
digit
0, 1
D. Knuthが考案
有限桁でガウス整数を記述可能

1+i進法

独自
base
1+i
digit
0, 1
有限桁ではガウス整数全体は記述不可

i+1進法

既知

Twindragon

既知

2i進法

既知
base
2i
digit
0, 1, 2, 3
D. Knuthが考案

黄金進法の負への拡張

未知
(-φ)4(-φ)3(-φ)2(-φ)1(-φ)0(-φ)-1(-φ)-2(-φ)-3(-φ)-4
0000000000
0000100001
0001001002
0010001003
0010101004
0100010015
0101000016
1000000017
1000100018
1001001019
10100010110

フィボナッチ記数法の負への拡張

未知
13-85-32-11
0100101-5
0001010-4
0001000-3
0001001-2
0000010-1
00000000
00000011
00001002
00001013
00100104
00100005
00100016
00101007
00101018
10010109

factorial based radix

既知
base
n!
digit
0~n
3!2!1!0!
00101
01002
01103
02004
02105
10006
10107
11008
11109
120010

p-進法

既知
無限桁で負の数を含む有理数を表せる
-1=…111111
-1/3=…010101

(蛇足)3足さん!

http://butchi.jp/documents/program/santasan/

(蛇足)

Googleで「16進数」を検索すると…

繰り上がり則

2進法では、左に繰り上がる
2進法の繰り上がり則

繰り上がり則

黄金進法では左に1繰り上がり、右に2繰り下がる
黄金進法の繰り上がり則

繰り上がり則

では、上にも繰り上がってはどうか?
Butchi数の繰り上がり則

Butchi数

独自
Butchi数解説ページ
卒業論文「2進数の平面的表現に関する考察」

余談

このスライドはHTML 5の技術を用いて作りました。
数式はMathematicaを用いてMathMLで記述しています。
Firefox 14で動作確認済みです。