ノイマン型コンピュータにおける計算限界と計算誤差
前回分は滅茶苦茶書き足してきたので読み直しておいてください。
8月実施予定の2学期末テストでは書き足した内容も出すよ。
物理的に論理回路の作り方は高校範囲外(というより情報系学部でも物理回路の専門家じゃないとやらない)ので除外するけど。
プログラミング言語での変数型
完全チューリングマシンを実装したパターンから初歩的なCPU、メモリを備えたノイマン型コンピュータに進化してきたあと、プログラミング言語が機械語(低級言語)から高級言語(C言語とかPythonとか)に進む間、人間は自力で機械語を書いていました。
このころに有名なプログラマーとしてはグレース・ホッパー女史とかがいらっしゃる。（COBOLの開発者）
ちなみにプログラム上の不具合をバグというが、ホッパー女史のコンピュータで「プログラムは正しいはずなのに計算結果がおかしい」と調査していく中でハードウェアの箱を開けたら蛾が1匹詰まっていてそのせいで熱暴走して計算結果が異なっていた、ということからきているといわれる。
閑話休題。
んで、一般のPCにおいては1B=8bitで計算をするわけなんだけど、8bitで表現できるのは0~255の256段階しかないわけです。
少なくね？
ということでコンピュータが進歩するたびに2B、3B、4Bで1つの値を表現しようぜ？という方向に進んだ。
COBOLのほかにもC言語も初期の高級言語にあるけども、C言語の時点で複数バイトを変数の型として持つことになった。
変数の型とはInteger,characterなど、「この変数は整数を表現する」といった宣言を行うことで計算処理が行える。
その種類としては、
- Integer:整数
- Character:文字
- float:実数
- Double:倍精度実数
あたりがC言語では基本として存在する。
なお、コンパイラ環境ごとに型ごとのB数が異なるので、異なる環境から持ってきたソースコードをコンパイルする際は注意が必要。
(https://qiita.com/yamadasuzaku/items/29de9a5761f3bf0768e0)
で、よくある問題としてint(整数)型÷int型をするとどうなるか？
例えば1/2 =0.5 と何も考えずに計算する人が多いわけだが、答えをint型で、と指定されると答えは0になる。
(0あまり1 という小数分数をやる前の小学生に戻るのだ！)
ちーなーみーにー 自然数・整数・実数の区別は中学1年の範囲ぞ？区別しとけ？(中1で出てくる無理数はπのみ。)
なお実数を分解する有理数無理数については平方根の理解が必要なので二次関数をやる中3の範囲。
虚数及び複素数は高校2年生の数学Ⅱの範囲になったぞ。
四元数は物理エンジンなどで利用するには滅茶苦茶便利らしいが専門的な内容になるので大学数学部以上の内容になる。
八元数とか十六元数？ここで触れるにはその内容は高度すぎる。
おーばーふろー
アダルトゲームメーカーの一つ・・・ではなくて、計算するとき、変数は型ごとに上限のバイト数を持っているわけだけど、それを超えたらどうなるの？という問題にぶち当たる。
これが計算できる範囲を上振れしてこえるとオーバーフローという。
オーバーフロー発生時にどういう処理をするか、という点についてはコンパイラだったりプログラム内で異なっていて、使えるメモリに制限が強かったファミコン・スーファミ・GBあたりではこのあたりの処理がおかしくて愉快なバグが発生することが多い。
最近の話題だとDQ4における8逃げバグ(8回逃げると以降の通常攻撃が常に会心の1撃になる)などが該当。
https://togetter.com/li/1715732
ちなみにカジノのコイン暴落とかもこれ。https://dic.nicovideo.jp/a/838861
逆に下限を下回るとアンダーフローという。
整数型を作る場合、最左bitが1のときは負の数、歳差bitが0のときは正の整数と扱うことが多い。(1Bで0~255を表現するときは「非負整数である」という宣言の仕方となる)
ソフトウェア上で必要なメモリの割り当てなどを実施するのがOSの役割になるけども、OS割り当て範囲を乗り越えてメモリ範囲を侵食することをバッファオーバーフロー、バッファオーバーランという。
C言語など、メモリ直接操作機能が残っている処理系でプログラミングを行う場合、プログラマはそういったバッファオーバーランを起こさないようにプログラミングする必要がある。
Java等VMを利用する言語の場合、OSとの間にVMが入るのでVMでもバッファオーバーランを防止するため、C言語などよりはプログラマはこの点を考えなくてよい(代わりにVMがOverflowExceptionを吐くけどな)
計算誤差
詳細をがっつり読みたい方は上記リンク参照。
2進数で0.1と記載すると10進数で0.5になる。
これは2進数の小数点より上の桁が10進数で表現すると1,2,4,8,16,32...と2の乗数になるためだが、同じ理屈で小数点第1位は10進数で0.5、小数点第2位は10進数で0.25になるためである。
とすると、10進数でいうところの0.1などは2進数に直すと無限小数になってしまうため、完全一致した計算ができない場合が存在する。
このような小数点以下のbit数限界を超過する計算の場合、誤差が出る。
誤差を出さないようにする工夫の一つが2進化10進数などである。(4bitで10進数の桁が表記できるので、4bitで10進1桁を計算していけばいいんでね？という力技)
ちなみに実数型の名前が浮く(float)とか2重(double)という名前になっているかというと、実数(小数)の計算をする際に固定小数点と浮動小数点という考え方があった。
固定小数点は例えば2Bのデータのうち、左側1B目が小数点より大きい桁、右側1Bが小数点第1位～8位と固定するやり方である。(最左bitで正負を表現するのは変わらない)
この方式は人間がわかりやすいというメリットと単純さがあるが、1未満の小数を足し算し続けるようなことをすると、常に2B中1Bが無駄に桁を確保することになる。
そこで、小数点の位置を表現するための数bitとそれ以外のbitで数値表現してしまおうという浮動小数点方式が考え出された。
プランク定数6.62607015×10^(-34) を0.000...(略)...662607015と書かず、10^(-34)を掛け算することでスペースの省略と計算のしやすさが出せているわけだ。
これを2進数で同じようにしたのがfloat型だ。浮動小数点なので、浮いた(float)なのである。
んで、しばらくしてfloatだと計算精度が足らない、ということで「んじゃfloatの2倍のbit数付けりゃより正確だろ」という発想のもと2倍の精度の実数、ということでdouble型が用意された。
それでもbit数の限界があるので、その限界を丸め誤差という。
他に、差がほとんどない小数の引き算をすると有効数字ががた減りする桁落ち誤差がある。
ゲーデルの不完全性定理と停止性問題
ノイマン型コンピュータというか完全チューリングマシンにおいて、「プログラムが停止するかどうかを判別するプログラムは作成不能」という決定不可能性問題が存在する。
詳細はこの本が詳しいので読むといいよ
https://bookmeter.com/books/7977255
めっちゃ疲れた