float、double、IEEE、不思議の国のアリス

【参考】1,2,3,4,,


浮動小数点方式で小数を表現する場合、
・32ビット使う方法（＝IEEEの単精度＝float型）
・64ビット使う方法（＝IEEEの倍精度＝double型）
がある。
ちなみにint型＝32ビット符号付整数、long型＝64ビット符号付整数である。

単精度を例にとる。

32ビット＝符号部S（１）＋指数部E（８）＋仮数部M（２３）


によって、

(-1) ^S × 1.M (2) × 2 ^E-127


を表現する。仮数部の「1.M」という形を正規化という。
0 ≦ E ≦ 254　∴ -127 ≦ E - 127 ≦ 127 なので、
「1.M」を元にして小数点が左右に127ずつフワフワ動く感じ。

ここでめっちゃちっこい数（0に近い数）を考えてみる。

それは E = 0 のときで、1.0...00 (2) × 2 ^-127
その次に小さい数は、　1.0...01 (2) × 2 ^-127
その差は、　　　　　　　　0.0...01 (2) × 2 ^-127 = 2 ^-150

刻みが2 ^-150ごとの定規なのに、最初の刻みだけ、0から2 ^-127の場所にある、ってこと。

これは、

目盛りが1mmごとの定規なのに、最初の目盛りは、0から8388608 mm = 8.4 km の場所にある

ってこと。馬鹿みたい。
この定規は、進んだ距離が２倍になると、目盛り幅も２倍になる、という性質をもつ。
たぶん、アリスの不思議の国あたりにある。「浮動」っていうのもチェシャ猫っぽい。
もし何かの刑罰で、
「〇目盛り進むまで決して休んではならない」みたいなルールでこの定規を歩かされたら、
かなり精神的に「くる」のは間違いない。

このままだと、2 ^-127より0に近い数は、アンダーフローで0化するので計算に支障が出る。
そこで、

32ビット＝符号部S（１）＋指数部E（８）＋仮数部M（２３）


によって、

(-1) ^S × 1.M (2) × 2 ^E-127


ただし、E = 0ならば、

(-1) ^S × 0.M (2) × 2 ^-126

を表すことにする。仮数部の「0.M」という形を非正規化という。

現在これらの仕様は、IEEE754 2008として策定されている。

なお、

・非正規数が発生すると、演算が遅くなるらしい。
・floatは計算時にはdoubleに変換されるので、特に速度メリットはないらしい。格納メモリは半分で済むけど。

Read More...

ソートアルゴリズムの計算量をくらべる

ソートアルゴリズムの計算量をまとめてみた。
ただし、マージソート・クイックソート・シェルソートあたりの優劣は、
ソート対象の個数や状態によって変動する。

例えばこの表からでも、

クイックソートはソート個数が一定以上になると、シェルソートより速くなりそう・・・

って事がわかる。

理由としては、「n log n」 vs 「n exp(1.25)」　はnによって大小関係が変わってくるから。
分岐点を探してみる。

n log n = n exp(1.25) ⇒ log n = n exp(1/4)

簡単のために、n = 2 exp(p)　とおくと、

p = 2 exp(p/4) ⇒ p exp(4) = 2 exp(p)

p = 16, n = 2 exp(16)

よって、n > 2の16乗（=65536） だと、n log n < n exp(1.25) となり、
オーダが逆転してしまう。

Read More...

小学生でもわかる、補数による負数表現

歴史的経緯とか言葉の意味とか、
「最上位ビットで+/-を表現するだけ」だと00000000も10000000も「0」になって困るとか、
とにかく難しいことは忘れる。

まずコンピュータ＝

引き算の筆算で、「隣の位から１０借りてくる」ことがどうしてもわからなくて、算数が嫌いになりそうな小学生

だと考える。
（ちなみに元教師の経験から言うが、
「隣の位から借りてくる」をうまく教えられるかどうかで教師の力量がわかる。）

例題：98765 - 45678

一の位から困る。泣き出す小学生。
「隣の位から」借りると難しいので、どーんと99999借りることにする。
もちろん後で返すつもり・・・たぶん。

すると、もちろん「99999 - 45678」を先に計算してもいい。
絶対に「隣から借りる」必要はないので、小学生も嬉しそう。

計算すべきは「98765 + 54321」に変身する。

引き算じゃなくなった！　でもこの心の不安はなんだろう・・・
借りていた「99999」はあとで返す、という約束を思い出す。
でも「 - 99999」は、また「隣から借りてくる」苦手な計算になる。
小学生がまた泣きそう。

「あと1だけ貸してくれまへんか？あとで100000まとめて返しまっさかい・・・」
「わかってるやろな？　利息はトイチやで」

1借りたので、+ 54321 ⇒　+ 54322 になる。

100000を返す　＝　あふれた桁を消す（無視する）。

やったことを振り返る。

引く数45678に対して、99999 - 45678 = 54321を計算した。
これは各位の数を、9に対して反転させた数。
54321 + 1 = 54322を計算した。
98765 + 54322を計算した。
その答えから、溢れた桁の数を消した。

--------------------------------- きょうのまとめ ---------------------------------

引き算は、「引く数の各位を反転させた数 + 1」の足し算、に変身できる。溢れた桁は無視する。

ふりかえると、
元の数□□□□□＋反転させた数■■■■■　＝　99999
元の数□□□□□＋反転させた数■■■■■ + 1　＝　100000（桁が１つ増えた！）
になっている。

反転させた数 + 1は言いにくいので、桁を１つ増やすのに補うべき数、ということで、
補数と呼ぶことにする。

まとめると、
（引かれる数）－（引く数）　⇒　（引かれる数）＋（引く数の補数）

Read More...