16 ms·
A Brief History of Random Numbers
- ggm 4y agoThese are mostly about PRNG, not true random sources. brief funny story. My dad built the 5th computer in the UK, ICCE [0] and one of the tests they wanted to run was statistical analysis over random number fields. They approached the General Post Office (GPO) which had an RNG called "ernie" [1] which ran the postal investment bond lottery. This is a true RNG, based on radio device avalanche diode behaviour (actually, neon tubes). It was dressed up as a computer but it was basically a detector device and A-to-D converter dressed up to look like one. They asked for a million truly random numbers to run some tests over. Interestingly, ERNIE was made by somebody who worked on Colossus at Bletchley. The GPO refused to share a feed of numbers: They were concerned the team would discover some predictable event in the number field, and either destroy the post office bond scheme by revealing it, or use it to make millions. [0] https://en.wikipedia.org/wiki/Imperial_College_Computing_Engine https://en.wikipedia.org/wiki/Imperial_College_Computing_Eng... [1] https://en.wikipedia.org/wiki/Premium_Bond#ERNIE https://en.wikipedia.org/wiki/Premium_Bond#ERNIE
- defrost 4y agoInterestingly, ERNIE was made by TWO somebodies who who worked on Colossus at Bletchley. From your ERNIE link: The designers were Tommy Flowers and Harry Fensom and it derives from Colossus, one of the world's first digital computers ... https://en.wikipedia.org/wiki/Tommy_Flowers https://en.wikipedia.org/wiki/Tommy_Flowers https://en.wikipedia.org/wiki/Harry_Fensom https://en.wikipedia.org/wiki/Harry_Fensom ( I travelled to Canada from Australia in the 1980s and interviewed William Tutte about codebreaking and the war, I missed out on an opportnity to talk to Tommy Flowers the following year and didn't return to the UK until after his death )
- ggm 4y agoLike a lot of early machines, ICCE was made in part from ex-GPO relays. (ie, it was electromechanical.) Valves were more expensive and relays were flooding the market post-war. Guess which WW2 activity used a very large number of relays, and was made by the GPO (who used relays heavily in telephony), and was subsequently discontinued by the GPO at wars end as things to do with encoding and decoding scaled back thus flooding the electronics market in the UK with relays... Tommy Thomas (head of the ERCC in edinburgh where my dad wound up and I therefore lived) worked at Manchester on the Mark 1. He never talked about it and I never asked, subsequently. We both wound up in Australia at the CSIRO, where Radiophysics had been started by people in the radar space, and that bled into their interest in Computing. it's a small world. He was the head of the IT division and I was a lowly researcher, our paths didn't cross much. I wish I'd talked to him more, about this stuff and computer history.
- defrost 4y agoSeems like a click baiting kind of question that I'd surely Bombe. I ended up mainly doing geophysical field work with a lot of aquisition, processing, and interpretation coding work .. but I dabbled in symbolic computer algebra systems (in Australia) for a while and loitered a little in technical history of the borderline classified - I interviewed "for the record" Leonard Beadell, Jack Wong Sue, Mark Oliphant, people associated with the Mungalalu Truscott Airbase, etc. I seem to recall a fair bit was done here with early over the horizon radar work but I didn't go far in that direction ending up more in radiometrics and resource | energy tracking.
- ggm 4y agoIn the pop-sci space, Robert Buderi's book on radar is really about a lot more than Radar, and covers off on the field really well including Taffy Bowen's work in Australia and the contribution to radioastronomy. (you probably know it)
- danielodievich 4y ago"that I'd surely Bombe" <- nice bletchley park/enigma pun. Bravo!
- defrost 4y agoNot bad, but I regretted not adding more [Pp]olish . . . https://en.wikipedia.org/wiki/Bomba_(cryptography) https://en.wikipedia.org/wiki/Bomba_(cryptography)
- layman51 4y agoWow! Also, I think [0] is the first Wikipedia I have come across that doesn’t have a lead section at all.
- ggm 4y agos/doesn't/didn't/ but it's probably grossly inadequate.
- DougMerritt 4y agoERNIE sounds kind of fascinating. And somewhat amusing. Going off on a tangent: An oft-neglected issue is that, even when the random source (like avalanched diodes) is actually sufficiently random, any apparatus that captures that randomness for use inherently causes a bias in the observations. Even if everything else is perfect (it usually isn't), in terms of signal processing, any observation window (e.g. a finite length of time of measurement) is an aperture which ends up getting convolved with the signal source being observed. It sometimes helps to convert the skew into white noise with a "whitening" post-pass algorithm. Using real life randomness is still a good thing to do, of course, it's just that are always real world issues with anything and everything.
- spiffytech 4y agoIt 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?
- waldrews 4y agoBack in the day, uniform random variates weren't that hard to come by, but if you wanted to simulate some normals, unless you wanted to do double table lookup plus maybe some interpolation, those tables were as convenient as it got.
- artisanscribble 4y agoYou say that, but generating uniform variates was itself a whole trick. Famously RAND put a lot of effort into creating a ton of them and publishing them: https://en.wikipedia.org/wiki/A_Million_Random_Digits_with_100,000_Normal_Deviates https://en.wikipedia.org/wiki/A_Million_Random_Digits_with_1...
- NegativeK 4y agoThe RAND corporation published a book filled with just random digits. https://www.rand.org/pubs/monograph_reports/MR1418.html https://www.rand.org/pubs/monograph_reports/MR1418.html
- layer8 4y agoHilariously, there’s an Errata available.
- chunkyks 4y agoI revisited this in 2020 and found some additional things, separate from that errata. All my code is available here: https://github.com/RANDCorporation/milliondigits https://github.com/RANDCorporation/milliondigits And there's a news article about it here: https://www.wsj.com/articles/rand-million-random-digits-numbers-book-error-11600893049 https://www.wsj.com/articles/rand-million-random-digits-numb...
- vlmutolo 4y agoThere’s some interesting discussion regarding xoshiro vs PCG. https://news.ycombinator.com/item?id=24785572 https://news.ycombinator.com/item?id=24785572
- rgmerk 4y agoWhat 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.
- whyever 4y agoNowadays, you can just choose a CSPRNG and be done with it. There are not many use cases where you might prefer a simpler PRNG.
- pixelesque 4y agoAre 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.
- NohatCoder 4y agoDepends on what you compare, but with modern cryptography instructions you can now generate a few bytes per cycle, so billions of numbers is not an issue.
- espadrine 4y agoNot 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 https://eprint.iacr.org/2019/1492.pdf [1]: https://github.com/espadrine/shishua#comparison https://github.com/espadrine/shishua#comparison
- camel-cdr 4y agoWasn'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)
- nemo1618 4y agoPseudo-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 circumstances where a PRNG is truly necessary.
- whyever 4y agoThe 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.
- denton-scratch 4y ago> 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.
- nemo1618 4y agoMy whole point is that cryptographically-secure should be the default, as there are many scenarios where a PRNG leads to a security vulnerability where a CSPRNG would not. It is precisely new programmers who should be using CSPRNGs for everything, because they are the least well-equipped to know when strong entropy is necessary! We should (almost) never be asking "Do you really need a CSPRNG?" but rather "Do you really need a PRNG?"
- denton-scratch 4y ago> because they are the least well-equipped to know when strong entropy is necessary! Yuh. I'm not sure what "strong entropy" means, in this context; entropy's usually reported as some number of bits of entropy. So perhaps "a lot of entropy" is clearer. At any rate, by default a (CS)PRNG doesn't have any entropy that isn't present in its seed. According to some, at least, that entropy is diminished every time you read from the RNG, so it depletes to nothing after a finite number of reads. I've finally come to the conclusion that entropy, whatever that means, is orthogonal to RNGs. Instead, RNGs should be classified by their unpredictability. A CSPRNG is one with high unpredictability. And I've given up on trying to build a DIY HWRNG. It was a misbegotten project.
- camel-cdr 4y agoA 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/ https://www.romu-random.org/ [1] https://numpy.org/devdocs/reference/random/bit_generators/sfc64.html https://numpy.org/devdocs/reference/random/bit_generators/sf... [2] https://github.com/tylov/STC/blob/master/docs/crandom_api.md https://github.com/tylov/STC/blob/master/docs/crandom_api.md [3] https://arxiv.org/abs/1704.00358 https://arxiv.org/abs/1704.00358 [4] https://espadrine.github.io/blog/posts/shishua-the-fastest-prng-in-the-world.html https://espadrine.github.io/blog/posts/shishua-the-fastest-p... Edit: I had a few names mixed up
- denton-scratch 4y agoWhy's he going on about slide-rules?
- thanatropism 4y agoStylistic flair.
- h2odragon 4y agogood shorthand for "the time before computers, when math was done with meat and dinosaurs roamed the earth"
- denton-scratch 4y agoOh, OK. I couldn't see what approximate calculations using logarithms had to do with random integers. Also, I learned to use a slide-rule in the sixties; I 've never touched one again until I inherited an antique, a few years ago. Nobody was using slide-rules in the seventies, surely.
- faceloss 4y ago[dead]
- makeworld 4y agoLearn more about PCG here: https://www.pcg-random.org/ https://www.pcg-random.org/
- beyondCritics 4y agoWow, reading this am suddenly noticing that hiding the latency in system code can be much more simpler than i thought it is. Say i have a function X f(X u); on which i want to iterate occasionally to get in turn f(u0),f(f(u0)),... The "smart" way to do this, is X u=f(u0); //Initialize once ... X smart_f() { X w = u; u = f(w); return w; // This line is not stalled by the previous one, // hence a super scalar processor might be able to hide the latency of calculation f(w) } I doubt any compiler will be able to figure this out, and surely not if f has side effects.