Re:Billions of Random Numbers in a Blink of an Eye
by dragandj on Wednesday July 03, 2019 @05:14AM
(#20342801)
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.
Re:Billions of Random Numbers in a Blink of an Eye
by tptacek on Tuesday July 02, 2019 @05:27PM
(#20339562)
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.
Re:Billions of Random Numbers in a Blink of an Eye
by FabHK on Tuesday July 02, 2019 @05:57PM
(#20339740)
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.)
Re:Billions of Random Numbers in a Blink of an Eye
by petschge on Tuesday July 02, 2019 @07:55PM
(#20340445)
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.
Re:Billions of Random Numbers in a Blink of an Eye
by tgsovlerkhgsel on Wednesday July 03, 2019 @03:10AM
(#20342258)
> 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.
Re:Billions of Random Numbers in a Blink of an Eye
by wolf550e on Wednesday July 03, 2019 @01:42PM
(#20346614)
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).
Re:Billions of Random Numbers in a Blink of an Eye
by FabHK on Wednesday July 03, 2019 @10:04AM
(#20344343)
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.
Re:Billions of Random Numbers in a Blink of an Eye
by tgsovlerkhgsel on Sunday July 07, 2019 @03:58PM
(#20377416)
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.
Re:Billions of Random Numbers in a Blink of an Eye
by tptacek on Tuesday July 02, 2019 @06:05PM
(#20339809)
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.
Re:Billions of Random Numbers in a Blink of an Eye
by FabHK on Tuesday July 02, 2019 @06:30PM
(#20339979)
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.
Re:Billions of Random Numbers in a Blink of an Eye
by FabHK on Tuesday July 02, 2019 @06:01PM
(#20339765)
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.
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 :)"
Re:Billions of Random Numbers in a Blink of an Eye
by nimih on Wednesday July 03, 2019 @12:49AM
(#20341662)
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.
Re:Billions of Random Numbers in a Blink of an Eye
by zaarn on Wednesday July 03, 2019 @05:26AM
(#20342847)
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.
Re:Billions of Random Numbers in a Blink of an Eye
by thisguy47 on Wednesday July 03, 2019 @01:11PM
(#20346303)
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!
Re:Billions of Random Numbers in a Blink of an Eye
by bfuller on Tuesday July 02, 2019 @09:27PM
(#20340844)
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.
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
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.
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.)
[1] https://en.wikipedia.org/wiki/Low-discrepancy_sequence [2] https://blog.demofox.org/2017/05/29/when-random-numbers-are-...
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
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.
[1] http://www.pcg-random.org/posts/bounded-rands.html
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.
[1]: http://michaelbrundage.com/note/2005/01/05/random-number-gen...
[2]: https://software.intel.com/en-us/node/590411
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...
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 :)"
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...
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)
I get results about 100x slower those of the article's CPU benchmark when using numpy on a 2019 MBP:
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.You might want to try this one:
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.For any conceivable application, you just need 256 bits of entropy and a good CSPRNG. https://blog.cr.yp.to/20170723-random.html