問題CPP12000の解答例と解説 C++ Lv.3
実数の2進数表記(40分)
0 ≤ x < 1 の実数の小数点部分を32bitで表現することを考える前に、2bitで表現したらどうなるかを考えてみよう。
2bitというのは、00、01、10、11の22=4つの値のことだよ。そうすると、4つの値はそれぞれ以下のようになるよ。
4つの実数にしか割り当てられないから、その間の実数は表現できないんだ。例えば、0.1は正確に表現できないんだ。それで問題は32bitで表現するので、0 ≤ x < 1 の実数を232=4,294,967,296個の実数に等分割分して割り当てていけばいいんだ。
それで、この2進数の文字列の作り方だけど、一番左のbitは、0.5 以上なら 1 になるんだ。
それで0.5以上の場合は、そのまた半分の0.75以上なら2つ目のbitが1になり、0.5 <= x 0.75 なら 0になるんだ。0.5未満の場合も、そのまた半分の0.25以上か未満で、左から2つ目のbitが1か0になるよ。
こういう風に、0.5、0.25、0.125、… よりも大きいか小さいかで32回調べていくプログラムを書くと、以下のようになるよ。(ちょっと言葉だけで上手に伝えるのが難しいけど、プログラムを読んでもらった方がわかるかもしれない。)
2bitというのは、00、01、10、11の22=4つの値のことだよ。そうすると、4つの値はそれぞれ以下のようになるよ。
0 | 00 |
0.25 | 01 |
0.5 | 10 |
0.75 | 11 |
4つの実数にしか割り当てられないから、その間の実数は表現できないんだ。例えば、0.1は正確に表現できないんだ。それで問題は32bitで表現するので、0 ≤ x < 1 の実数を232=4,294,967,296個の実数に等分割分して割り当てていけばいいんだ。
0 | 00000000000000000000000000000000 |
1*2-32 | 00000000000000000000000000000001 |
2*2-32 | 00000000000000000000000000000010 |
3*2-32 | 00000000000000000000000000000011 |
... | ... |
(232-4)*2-32 | 11111111111111111111111111111100 |
(232-3)*2-32 | 11111111111111111111111111111101 |
(232-2)*2-32 | 11111111111111111111111111111110 |
(232-1)*2-32 | 11111111111111111111111111111111 |
それで、この2進数の文字列の作り方だけど、一番左のbitは、0.5 以上なら 1 になるんだ。
それで0.5以上の場合は、そのまた半分の0.75以上なら2つ目のbitが1になり、0.5 <= x 0.75 なら 0になるんだ。0.5未満の場合も、そのまた半分の0.25以上か未満で、左から2つ目のbitが1か0になるよ。
こういう風に、0.5、0.25、0.125、… よりも大きいか小さいかで32回調べていくプログラムを書くと、以下のようになるよ。(ちょっと言葉だけで上手に伝えるのが難しいけど、プログラムを読んでもらった方がわかるかもしれない。)
<解答例 1>
F11キーでフルスクリーンモード、Escキーで元に戻ります。
これを数式で表すと、2の-n乗の値を組み合わせで、以下のように表すことができるよ。
この太字のaの部分をつなげると2進数になるよ。例えば 0.5 は、こうだよ。
そして 0.75はこう。
そして 0.25はこう。
実際のfloat型もdouble型も、指数化して値を持つけど、小数点以下の値の持ち方はこれと同じだよ。
float型はサイズは32bitだけど、正負の符号を1bitで、2の何乗か(指数)を8bitで、そして小数点以下を含んだ実数(仮数)を残りの23bitで格納しているんだ。
そうすると、float型は2-23≒0.00000011920=1.1920e-7 刻みで値を持つので、それよりも小さい値は持てないんだ。だから、その値よりも小さな値はみんな丸められてしまうから、誤差が発生するよ。それなので有効桁数というのが出てきて、float型は0.0000001(7桁)の値は正確に持てないから、有効桁数は6桁になるんだ。(実際はもうちょっと複雑で、float型の小数部は24bitとも言えるんだ。そうすると、2-24≒0.0000000596046=5.96046e-8で有効桁数は7桁とも言えるよ。"とも言える"なんて、あいまいな言い方だけど、四捨五入してしまったりするから、ここはあいまいになるんだ。気になる人は教科書やネットで調べてみよう。)
double型の小数部(仮数部)は52bitなので、2-52≒2.220446e-16 刻みで値を保持するから、有効桁数は15桁だよ。ただし、float型のときと同じ理由で53bitを使用していると言えるので、2-53≒1.110223e-16 有効桁数は約16桁とも言えるよ。
実数型(double,float)の整数部分に関しては、ここに問題があるよ。 実数型の範囲
解答例と解説のページはこちらだよ。 解答例と解説
a1*2-1 + a2*2-2 + a3*2-3 + ... + a32*2-32 (an = { 0 or 1 }) |
この太字のaの部分をつなげると2進数になるよ。例えば 0.5 は、こうだよ。
0.5 = | 1*2-1 + 0*2-2 + 0*2-3 + ... + 0*2-32 | = 0.5 + 0 + 0 + ... + 0 |
0.75 = | 1*2-1 + 1*2-2 + 0*2-3 + ... + 0*2-32 | = 0.5 + 0.25 + 0 + ... + 0 |
0.25 = | 0*2-1 + 1*2-2 + 0*2-3 + ... + 0*2-32 | = 0 + 0.25 + 0 + ... + 0 |
実際のfloat型もdouble型も、指数化して値を持つけど、小数点以下の値の持ち方はこれと同じだよ。
float型はサイズは32bitだけど、正負の符号を1bitで、2の何乗か(指数)を8bitで、そして小数点以下を含んだ実数(仮数)を残りの23bitで格納しているんだ。
そうすると、float型は2-23≒0.00000011920=1.1920e-7 刻みで値を持つので、それよりも小さい値は持てないんだ。だから、その値よりも小さな値はみんな丸められてしまうから、誤差が発生するよ。それなので有効桁数というのが出てきて、float型は0.0000001(7桁)の値は正確に持てないから、有効桁数は6桁になるんだ。(実際はもうちょっと複雑で、float型の小数部は24bitとも言えるんだ。そうすると、2-24≒0.0000000596046=5.96046e-8で有効桁数は7桁とも言えるよ。"とも言える"なんて、あいまいな言い方だけど、四捨五入してしまったりするから、ここはあいまいになるんだ。気になる人は教科書やネットで調べてみよう。)
double型の小数部(仮数部)は52bitなので、2-52≒2.220446e-16 刻みで値を保持するから、有効桁数は15桁だよ。ただし、float型のときと同じ理由で53bitを使用していると言えるので、2-53≒1.110223e-16 有効桁数は約16桁とも言えるよ。
実数型(double,float)の整数部分に関しては、ここに問題があるよ。 実数型の範囲
解答例と解説のページはこちらだよ。 解答例と解説
初めての方へ:このページは、このサイトで用意しているプログラミング問題の解答と解説のページです。このサイトではブラウザ上からプログラミングができます。会員登録(無料)して、プログラミングしてみませんか?
新規登録
新規登録