2進数で循環小数してみる - インゲージ開発者ブログ

こんにちは、masm11 です。

時々数学で遊んでみたくなりませんか? というわけで、今回は数学と戯れてみたいと思います。循環小数です。とは言え、ただ実証してみるだけですので、気楽にお付き合いいただければと思います。

循環小数とは

まず、循環小数とは何でしょうか?

$0.123123123\cdots$

見たまんま、循環している小数のことですね。

おそらく「 $\cdots$ 」という書き方が曖昧で数学者の気に食わないのでしょう、これは以下のように書きます。

$0.\dot{1}2\dot{3}$

1 と 3 の上に点を付けて、「以下、1～3 の部分の繰り返しですよー」という意味です。正確です。

では、これを分数で表現してみます。

実は、

$\displaystyle 0.\dot{1}2\dot{3} = \frac{123}{999}$

なのです。

もちろん、 $0.123123\cdots$ の場合に限りません。

$\displaystyle 0.\dot{6}78\dot{9} = \frac{6789}{9999}$

です。循環している部分を分子に書き、同じ桁数だけ 9 を分母に並べるのです。

ここまでは、もしかすると、「あ、高校の時にやった」という方もいらっしゃるかもしれません。

0.1 を2進数で正確に表現する

「そんなことできるの?w」いえいえ、上記のように、循環小数を正確に表現できるのですから、できるかもしれません。

ここからは、10進数か2進数かを数値の右下に書きます。 $10_{10}$ は $10$ のことで、 $100_2$ は $4$ のことです。

では行きましょう。

$\displaystyle 0.1 _ {10} = \frac{1 _ {10}}{10 _ {10}} = \frac{1 _ {2}}{1010 _ {2}}$

ここまでは分数で2進数表記にしただけです。

10進数で分母を 999 の形にすればいいということは、2進数でも 111 の形にすればいいのかもしれません(*1)。

$\displaystyle = \frac{1_2}{101_2}\frac{1_2}{10_2}$

$101_2$ は $5 _ {10}$ ですね。これを $111\cdots_2$ の形にするにはどうすればいいでしょうか? 分母分子に何かを掛けましょう。 $5 _ {10}$ , $10 _ {10}$ , $15 _ {10}$ , ... あ、 $15 _ {10}$ が $1111_2$ ですね。では $3 _ {10}$ を掛けることにします。

$\displaystyle = \frac{11_2}{1111_2}\frac{1_2}{10_2} = \frac{0011_2}{1111_2}\frac{1_2}{10_2}$

最後の $=$ は、 $0$ を補っただけです。

さて、仮説 (*1) が正しいなら、

$\displaystyle = 0.\dot{0}01\dot{1}_2\frac{1_2}{10_2}$

です。最後の分数は、 $2 _ {10}$ で割ってるだけなので、

$\displaystyle = 0.0\dot{0}01\dot{1}_2$

となります。

さて、この値が10進数でいくつなのか、Ruby でコードを書いて確認してみました。

sig = 0.25
sum = 0

32.times do |i|
  mod = i % 4
  sum += sig if [2, 3].include? mod
  puts sum

  sig /= 2
end

2進数の一桁ずつ、1 なら sum に加えて、0 なら加えない、それだけのコードです。結果は以下のようになりました。

0
0
0.0625
0.09375
0.09375
0.09375
0.09765625
0.099609375
0.099609375
0.099609375
0.099853515625
0.0999755859375
0.0999755859375
0.0999755859375
0.0999908447265625
0.09999847412109375
0.09999847412109375
0.09999847412109375
0.09999942779541016
0.09999990463256836
0.09999990463256836
0.09999990463256836
0.09999996423721313
0.09999999403953552
0.09999999403953552
0.09999999403953552
0.09999999776482582
0.09999999962747097
0.09999999962747097
0.09999999962747097
0.09999999986030161
0.09999999997671694

$0.1 _ {10}$ に限りなく近くなっていますね。

0.1 の場合の実証としてはここまでです。

$\displaystyle 0.0\dot{0}01\dot{1}_2$

これで、おそらく正確に表現できたのでは、と思います。

一休み

2進数の小数が出てきたので、ついでに説明してみますと、

$\displaystyle 0.0\dot{0}01\dot{1}_2 = 1.1001100\cdots _ 2 \times 2 _ {10} ^{-4 _ {10}}$

と、小数点より上が 1 になるように調整して、小数点より上を取り除き、 $1001100\cdots _ 2$ を浮動小数点の仮数部、 $-4 _ {10}$ を指数部と呼びます (ただし、wikipedia によると、他にも方式があるようです)。

0.01 の場合

さて、0.1 を2進数で表現した結果はご存知の方も多かったのではないでしょうか。もう一つくらいやってみましょうか。0.01 です。

$\displaystyle 0.01_{10} = \frac{1 _ {10}}{100 _ {10}} = \frac{1 _ {16}}{64 _ {16}} = \frac{1_2}{1100100_2} = \frac{1_2}{11001_2}\frac{1_2}{100_2}$

0.1 の場合と同様にここまで変形しました。 $11001_2$ は $25 _ {10}$ です。これを何倍かして $2 ^N-1$ にしたいのです。

32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536

ここまでは頭に思い浮かべながら、違うことが想像できました。16bit 世代にはここらへんが限界です。この先は覚えていません。素直に Ruby の力を借りましょう。

n = 2

loop do
  break if (n - 1) % 25 == 0
  n *= 2
end

puts n
puts (n - 1) / 25

出てきた答えは、

1048576
41943

これは、1M (メガ) ですね。これだけは最近ようやく覚えました。 $2 ^{20}$ です。そして、上の出力結果の通り、 $2 ^{20}-1$ は $25 \times 41943$ だそうです。

では、分母分子を $41943 _ {10}$ 倍しましょう。 $41943 _ {10} = 1010001111010111_2$ なので、

$\begin{aligned} \frac{1_2}{11001_2}\frac{1_2}{100_2} &= \frac{1010001111010111_2}{11111111111111111111_2}\frac{1_2}{100_2} \\ &= \frac{00001010001111010111_2}{11111111111111111111_2}\frac{1_2}{100_2} \\ &= 0.\dot{0}000101000111101011\dot{1}_2\frac{1_2}{100_2} \\ &= 0.00\dot{0}000101000111101011\dot{1}_2 \end{aligned}$

これを 0.1 の場合と同様に Ruby のプログラムで検証します。

0
0
0
0
0.0078125
0.0078125
0.009765625
0.009765625
0.009765625
0.009765625
0.0098876953125
0.00994873046875
0.009979248046875
0.0099945068359375
0.0099945068359375
0.009998321533203125
0.009998321533203125
0.009999275207519531
0.009999752044677734
0.009999990463256836
0.009999990463256836
0.009999990463256836
0.009999990463256836
0.009999990463256836
0.009999997913837433
0.009999997913837433
0.009999999776482582
0.009999999776482582
0.009999999776482582
0.009999999776482582
0.009999999892897904
0.009999999951105565
0.009999999980209395
0.00999999999476131
0.00999999999476131
0.00999999999839929
0.00999999999839929
0.009999999999308784
0.009999999999763531
0.009999999999990905
0.009999999999990905
0.009999999999990905
0.009999999999990905
0.009999999999990905
0.00999999999999801
0.00999999999999801
0.009999999999999787
0.009999999999999787

綺麗に 0.01 に近づいてますね!