Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

A Brief History of Random Numbers

sr.ht

Post reply on HN
Print view View original

21–30 of 55 posts

Re: A Brief History of Random Numbers

#21

Post by whyever »

nemo1618 wrote: post #17

Pseudo- random! A new programmer reading this article would come away with the impression that, if they need random numbers, they should use xorshift or PCG, when in reality they should be calling getentropy(), or, if a syscall is too expensive, using a CSPRNG (e.g. ChaCha or BLAKE3) seeded with getentropy(). We now have RNGs that are both secure and really, really fast -- multiple GB/s fast -- so there are very few…

The linked text is from a Rust library for generating random numbers where predictability is acceptable, i.e. it does not concern itself with cryptographic security.

The more popular library rand usese ChaCha and getentropy as you described.

Re: A Brief History of Random Numbers

#22

Post by whyever »

rgmerk wrote: post #11

What this comes down to is that you just can't arbitrarily choose a random number and hope that it meets your needs. You have to understand what properties you actually care about and choose a (P)RNG that has those properties.

Nowadays, you can just choose a CSPRNG and be done with it. There are not many use cases where you might prefer a simpler PRNG.

Re: A Brief History of Random Numbers

#23

Post by dumpsterdiver »

rgmerk wrote: post #11

What this comes down to is that you just can't arbitrarily choose a random number and hope that it meets your needs. You have to understand what properties you actually care about and choose a (P)RNG that has those properties.

It's sounds like what you're saying is that any truly random property would prove vexing to those who would prefer properties that only appear random, but in fact are reliably less random.

Perhaps this is because true randomness doesn't always appear to be random enough. I would argue that this property is what makes it real. Sometimes true randomness might be six dice all showing the face of six.

Re: A Brief History of Random Numbers

#24

Post by pixelesque »

whyever wrote: post #22
rgmerk wrote: post #11

What this comes down to is that you just can't arbitrarily choose a random number and hope that it meets your needs. You have to understand what properties you actually care about and choose a (P)RNG that has those properties.

Nowadays, you can just choose a CSPRNG and be done with it. There are not many use cases where you might prefer a simpler PRNG.

Are CSPRNGs as fast as general high-performance (and non-secure) PRNGs like MT, PGC or Xoroshiro256+?

For many use cases in statistics / sampling / monte carlo simulations, you often need millions/billions of well-distributed random numbers with very low generation overhead.

Even things like game AIs care about performance with regards to the RNGs they use.

Re: A Brief History of Random Numbers

#25

Post by espadrine »

pixelesque wrote: post #24
whyever wrote: post #22

Earlier quoted context omitted.

Nowadays, you can just choose a CSPRNG and be done with it. There are not many use cases where you might prefer a simpler PRNG.

Are CSPRNGs as fast as general high-performance (and non-secure) PRNGs like MT, PGC or Xoroshiro256+? For many use cases in statistics / sampling / monte carlo simulations, you often need millions/billions of well-distributed random numbers with very low generation overhead. Even things like game AIs care about performance with regards to the RNGs they use.

Not all of them, but ChaCha8 (which many renowned cryptographers consider secure[0]) is in the same ballpark as the most common ones[1].

(A few notes on the second link: I wouldn’t recommend xoshiro256+x8 since it is very weak statistically, same for xoshiro256 IMO. Also, disclaimer, I wrote SHISHUA.)

[0]: https://eprint.iacr.org/2019/1492.pdf

[1]: https://github.com/espadrine/shishua#comparison

Re: A Brief History of Random Numbers

#26

Post by camel-cdr »

A history of PRNGs without mentioning George Marsaglia is heresy.

Also, PCG didn't stop the development. Nowadays, modern PRNGs explore the usage of chaotic PRNGs (without a fixed period), which are often faster than non-chaotic ones. Notable examples are the Romu family [0] of PRNGs and sfc [1], and tylov's sfc derivative [2].

Another thing that would be nice to mention is that we went full circle, the good old middle square method already used by von Neumann, has been found to work very well if you scale it up and add a weyl sequence. [3]

Edit: And how could I forget, there has also been a lot of effort in using SIMD, e.g. by SHISHUA. [4]

Another thing to consider is how to efficiently distribute the generated numbers in a given distribution. I'm not aware of any recent improvements in that regard, other then some approximations that have probably been reinvented a bunch of times.

[0] https://www.romu-random.org/

[1] https://numpy.org/devdocs/reference/random/bit_generators/sf...

[2] https://github.com/tylov/STC/blob/master/docs/crandom_api.md

[3] https://arxiv.org/abs/1704.00358

[4] https://espadrine.github.io/blog/posts/shishua-the-fastest-p...

Edit: I had a few names mixed up

Re: A Brief History of Random Numbers

#28

Post by denton-scratch »

nemo1618 wrote: post #17

Pseudo- random! A new programmer reading this article would come away with the impression that, if they need random numbers, they should use xorshift or PCG, when in reality they should be calling getentropy(), or, if a syscall is too expensive, using a CSPRNG (e.g. ChaCha or BLAKE3) seeded with getentropy(). We now have RNGs that are both secure and really, really fast -- multiple GB/s fast -- so there are very few…

> when in reality they should be calling getentropy()

A new programmer shouldn't be meddling in cryptography, so they probably don't need either cryptographically-secure pseudo-random numbers nor true random numbers. True random numbers are tricky.

Re: A Brief History of Random Numbers

#29

Post by kqr »

spiffytech wrote: post #7

It amused me that my college statistics textbook had an appendix of random numbers in the back of the book. Just a long list of numbers generated at random and then immortalized on the same medium as ancient texts like the Dead Sea Scrolls. I guess that's the best we had for students before the widespread adoption of computers?

My joke is that the random numbers is the most informative section of the book -- because it is, in the Shannon sense! But not in the colloquial sense, of course.

Re: A Brief History of Random Numbers

#30

Post by camel-cdr »

espadrine wrote: post #25
pixelesque wrote: post #24

Earlier quoted context omitted.

Are CSPRNGs as fast as general high-performance (and non-secure) PRNGs like MT, PGC or Xoroshiro256+? For many use cases in statistics / sampling / monte carlo simulations, you often need millions/billions of well-distributed random numbers with very low generation overhead. Even things like game AIs care about performance with regards to the RNGs they use.

Not all of them, but ChaCha8 (which many renowned cryptographers consider secure[0]) is in the same ballpark as the most common ones[1]. (A few notes on the second link: I wouldn’t recommend xoshiro256+x8 since it is very weak statistically, same for xoshiro256 IMO. Also, disclaimer, I wrote SHISHUA.) [0]: https://eprint.iacr.org/2019/1492.pdf [1]: https://github.com/espadrine/shishua#comparison

Wasn't xoshiro256+ mostly weak in the lower bits, and recommended to use to generate floating point numbers?

I suppose that this is probably indicative of a more fundamental weakness, but for reference the upper bits should be way higher quality that the Messene Twister (As that one fails PractRand while the upper bits of xoshiro256+ don't IIRC)

Post reply on HN