Billions of Random Numbers in a Blink of an Eye | Hacker News Reader

Billions of Random Numbers in a Blink of an Eye

dragan.rocks

89 pointstosh24 comments

Open articleView on HN

Maybe also worth checking out are two books that I'm writing right now where this is used and explained in more detail:

https://aiprobook.com

Deep Learning for Programmers at https://aiprobook.com/deep-learning-for-programmers/

Numerical Linear Algebra for Programmers at https://aiprobook.com/numerical-linear-algebra-for-programme...

Everything uses open source software:

https://github.com/uncomplicate

All the best with making it work for you - but for me that pricing strategy would seem to make for a very expensive book.

If I could sell a million copies, I would be gladly selling them for $1 each. However, since these are unique books for specialists, the potential audience is more limited, which unfortunately requires that they cost a bit more.

Just for what it's worth: it's not that cryptography needs difficult-to-generate "true" random numbers, but rather that it needs a particular kind of pseudorandomness. The best mental model to have of crypto-randomness is that it's seeded from events unpredictable enough to be effectively secret; a typical CSPRNG is, in fact, essentially a stream cipher that uses "entropy" (again, those unpredictable events) as its key.

Once you've got it seeded, you can get random numbers from your system's platform CSPRNG plenty fast, and CSPRNGs make, for most applications, a reasonable default RNG.

1. Agreed that CSPRNG are fast enough for most purposes, and should be the default PRNG basically everywhere.

2. The magic ingredients of a CSPRNG are not only the "secret entropy" for seeding, but also the property that given a sequence of its outputs, it's sufficiently hard to predict the next output (this implies that it won't fail the usual statistical tests - every CSPRNG is a PRNG, but not vice versa: for example, with 624 outputs of the Mersenne Twister, you can predict all subsequent ones.)

This next-bit test property was sort of implied (by saying "stream cipher"), but I wanted to spell it out, as it's good to have in one's mental model.

3. For some purposes (such as Monte Carlo simulations), a non-CSPRNG makes sense, as they're still faster. (But given the asymmetric payoffs of a mistake, default should be CSPRNG.)

What you're saying in (2) is essentially the same thing as saying "a typical CSPRNG is a stream cipher keyed by entropy", except that people seem to have a really hard time reasoning about what "predictability of the next bit" means, and not so hard of a time reasoning about what the keystream of a stream cipher does.

Might depend on your background. For a cryptographer, that property is an obvious consequence of being a stream cipher's keystream. For a Monte Carlo guy, it's not obvious, but close to miraculous.

And what everyone needs to know is that it doesn't hold for many (non-CS) PRNG, as apparently poker site operators have found out to their chagrin.

Actually you can make use of non-randomness in Monte Carlo simulations to get better results. There is various names for this, but the one I like best is "low discrepancy series". Have a look at [1] or [2] for a quick intro. These are sometimes also called quasi-random (or sub-random), but I find that a bit too close to pseudo-random.

[1] https://en.wikipedia.org/wiki/Low-discrepancy_sequence [2] https://blog.demofox.org/2017/05/29/when-random-numbers-are-...

> a non-CSPRNG makes sense, as they're still faster

Nowadays with highly optimized and often hardware-accelerated crypto, I honestly doubt it matters.

Using "openssl rand", I can generate randomness 2x as fast as with a naive

  while (1) { r = rand(); fwrite(&r, 4, 1, stdout); }

compiled with -O2. If I replace "openssl rand" with "openssl enc -aes-128-ctr < /dev/zero", I get randomness 4 times faster again, i.e. 8 times as fast as with the naive approach using rand(), hundreds of megabytes on a single core.

And I don't have to worry about the properties of the PRNG.

Yes, good point. As O'Neill pointed out in a blog post last year on "Efficiently Generating a Number in a Range" [1], the impact of choosing a faster PRNG is smaller than the impact of choosing a good algorithm to generate an integer in a range. There'll be very few applications where choosing a faster PRNG has any significant impact.

[1] http://www.pcg-random.org/posts/bounded-rands.html

Not "hundreds of megabytes on a single core", 5 GB per second on a single core on a i7-6700HQ. Use `openssl speed -evp aes-128-ctr`, look at right-most column of 16kb blocks (like TLS record layer).

Fair, but rand() is kinda trashy, and the overwhelming part of that cost is fwrite anyway.

A large part of the cost being "not random number generation" is part of the point - speed of random number generation generally doesn't matter compared to the speed of what you do with the numbers, and optimizing other things, e.g. how to get the bits converted to random numbers usable by an application, are much more important than quickly generating the random bits.

I was curious what PRNG was being used and it was a bit deep in the post, but it appears to be Philox [1] or ARS5 [2].

[1]: http://michaelbrundage.com/note/2005/01/05/random-number-gen...

[2]: https://software.intel.com/en-us/node/590411

Yes, both part of John Salmon, D. E. Shaw et al.'s Random123 suite. I am actually surprised that they're so fast, I'd have thought that PCG or the xoroshiro family is faster. But then, none of them are CSPRNG.

https://www.deshawresearch.com/resources_random123.html

http://www.thesalmons.org/john/random123/releases/1.00/docs/...

http://www.thesalmons.org/john/random123/papers/random123sc1...

And when I look at the home page

https://neanderthal.uncomplicate.org/

I saw first: "implemented in Clojure" and didn't understand how it's "100x faster than optimized pure Java".

But reading further it's clear:

"Does not try to poorly reinvent the wheel. Respects decades of BLAS and LAPACK standardization. Does the number crunching part with native BLAS and/or GPU, but provides a tiny Clojure layer for sanity. Win-win :)"

I was surprised, but I guess everything is working near optimally.

1 Billion 32 bit numbers in 347 ms is 23 G Bytes/s. In 40ms is 200 G Bytes/s. DDR4 is 26 G Bytes per second. And Nvidia GPUs do indeed have over 200 G Bytes/s: https://www.microway.com/knowledge-center-articles/compariso...

Am I missing something? With numpy on my 2017 Macbook Pro, I can generate 1B random, normally distributed numbers on a CPU in ~1.3 microseconds.

In [3]: %timeit np.random.normal(1000000000)

1.3 µs ± 26.2 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)

Edit: and 2.5e17 in ~7.95 microseconds

In [5]: %timeit np.random.normal((500000000, 500000000))

7.95 µs ± 90.7 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)

You might be misremembering the numpy.random api, since you appear to only be generating one or two random numbers in your tests.

I get results about 100x slower those of the article's CPU benchmark when using numpy on a 2019 MBP:

  python -m timeit -s 'import numpy as np; x = np.zeros(1000000)' -u msec 'np.random.normal(x)'
  10 loops, best of 5: 30.9 msec per loop

edit: I'm no python wizard myself, so I'm perfectly willing to believe that there's a better way to generate a random array in numpy than what I'm doing.

I don't think that is measured correctly: A CPU at 5GHz would take 0.2ns per cycle, how is it supposed to generate 1 billion (!) numbers in only 100x the time? Even if you had 64c/128t threadrippers in a dualsocket and this workload perfectly distributed, you'd only get within 100'000x the time of a single cycle. There's still a factor of 10'000 left.

You might want to try this one:

  np.random.normal(size=1000000000)

For size=1000 I get on my machine about 36 ns per number (total 36 µsecs). You probably measured for size=1 but a normal of 1 billion, not 1 billion numbers at a normal of 1.

Ah yes, thanks everyone for pointing out my mistake, I am not using the `size` parameter, so this is really only generating a single random number. My mistake!

Unrelated by I'll ask anyway: Does anyone know of a way to get high bandwidth quantum random numbers for cheap? I am using ANU's service but its not enough to scale, and it seems quantum random numbers are sort of expensive to produce.

Why, exactly do you need “quantum random numbers”?

For any conceivable application, you just need 256 bits of entropy and a good CSPRNG. https://blog.cr.yp.to/20170723-random.html

but can i use it to mine bitcoin?

Reply on news.ycombinator.com