fixedpoint.jp




2014/08/02

0と1の間に(浮動小数点)数がいくつあるか

「0と1の間に実数がいくつあるか」という問いを数学で扱う場合、[0, 1]という閉区間の濃度は実数濃度と等しいため、連続体仮説が関係します。

一方、この問いを浮動小数点数として正確に表せる範囲で考えると、もちろん有限個しかありません。では実際に何個あるでしょうか?

具体的には、「IEEE 754の倍精度浮動小数点数(double)の binary 形式で正確に表せる数で、0以上でかつ1以下のものがいくつあるか」を数えることにします。

見通しをよくするため、double での表現は以下のどれか1つに分類されることに注意してください。

まず第一に、自明に zero を1個としてカウントします。

次に、非正規化数は全て1より小さいです。このため、正の非正規化数は全てカウントすることになります。

NaN および Infinity は当然カウントしません。

最後に「それ以外」の場合ですが、ここに1が含まれているのでこれをまずカウントします。あとは「それ以外」に1より小さい正の数がどれだけあるかを数えればいいことになります。「それ以外」では、fraction が何であれ significant の暗黙の最上位のビットが1です。このビットが exponent が掛かることにより小数点以下にシフトされていれば、その正の数は1より小さくなります。さてここでは double で考えているので、exponent の bias は1023です。つまり biased exponent が1022以下であれば、その正の数は1より小さくなります。逆に、biased exponent が1022より大きければ、その正の数は1以上となります。

以上をまとめると、

が小計となります。53は fraction のビット数です。結局、合計で1+(2^53-1)+(1+1022*(2^53)) = 1+1023*(2^53) = 9214364837600034817個というのが答えになります。

補足として、問いを「IEEE 754 binary 形式の double で0以上1以下になる表現がいくつあるか」と変えると、negative zero を考慮して上の合計に1を足す必要がありそうです。

#permalink

Archives

2014: Apr / Mar / Feb / Jan

2013: Dec / Nov / Oct / Sep / Aug / Jun / May / Apr / Mar

2012: Nov / Oct / Sep / Jul / Jun / May / Mar / Feb / Jan

2011: Dec / Nov / Oct / Sep / Jul / Jun / Apr / Mar / Feb / Jan

2010: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2009: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2008: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2007: Dec / Nov / Oct / Sep / Aug / Jul / Jun / May / Apr / Mar / Feb / Jan

2006: Dec / Nov / Oct / Sep


© 2006-2014 fixedpoint.jp