okkyの日記： 浮動小数点表現での一定範囲内の全列挙…だと?! 5
とある場所で見た質問
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
【急募】C/C++で浮動小数点型(float, double, long double)の2数n1, n2があるとき、
1)n1からn2までにある数の個数(数学じゃないので有限個ですね)
2)n1からn2までにある数を全列挙する
方法を募集します
QQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQQ
どうやら本当にやりたいのはこちららしい:
https://teratail.com/questions/28673?sip=n0070000_019&uid=38546
が、本来の目的なんぞ無視して ( w ) 2番の問題「n1からn2までにある数を全列挙する」がなぜあかんかについてだけ述べる。
話を簡単にするために、double に限定しよう。桁数が少ないと現実味がないことが分かりにくいし、桁数が多すぎると説明を書いていてくらくらするから…。
さて。
https://ja.wikipedia.org/wiki/IEEE_754
IEEE754の倍精度というのはこういうフォーマットになっている(1文字1bitだと思いねぇ):
S EEEEEEEEEEE FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
S: 符号(0だとプラス、 1だとマイナス)
E: 指数部11bit 1.0 を表すときにはこれは 1023 という数字になるようバイアスがかかっている(が、それは問題の本質ではないので気にしないように)。
F: 仮数部 52bit。実際には 1.xxxxxxxxxxという表現の x の部分だけが記載されている。これは問題に影響をちょっとだけ与えるので覚えておくように。
ここで。1.0 から 2.0 までの間に何個「数」が表現できるのかについて考えよう。厳密には 1.0 <= x < 2.0 となるような x を考える。
S は 0 だ。これはいい。
1.0 は E が1023で F が全て0 になる。
2.0 は E が1024で F が全て0 になる。
つまり x < 2.0 になる最大の x は
Eが 1023 で、F が全て1になるような、そんな数だ。
なので、x の条件を満たす数は F の部分が 0x0000000000000 (16進数で13桁) から 0xFFFFFFFFFFFFF までの数だ。
総数は 4503599627370496 個だ。だって 0x10000000000000 だからね。
これはどうにか求まる。
問題はこれを全部「列挙する」事だ。
まず、必要な桁数は小数点以下が52桁、その前に "1." という文字が必要だ。
え？なぜわかるかって？
(1/2)^1 = 0.5
(1/2)^2 = 0.25
(1/2)^3 = 0.125…
と、2進数で1桁(1bit)増えるたびに10進数の最後の桁が１つづつ下に下がるんだから当然だよね??
で、改行を LF にするとして 55byte/line。
4503599627370496 * 55 byte がリストの出力サイズだ(テキストの場合だとして)。
話を簡単にするために SSD に書こう。100Mbyte/sec 出るとする。
必要な時間は…
( 4503599627370496 * 55 ) / (100*1024*1024)
= 96709589091.71514687415292328006 sec
= 335.37820306470846987134 year
あぁ、そうだ。EMC が DSSD を発表したんだった。
http://www.emc.com/about/news/press/2016/20160229-03.htm
これなら 100Gbyte/sec 出るぞ。100*1000*1000*1000だけど。
(4503599627370496 * 55) / (100*1000*1000*1000) / (60*60*24)
= 72.42113934845142660541 日。
…
ちなみに必要な容量は ざっと 367Pbyteだ。
元コメが本当に欲しかったものは何なんだろう… (スコア:1)
均等分布した乱数がほしいだけなら、0〜1の均等な実数乱数を欲しい個数だけ得てから変換すれば事足りるような。
十分な精度を持った小数点数を用いれば現実的な確率では重複はないものと期待される(ｷﾘｯ
重複が絶対に許容できない用途、たとえばN個の要素が必ず大小関係を持っていないといけない、のであれば、そのN個の要素について「万一重複した場合に比較に用いる順序値」（これは普通に整数でシャッフル）を予め定めておいて比較すれば良い。
数値だけで完結せねばならず、しかし精度の減少が許容されるならば、途中桁は乱数だけど末尾の数桁だけ絶対に重複しない（シャッフル値で上書き）手法もアリですかね。これなら同じ値には決してならない。
んー (スコア:1)
生成済の乱数を格納するハッシュテーブル(でなくてもいいけど、多分処理速度は一番速い)を用意して、生成済の値が出てきたらそれを捨てて再生成かなぁ。
生成する区間に対して生成すべき乱数の数が十分に少なくて、ハッシュテーブル全体が実メモリに載る程度に小さいのならこれでいいと思う。
# 値が衝突してたらやだっていう要求は、実は本人ではなくえらいさんの意向(≒命令)だったりしてｗ
Re:んー (スコア:1)
やっぱり衝突したら再生成かなぁ・・・。
ちなみに純粋に趣味でして、お仕事ではないです(仕事ではプログラミングしてない)
Re:んー (スコア:1)
[0,1) の区間で生成した一様乱数で衝突を回避出来ても、それを元に生成した(任意区間とかの)乱数は、浮動小数演算の際の丸め誤差の影響で、衝突しない保証は無いですからねぇ。
# 2倍するだけとかなら全単射 [wikipedia.org]なのは自明ですが。
元の乱数云々の方 (スコア:1)
区間によって分布（密度）が一様でないので整数と同じノリで作ると使いにくい階段状の偏りを含んだ乱数列になると思うけどそれはいいのだろうか……。