誤差は、コンピュータ内部で演算をした際に生じる演算結果と数学上の計算結果の差です。
どのようにして生じるのかを説明します。
①丸め誤差
円周率を表現したい。
一般的には「3.14」ですが、本来なら「3.1415…」と無限に続いていきます。
「3.14」と「3.1415…」には差がありますね。
一般的な「3.14」という風に、四捨五入や切り捨て、切り上げ等の
端数処理で発生した誤差を「丸め誤差」といいます。
②けた落ち
「円周率 - 3.14」という計算をしたい。
小数第4位まで表現可能とします。
円周率を丸めこみ、「3.1415」とすると、答えは「0.0015」となります。
すると、「有効桁数」が減少しています。
「有効桁数」とは、IEEE754で説明した、正規化した際の仮数部の桁数をいいます。
すなわち、「3.1415」は5桁、「0.0015」は2桁です。
では、何が問題なのかというと、
答えの「0.0015」を100倍したときに「0.1500」となりますが…
「0.1500」の「00」って正しくはないですよね。
元を辿れば「(円周率 - 3.14) × 100」ですから、答えが「0.1500」は正しいとは言い難いです。
このような「有効桁数」の減少を「けた落ち」といいます。
③情報落ち
「100 - 0.0000000000001」という計算がしたい。
しかし、「0.0000000000001」という数値があまりにも小さく、
「100」に桁数を揃えた際に、数値を無視されてしまうことがある。
これを「情報落ち」といいます。
④打切り誤差
「1 + 1 + 1 + 1 + …」を無限に行う計算がしたい。
しかし、無限に計算することは不可能です。
そこで、適当なところで計算を打ち切りにします。
そうして発生する誤差を「打切り誤差」といいます。
コンピュータのが扱う数値の規格に「IEEE754」があります。
そもそも「IEEE」とは、電気・電子分野における世界最大の学会「The Institute of Electrical and Electronics Engineers, Inc.」のことです。
「IEEE～」というのは、この学会で決められたなにかしらの決まり事です。
「IEEE754」とは、浮動小数点数の表現方法の1つです。
(※浮動小数点数：正負、数の並び、小数点の位置の情報を合わせることで数値を表現する方法)
「IEEE754」はSEMの並びで下記の形式で表現されます。
①S： 1bit：符号
②E： 8bit：指数部
③M：23bit：仮数部
①S： 1bit：符号
数値の正負を表します。
「0」は正、「1」は負を表します。
②E： 8bit：指数部
小数点の位置を表します。
正規化した際に動かした小数点の回数分を127でバイアスして表します。
(正規化、バイアスについては下記で説明します)
③M：23bit：仮数部
数値を表します。
23bitまで表現できるので、2^23 ≒ 8,000,000となります。
つまり、「S」「E」「M」を式であらわすと、下記の通りになります。
(-1)^S × 2^(E-127) × 1.M
さて、正規化について説明します。
正規化とは、ある数値をIEEE754の規定に則した表現に直すことをいいます。
正規化の方法は下記の通りです。
ここでは、25.625を例に説明します。
①S：正負の確認
25.625は正の数のため、S = 0 となります。
②E：小数点の位置の調整
まず、「25.625」を10進数から2進数「11001.101」へ基数変換します。
ここで小数点「1.…」となるように「1.1001101 × 10＾4」とずらします。
指数、つまり、E = 4 となります。
さて、ここでバイアスの登場です。
指数部は8bit、すなわち0～255が範囲です。
ですが、これでは少数の表現の幅が狭くなります。
たとえば、「0.001」という表現が不可能ですよね。
そこで、0～255を半分に分け、-127～128と考えます。
これで「0.001」を「1 × 10＾(-3)」と表現することができます。
しかし、今度は指数部となる「-3」の表現に困ってしまいます。
そこで、指数部には必ず「127」を加算することで、この問題を解決しています。
これで、「-127」であっても、「-127 + 127 = 0」となり、表現が容易になります。
この「127」を加算することをバイアスといい、「127」自体のことをバイアス値といいます。
すなわち、「E = 4 + 127 = 131 = 10000011」となります。
③M：数値の確定
②で作った「1.1001101 × 10＾4」の「1.1001101」の少数部分「1001101」が仮数部です。
一の位の「1」は不要です。
だって、必ず「1.…」になるようにするのだから。
必要のない情報は省きましょう。
まだ、仮数部は未完成です。
仮数部は23bitになるようにしなければなりません。
ですが、作った情報は「1001101」と7bitしかありません。
残りの16bitですが…後ろに「0」を16bit付与します。
つまり、「10011010000000000000000」となります。
①～③を全て合わせると
「01000001110011010000000000000000」となります。
まず、「25.625」を10進数から2進数「11001.101」へ基数変換します。
ここで小数点「1.…」となるように「1.1001101 × 10＾4」とずらします。
指数、つまり、E = 4 となります。
さて、ここでバイアスの登場です。
指数部は8bit、すなわち0～255が範囲です。
ですが、これでは少数の表現の幅が狭くなります。
たとえば、「0.001」という表現が不可能ですよね。
そこで、0～255を半分に分け、-127～128と考えます。
これで「0.001」を「1 × 10＾(-3)」と表現することができます。
しかし、今度は指数部となる「-3」の表現に困ってしまいます。
そこで、指数部には必ず「127」を加算することで、この問題を解決しています。
これで、「-127」であっても、「-127 + 127 = 0」となり、表現が容易になります。
この「127」を加算することをバイアスといい、「127」自体のことをバイアス値といいます。
すなわち、「E = 4 + 127 = 131 = 10000011」となります。
③M：数値の確定
②で作った「1.1001101 × 10＾4」の「1.1001101」の少数部分「1001101」が仮数部です。
一の位の「1」は不要です。
だって、必ず「1.…」になるようにするのだから。
必要のない情報は省きましょう。
まだ、仮数部は未完成です。
仮数部は23bitになるようにしなければなりません。
ですが、作った情報は「1001101」と7bitしかありません。
残りの16bitですが…後ろに「0」を16bit付与します。
つまり、「10011010000000000000000」となります。
①～③を全て合わせると
「01000001110011010000000000000000」となります。
アルゴリズムの評価方法として利用される「計算量・O記法」についてです。
(※アルゴリズム：ある問題を解く手順を単純な計算や操作を組み合わせて明確に直したもの)
例えば、「1+2+3」を計算するアルゴリズムがあったとします。
その計算量は、
①「1+2」の計算
②「①の結果+3」の計算
を実行するため「2」となります。
「計算量」には2種類の考え方があります。
⑴最大計算量
⑵平均計算量
上記の例では常に計算量は「2」ですが、アルゴリズムの内容次第でループ回数の情報量等によって大きく変化します。
そのため、アルゴリズムの計算量を一般化するために⑴や⑵の概念が存在します。
「O記法」とは、アルゴリズム計算量を記号「O」を用いて表現する手法です。
「O記法」で表現される計算量は、
そのアルゴリズムの処理時間を要素数 n の関数で表わしています。
そのアルゴリズムの処理時間を要素数 n の関数で表わしています。
一般的に、「O記法」は最悪のケースを想定しています。すなわち、変数nに代入する値は最大値を用います。