IEEE 7544 浮動小数点データ (Python の float 型 / JavaScript の Number 型)の厳密値を表示すると、2進数での小数値 $0.\cdots 1$ が10進数では最下位付近が特徴的な数になります。その特徴を下位 N 桁で列挙します。
See the Pen 2進数小数の10進表現末尾の数字 by Ikiuo (@ikiuo) on CodePen.
<!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>
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))))
実行結果
% 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進数の関係は、小数点以下のビット並びの整数を
B = b_1 b_2 b_3 \cdots b_{n-1} 1_n
とすると
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}$ の値は
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$ $625$ |
3, 5, 7, 9, ... 4, 6, 8, 10, ... |
| 4 | 4 | $0625$ $3125$ $5625$ $8125$ |
4, 8, 12, 16, ... 5, 9, 13, 17, ... 6, 10, 14, 18, ... 7, 11, 15, 19, ... |
| 8 | 5 | $03125$ $15625$ $78125$ $90625$ $53125$ $65625$ $28125$ $40625$ |
5, 13, 21, 29 ... 6, 14, 22, 30, ... 7, 15, 23, 31, ... 8, 16, 24, 32, ... 9, 17, 25, 33, ... 10, 18, 26, 34, ... 11, 19, 27, 35, ... 12, 20, 28, 36, ... |
$ k = 2^{\max(0, w-2)} $ 毎です。$w = 1$ の下一桁は $5$ なので省略して $w \ge 2$ とし
k = 2^{max(0, w-2)} \to k = 2^{w-2}
に記述を変更します。間隔には次の性質があります。
\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 \}$ とすると
\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}$ 個並べるだけです。