fixed-point numberとは何だったのか

この記事は某校のC++の３つ目の課題の課題文で出現した「fixed-point number」についての考察です。この課題も1,2日で終わると聞いたことがありましたが、2ヶ月ほどかかりました。小数点をあまり分かってないと[このような事故](https://www-users.cse.umn.edu/~arnold/disasters/Patriot-dharan-skeel-siam.pdf)で人を⚪︎してしまう可能性があるので小数を使ったコードは怖いなと思います。

今回は固定小数点数型を作る課題です。

こちらは昔の42Tokyo生のprintfの課題の記事です。当時はfloatの実装がありました。

[浮動小数点型をprintfを使わずに出力する方法](https:/qiita.com/daitai-daidai/items/44632da01d4b0a18c33e)

fixed-point numberという型を作ってください。という指示に従い、fixed-point numberを調べてみると、[ウィキの記事](https://ja.wikipedia.org/wiki/%E5%9B%BA%E5%AE%9A%E5%B0%8F%E6%95%B0%E7%82%B9%E6%95%B0)が見つかりました。
「fixed-point number」というのは日本語で「固定小数点数」らしいことがわかり、Q表記(Qフォーマット)を使い、固定小数点数型の種類を表せることがわかります。
例えば、Q12とは少数部分のビット数が12の固定小数点数をいいます。

そして課題文にはFractional bitsは8で固定せよ、とあるので、Q8表記の固定小数点数をint型でprivateなメンバー変数に格納されたクラスを定義すればよさそうだと思いました。

## 問題文の解釈について
詳細は諸事情で割愛しますが、同校の初期の課題に「regular file」という単語を含む問題文がありました。ここで、「regular file」を直訳すると「普通のファイル」となります。しかし、この「普通のファイル」という単語は日常用語として解釈してはいけないと思っています。この単語は実際には、コンピュータサイエンスの分野における専門用語の「regular file」のことを意味しています。その用語の立ち位置を正しく感じ取れるかは地味に大事な気がしています。

## IEEE754単精度浮動小数点数型の復習
固定小数点数型の前にそもそもIEEE754単精度浮動小数点数型を知らなかったので調べました。知ってる人は飛ばしてください。
課題文に与えられたリンクとググったりしてまとめたメモを載せます。あくまでメモなので、[参考資料](https://www.cprogramming.com/tutorial/floating_point/understanding_floating_point_representation.html)などを読みながら知識の再確認に使ってください。

- ビジュアライザー
  - https://bartaz.github.io/ieee754-visualization/
- 基本構造(32bit)
    - seeeeeeeemmmmmmmmmmmmmmmmmmmmmmmmmm
    - 符号bit(1bit)、指数部(8bit)、仮数部(23bit)の順
- 実は仮数部は工夫されている
  - "1.mの表現"が使われている
    - 仮数を1.mの表記にし、"m"の部分(小数点以下)を保存
    - データ節約のため
    - Q. これでは「0.0」は表現できなさそう？
    - A. できる。指数部、仮数部が全てゼロの時に0とする
      - 符号bitを使い「+0.0」と「-0.0」の2つの0を定義
    - Q.「1.0」はどう表現する
      - 「+0.0」のビットパターンと被ってしまう
- A. 実は指数部も工夫されている
  - "eeeeeeee - 127表現"が使われている
    - 指数に127を足した値を保存
  - 「1.0」を表現することができる
    - 「1.0」の指数部は127のbit表現(=11111111)
  - Q. 今度は「+0.0」がゼロに近いとても近い数ε(1.0 * 2^(-127))と同じbit表現になってしまう
  - A. この数εは「+0.0」として扱う
    - ゼロにとても小さい数εよりも「+0.0」の有用性が高そうだから
- 実は...
- mが非ゼロで指数部のbit配列が(00000000)の時：非正規化数(subnormal number)
  - 1.mの表現は使わず、最上位bitまでを指数部とみなし拡張して扱う
  - 精度を捨ててできるだけ小さい数を表現したい
  - （非正規化数）の正の最小値2^(-126-23)の精度は1bit
- 正の範囲でｈbit表現と実際の数字の大きさの対応関係が綺麗に保たれている
- 上記の例外について
  - 特別なbit表現がある
  - 「infinity」２つ、「NaN」２つ
  - 指数部が全て1
    - 仮数部が全て0
      - 「infinity」の２つの表現（正と負）
    - その他
      - 「NaN」の２つの表現（正と負）
- 指数部の"eeeeeeee - 127表現"の再考
  - ナイーブな表現での範囲：0~255
    - 2の補数表現での範囲：-128~127
      - bit配列(10000000)は指数部-128を意味する→ゼロにとても近い数
      - ...
      - bit配列(00000000)は指数部0を意味する→この集合内で特別に仮数部が全て0を「+0.0」と定義すると「1.0」の定義と被る
      - ...
      - bit配列(01111111)は指数部127を意味する→とても大きい数
     - "eeeeee - 127表現"での範囲：-127~128
        - bit配列(00000000)は指数部-127を意味する→この中で特別に「+0.0」を定義するとゼロにとても近い数と被りそう
        - ...
        - bit配列(01111111)は指数部0を意味する→「1.0」の定義を含む
        - ...
        - bit配列(11111111)は指数部128を意味する→この集合内で特別に「infinity」「NaN」を定義

## 誤差に関するメモ
課題に直接関係ないので飛ばして大丈夫です。
浮動小数点数型といえば誤差なのでついでに少し知識をつけておきたくなりました。丸め誤差や情報落ち、桁落ちはよく見かけるので、自分が馴染みのなかったものを掲載しました。
- ulp(unit in the last place, 計算機イプシロン) 
  - 同じ指数部を持つ2つの数字の最小幅
  - 同じ指数部を持つ2つの数字の最大値と最小値の差を考える
  - これは指数部に依存。この値を2^23分割する時の値
  - 1~2の範囲においては1(=2-1)を2^23分割するので2^(-23)
  - ulpが1を超えてulpが2になるのは16777216(2^24)~2^25の範囲で、2^24以上ではfloatは正確に表現できないとわかる
- ufp(unit in the first place)
  - 同じ指数部を持つ2つの数字の最大幅
- ulpとufp
  - ufpが最上位bitでulpが最下位bitを意味していてネーミングが面白い
  - ufp = 2^23 * ulp

badlandsについて
- ある関数のbadlandsという考え方
  - エラーの定義
    - `error(x,r) = |x−r| / ulp(fl(r))`
    - `r`は真の値, `x`は誤差が含まれうる調べたい値, `fl(x)`は実数x→float型を返す関数
  - エラーは浮動小数点の演算ではなく関数のそのものに付随する性質
  - エラーが4以上になる引数の範囲→badlandsと定義
  - badlandsでは元の関数の代わりに別関数を代用する
    - e.x. `log(x/y)`のbadlandsでは`log(x/y+1)`を使用

## 固定小数点数型に変換
あとは簡単です。
共有体を初めて使いました。
英語ネイティブな学生に聞いたらmentissaをメンティサと言っていました。
```cpp
int float2fixed(const float float_number)
{
	union
	{
		float f;
		unsigned int i;
	} num;

	num.f = float_number;

	unsigned int sign = (num.i >> 31 & 1);
	unsigned int exponent = ((num.i >> 23) & 0xFF);
	unsigned int mantissa = ((num.i >> (23 - _FRACTIONBITS)) & 0xFF) | ((num.i >> (23 - _FRACTIONBITS - 1)) & 1);// 四捨五入

	int result = 0;
	result |= sign << (sizeof(int) * 8 - 1);
	result |= exponent << _FRACTIONBITS;
	result |= mantissa;

	return result;
}
```
- しかしこれだと実は非正規化数も変換されてしまいます
  - 指数部が全て0の時は特別扱いするのがよさそうです
- infinityやNaNも数字に変換されてしまいます
  - 指数部が全て1の時は特別扱いするのがよさそうです

## おわりに
- IEEE754単精度浮動小数点数型と固定小数点数型の基本を学べました

## 参考資料
- [Understanding and Using Floating Point Numbers by Jeff Bezanson](https://www.cprogramming.com/tutorial/floating_point/understanding_floating_point.html)
- [Floating point number representation](https://www.cprogramming.com/tutorial/floating_point/understanding_floating_point_representation.html) 一番参考になった
- [IEEE 754 浮動小数点入門](https://ushiostarfish.hatenablog.com/entry/2019/08/12/210023)