TE
科技回声
首页24小时热榜最新最佳问答展示工作
GitHubTwitter
首页

科技回声

基于 Next.js 构建的科技新闻平台,提供全球科技新闻和讨论内容。

GitHubTwitter

首页

首页最新最佳问答展示工作

资源链接

HackerNews API原版 HackerNewsNext.js

© 2025 科技回声. 版权所有。

Perfect Random Floating-Point Numbers

110 点作者 pclmulqdq4 天前

13 条评论

camel-cdr1 天前
I&#x27;ve written an algorithm that generates a uniform random float in the range [a,b] that can produce every representable floating-point value with a probability proportional to the covered real number range*: <a href="https:&#x2F;&#x2F;github.com&#x2F;camel-cdr&#x2F;cauldron&#x2F;blob&#x2F;main&#x2F;cauldron&#x2F;random.h#L1464">https:&#x2F;&#x2F;github.com&#x2F;camel-cdr&#x2F;cauldron&#x2F;blob&#x2F;main&#x2F;cauldron&#x2F;ran...</a><p>* Well, almost. I messed up the probability around subnormals slightly and haven&#x27;t gotten around to fixing it yet.<p>Still, the algorithm it self should works for all other values and it was measurably more accurate than the regular algorithm.<p>In terms of performance it is 10x slower compared to the regular implementation of `(randu32(x)&gt;&gt;8)*(1.0f&#x2F;(1&lt;&lt;24))` on my Zen1 desktop.
评论 #43919807 未加载
FabHK1 天前
There&#x27;s another approach for doing this: generate a random number between 1 and 2 (they all have the same exponent) and then subtract 1 (that&#x27;s the default implementation in Julia [0]). But I think it also just gives you 2^53 different numbers.<p>So, between .5 and 1 you miss out on every second representable number, between 0.25 and .5 you miss out on 3&#x2F;4 of them, and so on.<p>I guess for many cases that&#x27;s good enough, but the article seems like a nice improvement.<p>ETA: Lemire has some thoughts on this [1] and links to what might be a prior solution [2]. Vigna (of xoroshiro fame) writes about it at the bottom of [3] and also links to [2]. So, presumably the implementation described in the article is faster? (&quot;There have been some past attempts to fix these flaws, but none that avoid a huge performance penalty while doing so.&quot;<p>EDIT2: BTW, one of the things I love about HN (well, the world, really) is that there are people that care deeply that we can uniformly sample floats between 0 and 1 correctly, and all of them, and do it faster.<p>[0] see <a href="https:&#x2F;&#x2F;github.com&#x2F;JuliaLang&#x2F;julia&#x2F;blob&#x2F;master&#x2F;stdlib&#x2F;Random&#x2F;src&#x2F;generation.jl">https:&#x2F;&#x2F;github.com&#x2F;JuliaLang&#x2F;julia&#x2F;blob&#x2F;master&#x2F;stdlib&#x2F;Random...</a><p><pre><code> rand(r::AbstractRNG, ::SamplerTrivial{CloseOpen01_64}) = rand(r, CloseOpen12()) - 1.0 </code></pre> [1] <a href="https:&#x2F;&#x2F;lemire.me&#x2F;blog&#x2F;2017&#x2F;02&#x2F;28&#x2F;how-many-floating-point-numbers-are-in-the-interval-01&#x2F;" rel="nofollow">https:&#x2F;&#x2F;lemire.me&#x2F;blog&#x2F;2017&#x2F;02&#x2F;28&#x2F;how-many-floating-point-nu...</a><p>[2] <a href="https:&#x2F;&#x2F;mumble.net&#x2F;~campbell&#x2F;2014&#x2F;04&#x2F;28&#x2F;uniform-random-float" rel="nofollow">https:&#x2F;&#x2F;mumble.net&#x2F;~campbell&#x2F;2014&#x2F;04&#x2F;28&#x2F;uniform-random-float</a><p><a href="https:&#x2F;&#x2F;mumble.net&#x2F;~campbell&#x2F;2014&#x2F;04&#x2F;28&#x2F;random_real.c" rel="nofollow">https:&#x2F;&#x2F;mumble.net&#x2F;~campbell&#x2F;2014&#x2F;04&#x2F;28&#x2F;random_real.c</a><p>[3] <a href="https:&#x2F;&#x2F;prng.di.unimi.it" rel="nofollow">https:&#x2F;&#x2F;prng.di.unimi.it</a>
评论 #43918821 未加载
评论 #43916453 未加载
评论 #43916563 未加载
pixelpoet1 天前
Some good references on this which IMO should have been mentioned in the article:<p><a href="https:&#x2F;&#x2F;pharr.org&#x2F;matt&#x2F;blog&#x2F;2022&#x2F;03&#x2F;05&#x2F;sampling-fp-unit-interval" rel="nofollow">https:&#x2F;&#x2F;pharr.org&#x2F;matt&#x2F;blog&#x2F;2022&#x2F;03&#x2F;05&#x2F;sampling-fp-unit-inte...</a><p><a href="https:&#x2F;&#x2F;marc-b-reynolds.github.io&#x2F;distribution&#x2F;2017&#x2F;01&#x2F;17&#x2F;DenseFloat.html" rel="nofollow">https:&#x2F;&#x2F;marc-b-reynolds.github.io&#x2F;distribution&#x2F;2017&#x2F;01&#x2F;17&#x2F;De...</a>
possiblywrong1 天前
&gt; Second, the least significant bits that come from this generator are biased.<p>I don&#x27;t think this is true; I&#x27;m guessing that the author borrowed this observation from one of the various other articles linked in this thread, that address the situation where we draw a 64-bit random unsigned integer and divide by `1&lt;&lt;64`, instead of drawing 53 bits and dividing by `1&lt;&lt;53`. The former does introduce a bias, but the latter doesn&#x27;t (but does still limit the fraction of representable values).
评论 #43919810 未加载
tialaramex1 天前
&gt; For unbiased random floating-point numbers, generate floating-point numbers with probabilities given by drawing a real number and then rounding to floating point.<p>Immediately there are alarms going off in my mind. Your machine definitely can&#x27;t pick real numbers, Almost All of them are non-computable. So you definitely can&#x27;t be doing that, which means you should write down what you&#x27;ve decided to actually do because it&#x27;s not that.<p>What you actually want isn&#x27;t the reals at all, you want a binary fraction (since all your f64s are in fact binary fractions) between 0 and 1, and so you just need to take random bits until you find a one bit (the top bit of your fraction), counting all the zeroes to decide the exponent, then you need 52 more bits for your mantissa.<p>I&#x27;m sure there&#x27;s a faster way to get the same results, but unlike the article&#x27;s imagined &quot;drawing a real number&quot; this is actually something we can realize, since it doesn&#x27;t involve non-computable numbers.<p>Edited: You need <i>52</i> more bits, earlier this comment said 51 but the one bit you&#x27;ve already seen is implied in the floating point type, so we need 52 more, any or all of which might be zero.
评论 #43918152 未加载
评论 #43924551 未加载
badmintonbaseba1 天前
Generalizing this to arbitrary intervals, not just [0, 1) looks tricky. Just scaling and shifting a perfect uniform result from [0, 1) doesn&#x27;t result in a perfect random floating-point number.
评论 #43918111 未加载
kevmo3141 天前
Cool observation! Despite knowing both about how floating points work and how random number generation works, this never occurred to me.<p>I do wish the solution were a bit simpler though. Could this be upstreamed into the language&#x27;s API? <a href="https:&#x2F;&#x2F;cs.opensource.google&#x2F;go&#x2F;go&#x2F;+&#x2F;refs&#x2F;tags&#x2F;go1.24.3:src&#x2F;math&#x2F;rand&#x2F;rand.go;l=189" rel="nofollow">https:&#x2F;&#x2F;cs.opensource.google&#x2F;go&#x2F;go&#x2F;+&#x2F;refs&#x2F;tags&#x2F;go1.24.3:src&#x2F;...</a>
评论 #43917543 未加载
hedora1 天前
I thought this was going to go further down the path that the Die Hard Battery of random number tests started:<p><a href="https:&#x2F;&#x2F;www.jstatsoft.org&#x2F;index.php&#x2F;jss&#x2F;article&#x2F;view&#x2F;v007i03&#x2F;892" rel="nofollow">https:&#x2F;&#x2F;www.jstatsoft.org&#x2F;index.php&#x2F;jss&#x2F;article&#x2F;view&#x2F;v007i03...</a><p>(Dieharder is probably a better suite to use at this point, but that paper is approachable.)
评论 #43919671 未加载
FabHK大约 22 小时前
So, fun fact:<p>Between 0 and 1, you have about a quarter of all floating point numbers (and then a quarter &gt; 1, a quarter &lt; -1, and a quarter between -1 and 0).<p>Between 1 and 2, you have about 0.024% of all floating point numbers (for double precision, a factor of around 1023).
gitroom1 天前
Yeah I&#x27;ve messed with this and always end up wishing the simple ways were actually good enough. The bit where floats aren&#x27;t really evenly spaced just gets annoying. Still, I kinda get the itch to cover all cases. Respect.
sfpotter1 天前
Probably relevant: <a href="https:&#x2F;&#x2F;prng.di.unimi.it&#x2F;" rel="nofollow">https:&#x2F;&#x2F;prng.di.unimi.it&#x2F;</a><p>I use the PRNGs here for my own needs and they work great... at least as far as I can tell. :-)
评论 #43919651 未加载
lutusp1 天前
&quot;Perfect Random [sic] Floating-Point Numbers&quot; ???<p>I had hoped that, somewhere in the article, the author would say, &quot;In this article, the term &#x27;random&#x27; is shorthand for &#x27;pseudorandom&#x27;.&quot; But no.<p>Programming students might read the article and come away with the idea that a deterministic algorithm can generate random numbers.<p>This is like the sometimes-heard claim that &quot;Our new error-detecting algorithm discovers whether a submitted program contains errors that might make it stop.&quot; Same problem -- wrong as written, but no qualifiers.
评论 #43918440 未加载
mahemm1 天前
Why not just read 64 bits off &#x2F;dev&#x2F;urandom and be done with it? All this additional complexity doesn&#x27;t actually buy any &quot;extra&quot; randomness over this approach, and I&#x27;m skeptical that it improves speed either.
评论 #43917528 未加载
评论 #43917534 未加载