2進数で有限小数となる10進有理数

10進法で表記した有理数を2進法の小数で表記したときに，有限の桁数で表すことができる有限小数になるための特徴付けを与える．この応用として10進法で表記した有限小数が計算機上で誤差を含む数値かどうかの判定ができる．

例．有理数 $\frac{5}{8}$ と $\frac{1}{10}$ の2進法の小数表記

例えば，10進法で表記した有理数 $\frac{5}{8}$ を2進法の小数で表すと $0.101_{2} = \frac{1}{2} + \frac{0}{2^2} + \frac{1}{2^3}$ となる．ここで，数の右下に 2 を付すと2進法表記を表すことにする．この場合は小数部が 3 桁となり有限の桁で表せられるので有限小数である．
次に，10進法表記の有理数 $\frac{1}{10}$ を2進数小数で表すと $0.00011001100110011..._{2}$ となる（0.1 を二進数に - Wolfram|Alpha）．したがって $\frac{1}{10}$ は2進法の小数で表記したとき有限小数とはならない．

2進数で有限小数となる有理数の特徴づけ

10進法で表記した有理数 $\frac{q}{p}$ が2進法の有限小数となるための必要十分条件は， $p$ が 2 の冪乗となることである．

証明

$\Rightarrow)$ 有理数が2進法の有限小数で $0.a_{1} a_{2} \ldots a_{n} \, (a_i \in \{0, 1\} \, \text{かつ} \, a_n = 1)$ と表せられると仮定する．このとき， $0.a_{1} a_{2} \ldots a_{n} = \frac{a_{1} \cdot 2^{n - 1} + a_{2} \cdot 2^{n - 2} + \cdots + a_{n - 1} \cdot 2 + 1}{2^n}$ となる．分子は $2^n$ より小さく奇数なので有理数となり，また分母は2の冪乗となる．

$\Leftarrow)$ 有理数 $\frac{q}{2^n}$ を考えると， $q$ は有限桁の2進数で表せられるので有限小数となる．❏

＊ $k$ 進法での有限小数の特徴付けがある．例えば10進数の有理数が有限小数となるための必要十分条件は分母が $2^n 5^m$ となること（Decimal representation - Wikipedia）

応用

有理数 $\frac{1}{10}$ の小数 $0.1$ を計算機上で表現しようとすると上で述べたように2進数の有限小数では表せられないので誤差を含む（一般的な浮動小数点数型の場合）．ただし，有限小数でも桁数がその型で収まらない場合は誤差を含む．下に有理数 $\frac{5}{8}$ と $\frac{1}{10}$ を浮動小数点数型で表した結果を載せる．

有理数 5 / 8
float型      ： 0.625000000000000000000000000000 (4 Byte)
double型     ： 0.625000000000000000000000000000 (8 Byte)
long double型： 0.625000000000000000000000000000 (16 Byte)

有理数 1 / 10
float型      ： 0.100000001490116119384765625000 (4 Byte)
double型     ： 0.100000000000000005551115123126 (8 Byte)
long double型： 0.100000000000000000001355252716 (16 Byte)

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

int main() {
    cout << setprecision(30) << setiosflags(ios::fixed);

    cout << "有理数 5 / 8" << endl;
    cout << "float型      ： " << 5.0f / 8.0f
         << " (" << sizeof(5.0f / 8.0f) << " Byte)" << endl;
    cout << "double型     ： " << 5.0 / 8.0
         << " (" << sizeof(5.0 / 8.0) << " Byte)" << endl;
    cout << "long double型： " << 5.0l / 8.0l
         << " (" << sizeof(5.0l / 8.0l) << " Byte)" << endl;

    cout << "\n有理数 1 / 10" << endl;
    cout << "float型      ： " << 0.1f
         << " (" << sizeof(0.1f) << " Byte)" << endl;
    cout << "double型     ： " << 0.1
         << " (" << sizeof(0.1) << " Byte)" << endl;
    cout << "long double型： " << 0.1l
         << " (" << sizeof(0.1l) << " Byte)" << endl;

    return 0;
}

　
0.1 は誤差を含むので下のようなプログラムを書くと無限ループとなり停止しない．

for (double x = 0.0; x != 1.0; x += 0.1)
    cout << x << endl;

実行結果の上位13個を表示

0.00000000000000000000
0.10000000000000000555
0.20000000000000001110
0.30000000000000004441
0.40000000000000002220
0.50000000000000000000
0.59999999999999997780
0.69999999999999995559
0.79999999999999993339
0.89999999999999991118
0.99999999999999988898
1.09999999999999986677
1.19999999999999995559

小数が誤差を含むかの判定方法

10進数の小数 0.625 などが2進法で有限小数とはならずに誤差を含むかどうかの簡潔な判定方法を考える．

小数部が $x$ で $n$ 桁の小数は分数で $\frac{x}{10^n}$ と書けて $\frac{x}{10^n} = \frac{x}{2^n 5^n}$ となる．この分数が2進法で有限小数となるためには分母が2の冪乗となるので， $x$ が $5^n$ で割り切れる必要がある．したがって，判定方法は次の通りである．

10進数の小数の小数部が $x$ でその桁数が $n$ であるとき，その小数が2進法で有限小数となるための必要十分条件は， $x$ が $5^n$ で割り切れることである．

0.625 は小数部が 625 で 3 桁である．625 は $5^3$ で割り切れるので2進法で有限小数となり誤差を含まない
0.1 は小数部が 1 で 1 桁である．1 は $5^1$ で割り切れないので2進法で有限小数とはならずに誤差を含む

追記．float型のビット表現

浮動小数点数型のビット表現を取得するには共用体を使用する．浮動小数点数型と誤差に関しては浮動小数点数型と誤差を参照．
有理数 $\frac{1}{10}$ をfloat型で表現すると $(-1)^0 \times 2^{123 - 127} \times 1.10011001100110011001101$ となった．

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

template<typename T>
string to_bits(T x) {
    string b;
    while (x) {
        b += (char)((x & 1) + '0');
        x >>= 1;
    }
    reverse(b.begin(), b.end());
    b = string(8 * sizeof(x) - b.size(), '0') + b;
    return b;
}

int to_int(const string &b) {
    int x = 0;
    for (auto c : b) {
        x *= 2;
        if (c == '1') x += 1;
    }
    return x;
}

void print_bits(const string &b) {
    cout << "符号部： " << b.front() << endl;
    cout << "指数部： " << b.substr(1, 8)
         << " (" << to_int(b.substr(1, 8)) << ")" << endl;
    cout << "仮数部： " << "1." << b.substr(9, 23) << endl;
}

int main() {
    cout << setprecision(30) << setiosflags(ios::fixed);

    union U {
        float y;
        int x;
    };

    union U u = {0.1f};
    cout << "有理数 1 / 10" << endl;
    cout << "10進数表記： " << u.y << endl;
    cout << "2進数表記 ： " << to_bits(u.x) << endl;
    print_bits(to_bits(u.x));

    return 0;
}

ある型のオブジェクトが格納されているバイト列を別の型のオブジェクトと解釈してアクセスする方法を type punning と呼びます．type punning は C 言語では認められていますが C++ 17 以前では未定義の動作になります．C++ 20 からは std::bit_cast を使用すことによって合法的かつ安全に行えます．
　

追記（2023年10月8日）

C++17 から十六進浮動小数点数リテラルが導入されました。この機能は浮動小数点数リテラルの仮数部を十六進数で表記できるので、上で見てきた十進数から二進数の変換で起こる誤差を生じさせずに記述することができます。
　
　

用語の定義が曖昧なので後で書き直すはず．たぶんみんな知っていて書くことでもないのかなと思いながらもとりあえず書いた．曖昧なまま書いているので指摘してもらえると嬉しいです．

ソースコード上で実数は有限小数でしか書けないけど（四則演算すると循環小数になるものとかあるけど），そのような数でも計算機内部で浮動小数点数として扱おうとすると誤差を含む場合が多いという気持ちが分かるはず（∵ 分母が2の冪乗）．0.1255 を見て「 1255 が $5^4$ で割り切れないから誤差含むよ」と言われたところであまり嬉しくはないかもしれないけど，誤差がいろいろなところで発生するんだなという気持ちが分かるはず（なぜ書いたかのモチベーションが分からなくなってきた）．言いたいことは数値計算ってスゴイなということです．