固定小数点演算について

固定小数点演算について
前回では、「ブレゼンハム」アルゴリズムによって直線を引きましたが、整数による直線の描画方法はもう一つあります。
それは「固定小数点演算」を使った方法です。

今回は、まずは「固定小数点演算」がどういうものであるかを説明します。
基本
固定小数点演算」は、浮動小数点数値を整数で擬似的に表現し、演算を高速化するために使われます。
画像処理プログラムなどでは、高速化の手段としてよく使われるので、覚えておいた方が良いです。

固定小数点数では、整数の「上位ビットを整数部分」「下位ビットを小数部分」として扱います。

固定小数点数として扱う整数の全ビット数が 32bit の場合、小数部分を 12bit として扱うなら、
「下位 12bit が小数部分、上位の残り 20bit ビットが整数部分」となります。

固定小数点数で気をつけなければならないのは、このビット数のバランスです。

小数部分のビット数が多いほど小数部分の精度が上がることになりますが、その分、整数部分の値の範囲が縮まることになるので、小数部分を大きくしすぎると、計算時に整数部分が桁溢れする場合があります。

固定小数点数を使う場合は、桁溢れと、整数部分の値がどれだけの範囲の値を表現できるかに気を付ける必要があります。
固定小数点数
浮動小数点数値を固定小数点数に変換するには、以下のようにします。
(小数部分を 8bit とした場合)

int fval = (int)round(1.5 * (1<<8));  //0x180
round() は小数点丸め。
固定小数点数値
浮動小数点の値「1.5」を 8bit の固定少数点数に変換すると、「0x180」となります。
下位 8bit 「0x80」が小数部分の値で、これが「0.5」に相当する値です。
上位ビット「0x1」が整数部分です。これはそのまま「1」ですね。
整数部分を求める
固定小数点数から整数部分を取得する場合は、固定小数点数を小数ビット数分だけ右シフトすることで求められます。
また、符号ありの整数を使っていれば、負の値も扱えます。

n = fval >> 8
シフト演算
固定小数点数では、「1 << 小数ビット数」の値は、浮動小数点で表現するところの「1.0」となります。

1.0 = 1 << bits」ということは、「0.5 = (1 << bits) / 2」となります。
ここで、「整数を 2 で割る = 整数を右に1つシフトする」なので、
0.5」の値は「(1 << bits) >> 1」または「1 << (bits - 1)」として表現することもできます。

このように、整数ならばシフト演算が使えるので、固定小数点数においても、2 の n 乗で乗算または割り算をする場合は、シフト演算を使えば高速に処理できます。

fval = 2<<8; //0x0200 = 2.0
fval >>= 1;  //0x0100 = 1.0
fval >>= 1;  //0x0080 = 0.5
固定小数点演算
固定小数点を演算する場合。
加算/減算
固定小数点数同士を加算/減算する場合は、普通の整数と同じように加算/減算するだけで OK です。

3.5 + 1.25 = 4.75
3.5 - 1.25 = 2.25
fval1 = (int)round(3.5 * (1<<8));  //0x380
fval2 = (int)round(1.25 * (1<<8)); //0x140

n1 = fval1 + fval2; //0x4c0 = 4.75
n2 = fval1 - fval2; //0x240 = 2.25
乗算 (固定小数点数×普通の整数)
「固定小数点数×3」など、固定小数点数と普通の整数値を乗算する場合は、そのまま整数値を掛けます。

1.5 * 5 = 7.5
fval = (int)round(1.5 * (1<<8)); //0x180
n = fval * 5; //0x780 = 7.5

x2 や x4 など、n の2乗の値を掛ける場合は、左シフトでも構いません。
乗算 (固定小数点数×固定小数点数)
固定小数点数同士を乗算する場合は、乗算後に、小数ビット数分を右シフトします。

3.5 * 1.5 = 5.2
fval1 = (int)round(3.5 * (1<<8)); //0x380
fval2 = (int)round(1.5 * (1<<8)); //0x180

n = (fval1 * fval2) >> 8; //0x540 = 5.2

乗算した後になぜ右シフトが必要かというと、fval1 * fval2 した時の値を見ればわかります。
fval1 * fval2 は「0x380 * 0x180 = 0x54000」となり、求めたい値「5.2 = 0x540」の値からは掛け離れています。
これを小数ビット数分右にシフトすると、ちょうど 0x540 になります。

固定小数点数×普通の整数」が普通の乗算で良いのに対して、「固定小数点数×固定小数点数」は小数部分の桁分を余計に掛けていることになるので、その分元に戻す必要があります。
桁溢れに注意
また、この乗算の場合は桁溢れに注意しなければなりません。

fval1 * fval2 の乗算結果を見ればわかるように、固定小数点数同士を掛けると、演算結果の値が大きくなります。
そもそも、固定小数点数自体が整数としては大きな値になるので、その数値同士を掛けることになるのですから、当然の結果と言えます。

64bit OS なら 64bit 整数を扱えるので、それほど気にしなくても良いかもしれませんが、32bit OS では小数点ビット数を少なめにしないと、桁溢れの可能性が高くなります。
除算
除算も乗算と同じような感じです。
固定小数点数÷普通の整数
普通の整数で割る場合は、そのまま割り算します。
÷2、÷4 などの場合は右シフトで高速化できます。

n = fval / 5;
n = fval >> 2;
固定小数点数÷固定小数点数
固定小数点数同士で割り算する場合は、乗算の時とは逆に、小数ビット分を右にシフトしてから、割り算を行います。

12.5 / 2.5 = 5.0
fval1 = (int)round(12.5 * (1<<8)); //0xC80
fval2 = (int)round(2.5 * (1<<8));  //0x280

n = (fval1 << 8) / fval2;  //0x500

なぜ先に右シフトが必要かというと、今度は乗算の時とは逆で、固定小数点数で割るには桁が足りないからです。

除算に関しても、乗算と同じように桁溢れの可能性がありますので、注意してください。