2進数小数の10進表現末尾の数字

IEEE 7544 浮動小数点データ (Python の float 型 / JavaScript の Number 型)の厳密値を表示すると、2進数での小数値 $0.\cdots 1$ が10進数では最下位付近が特徴的な数になります。その特徴を下位 N 桁で列挙します。

<p class="codepen" data-height="360" data-default-tab="result" data-slug-hash="VYZEeEL" data-pen-title="2進数小数の10進表現末尾の数字" data-user="ikiuo" style="height: 360px; box-sizing: border-box; display: flex; align-items: center; justify-content: center; border: 2px solid; margin: 1em 0; padding: 1em;">
  <span>See the Pen <a href="https://codepen.io/ikiuo/pen/VYZEeEL">
  2進数小数の10進表現末尾の数字</a> by Ikiuo (<a href="https://codepen.io/ikiuo">@ikiuo</a>)
  on <a href="https://codepen.io">CodePen</a>.</span>
</p>
<script async src="https://cpwebassets.codepen.io/assets/embed/ei.js"></script>


```HTML:
<!DOCTYPE html>
<html lang="ja">
  <head>
    <meta charset="utf-8">
    <title>2進数小数の10進表現末尾の数字</title>
    <style>
     body {
         width: 20em;
         margin: auto;
     }
     td {
         text-align: center;
     }
    </style>
  </head>
  <body>
    <table>
      <tr><td>2進数小数の10進表現末尾の数字</td></tr>
      <tr><td>
        <label for="tagCol">桁数</label>
        <input id="tagCol" name="tagCol" type="range"
               min="1" max="11" step="1" value="4" oninput="onUpdate()">
        <span id="tagColText"></span>
      </td></tr>
      <tr><td id="tagList"></td></tr>
    </table>
  </body>

  <script>

   function onUpdate() {
       const N = Number(tagCol.value); tagColText.innerText = N;
       const P = '0'.repeat(tagCol.max);
       const R = Math.pow(5, N);
       const V = [...Array(1 << (N - 1))].map(
           (_, i) => '0. ⋯ ' + (P + (R * ((i << 1) + 1))).slice(-N));
       tagList.innerText = V.reduce((p, v) => p + (v + '\n'), '');
   }

   window.onload = onUpdate;

  </script>
</html>
```

```python:sample.py
#!/usr/bin/env python3

import argparse
import sys

parser = argparse.ArgumentParser()
parser.add_argument('digits', metavar='N', type=int, help='桁数')
args = parser.parse_args()

N = args.digits
if N <= 0:
    print(f'桁数 = {N}: 1以上を指定してください')
    sys.exit(2)

S = pow(5, N)
valfmt = f'0.⋯ {{:0{N}}}'
for n in range(1 << (N - 1)):
    print(valfmt.format(S * (1 + (n << 1))))
```

```console:実行結果
% python3 sample.py 5
0.⋯ 03125
0.⋯ 09375
0.⋯ 15625
0.⋯ 21875
0.⋯ 28125
0.⋯ 34375
0.⋯ 40625
0.⋯ 46875
0.⋯ 53125
0.⋯ 59375
0.⋯ 65625
0.⋯ 71875
0.⋯ 78125
0.⋯ 84375
0.⋯ 90625
0.⋯ 96875
```

# 算出方法

2進小数と10進数の関係は、小数点以下のビット並びの整数を

```math:
B = b_1 b_2 b_3 \cdots b_{n-1} 1_n
```

とすると

```math:
N = \frac{ B }{ 2^n } = \frac{ D = B \times 5^n }{ 10^n = 2^n \times 5^n }
```

だから、小数点以下の桁数は2進数も10進数も同じで、$D$ は $5^n$ の倍数です。末尾を下$w$桁とすると、2進数の最下位桁は $1$ だから、出てくる数値は1ビット分減って最大で $2^{w-1}$ 個です。

$2^{-n}$ の値は

```math:
2^{-n} = \frac{ 1 }{ 2^n } = \frac{ 5^n }{ 2^n \times 5^n } = \frac{ 5^n }{ 10^n }
```

なので $n$ を $1$ から順に

| $n$ | $2^{-n}$ |
|--:|:--|
|  1 | $0.5$ |
|  2 | $0.25$ |
|  3 | $0.125$ |
|  4 | $0.0625$ |
|  5 | $0.03125$ |
|  6 | $0.015625$ |
|  7 | $0.0078125$ |
|  8 | $0.00390625$ |
|  9 | $0.001953125$ |
| 10 | $0.0009765625$ |
| 11 | $0.00048828125$ |
| 12 | $0.000244140625$ |
| 13 | $0.0001220703125$ |
| 14 | $0.00006103515625$ |
| 15 | $0.000030517578125$ |
| 16 | $0.0000152587890625$ |
| $\vdots$ | $\vdots$ |

で、下$w$桁 $T$ では同じ値が繰り返し出現します。その間隔は

| 間隔 | $w$ | 下$w$桁 $T$ | $2^{-n}$ 出現行 |
|--:|--:|--:|:--|
| 1 | 1 | $5$ | 1, 2, 3, 4, ... |
| 1 | 2 | $25$ | 2, 3, 4, 5, ... |
| 2 | 3 | $125$ <br> $625$ | 3, 5, 7, 9, ... <br> 4, 6, 8, 10, ... |
| 4 | 4 | $0625$ <br> $3125$ <br> $5625$ <br> $8125$ | 4, 8, 12, 16, ... <br> 5, 9, 13, 17, ... <br> 6, 10, 14, 18, ... <br> 7, 11, 15, 19, ... |
| 8 | 5 | $03125$ <br> $15625$ <br> $78125$ <br> $90625$ <br> $53125$ <br> $65625$ <br> $28125$ <br> $40625$ | 5, 13, 21, 29 ... <br> 6, 14, 22, 30, ... <br> 7, 15, 23, 31, ... <br> 8, 16, 24, 32, ... <br> 9, 17, 25, 33, ... <br> 10, 18, 26, 34, ... <br> 11, 19, 27, 35, ... <br> 12, 20, 28, 36, ... |

$ k = 2^{\max(0, w-2)} $ 毎です。$w = 1$ の下一桁は $5$ なので省略して $w \ge 2$ とし

```math:
k = 2^{max(0, w-2)} \to k = 2^{w-2}
```

に記述を変更します。間隔には次の性質があります。

```math:
\begin{eqnarray}
5^w \times 5^k & \equiv & 5^w \pmod{ 10^w = 2^w \times 5^w } \\
5^k & \equiv & 1 \pmod{ 2^w } \\
\left( 1 + 4 \right)^k & \equiv & 1 \pmod{ 2^w } \\
1 + \sum_{x=1}^{k}{ \frac{ 4^x k! }{ x! (k - x)! } } & \equiv & 1 \pmod{ 2^w } \\
\sum_{x=1}^{k}{ \frac{ 2^{2(x-1)+w} \cdot (2^{w-2} - 1)! }{ x! \left( 2^{w-2} - x \right)! } } & \equiv & 0 \pmod{ 2^w } \\
\end{eqnarray}
```

間隔内の値 $T$ は、$s$ を $\\{ 0,1,2,\cdots,k-1 \\}$ とすると

```math:
\begin{eqnarray}
T & \equiv & 5^s \times 5^w \pmod{ 10^w = 2^w \times 5^w } \\
1 + 2t & \equiv & 5^s \pmod{ 2^w } \\
\end{eqnarray}
```

と表せて、${1+2t}$ は奇数で $B$ の一部になります。以上により、求める値は

- $n$ を $w$ に置換して考えられる
- $D$ は $10^w$ 未満の $B \times 5^w$
- $B$ は $2^w$ 未満の奇数 (2進数の最下位桁は $1$)

なので、$5^w$ の奇数倍を $2^{w-1}$ 個並べるだけです。