BBC BASIC implementation of RANDU

[DDRM]

Indeed, many modern processors include a source of true randomness, through the RDRAND instruction (for Intel/AMD), which is at least based on an internal source of entropy (usually thermal, I think), though they then layer a PRNG on top of it for speed, re-seeding it regularly from the true random source. The problem with such an approach is that it's pretty slow - over 1000 clock cycles per call - and it would be much slower still if it used the true random bits all the time, since they take substantial time to be generated. A weakness on some multi-core processors has been shown (they all (used to?) share the same RDRAND source, so it is possible to use a side-channel attack to deduce the likely numbers supplied to a different core).

The lava-lamp generator is still available, I believe, but random bit generation there is VERY slow!

It is possible to use the "system time" as a seed, but even that isn't very random if you regularly turn off/restart your computer, since as I recall it gives time since startup, so the value is likely to lie within a relatively narrow range - a million seconds is about 11 days, if I recall, and even if you use ms you are still only looking at a range of ~10^9. Using "real life clock time" is also pretty rubbish - there were a number of online casinos that used that approach, and got badly stung, since it was possible to deduce what their time was within a few seconds, and then try all the sequences that arose (since their PRNG algorithm was known).

More usefully, modern computer systems provide "cryptographically secure" pseudo-random number generators - that should be good enough for essentially any use (unless the CIA made Intel build in a backdoor! ).

[Hated Moron]

The usual way of introducing genuine randomness is to sample the time when the function is first called.

It doesn't introduce "genuine randomness", that's completely wrong. What it does is to determine the starting point in the pseudo-random sequence, but from then on it is again totally predictable.

You will find I have said this dozens of times over the years, but unless you are an expert mathematician steer clear of drawing naïve conclusions like that because not only are you likely to be incorrect, you could introduce bias or worse into a program you are writing.

From your comments I'm not sure that you've even read the Wiki article to which I linked earlier in the thread. Please do so and take careful note of what it says.

These days most computers are connected to the internet, so in theory at least, randomness could be guaranteed, either by reading the time off the internet or by making use of some other factor

Again, I would strongly suggest you leave this to the experts. There is a cautionary tale at Wikipedia here where it discusses the Windows CryptGenRandom API function which attempted to do exactly the kinds of things you suggest, but still had significant weaknesses.

[p_m21987]

The Spectrum code was so obviously awful and I had every confidence in your code (whether you had written it or chosen it is irrelevant) that sooner or later it would turn up every number. My comments were in no sense a criticism, just an interesting fact.

While the Spectrum's pseudo-random number generator was bad, I think it's important to note the time and the context that it was made in.

The early Sinclair computers were made by a very small team working under heavy constraints, with the ambitious aim of making a computer that was affordable for the masses, at a time when a computer could easily take a whole month's pay or more depending on an individual person's financial situation.

They succeeded and I think it's amazing what they achieved. Despite the flaws, I think the ZX Spectrum was and is a marvellous machine and a very important part of British computing history.

[nvingo]

Can anyone think of any other possible sources of randomness?

Since input devices microphone and camera have been mentioned, how about mouse movements/trackpad touches?
It's most likely impossible for an operator to replicate precisely X-Y movements, besides like those other input devices, an optical mouse vibrating naturally, generates a 'noisy' signal.

[KenDown]

In reply to Richard, I've no intention of trying to write my own random function. The present RND() is quite good enough for anything I need.

In reply to both DDRM and Richard, I didn't envisage any of the methods I mentioned as providing a running randomness, more a completely random seed for RND().

And to p_m21987, yes, the Sinclair, like all Sir Clive's products, was aimed at a mass market and cut lots of corner - anyone remember his dreadful "electric car"? I'm afraid it was the keyboard that turned me off, as word processing was a large part of what I wanted a computer for, and a genuine keyboard for touch-typing was de rigeur. I knew people who swore by it even after the Beeb came out and it is notable that the Electron copied the Spectrum's method of keyword entry.

[p_m21987]

Can anyone think of any other possible sources of randomness?

Since input devices microphone and camera have been mentioned, how about mouse movements/trackpad touches?
It's most likely impossible for an operator to replicate precisely X-Y movements, besides like those other input devices, an optical mouse vibrating naturally, generates a 'noisy' signal.

I remember at one point doing some experiments where I used 'arecord' to record raw audio from a USB audio dongle, and then I took the least significant bit of each sample of the audio signal and plotted it on the screen as a pixel.
It looked pretty random to my eyes at least (absolutely not a scientific measurement)

Assuming that the digital stream was coming raw straight from the ADC of the USB audio dongle and that it was somehow being affected things in the environment, perhaps it could potentially be a source of "randomness", though probably a very poor one if so.

But it's possible that the sound driver or the circuitry of the USB dongle itself were adding some sort of dithering to the digital signal, so either way you really can't trust it. It was a fun little experiment anyway.

[Hated Moron]

Assuming that the digital stream was coming raw straight from the ADC of the USB audio dongle and that it was somehow being affected things in the environment, perhaps it could potentially be a source of "randomness", though probably a very poor one if so.

One possible objection is that it's also where you might expect to find a watermark encoded in the stream (e.g. for Copyright identification purposes) so it might be far from random!

Admittedly these days watermarks are likely to be much more sophisticated than that, but not back in the days of analogue transmission (the BBC's television broadcasts were watermarked for many years, one of the best-kept secrets in the business and I was one of only a handful of people who knew about it).

[Hated Moron]

In reply to both DDRM and Richard, I didn't envisage any of the methods I mentioned as providing a running randomness, more a completely random seed for RND().

The trouble is that the main weakness of RND is not the way it is seeded (using QueryPerformanceCounter in BB4W and SDL_GetPerformanceCounter in BBCSDL, which is actually a pretty good source of initial 'randomness') but the sequence length, which at 2^33-1 is woefully inadequate for some common applications like shuffllng a pack of cards.

So in proposing different ways of seeding the PRNG you are not increasing the range of applications for which RND is suitable.

[p_m21987]

Assuming that the digital stream was coming raw straight from the ADC of the USB audio dongle and that it was somehow being affected things in the environment, perhaps it could potentially be a source of "randomness", though probably a very poor one if so.

One possible objection is that it's also where you might expect to find a watermark encoded in the stream (e.g. for Copyright identification purposes) so it might be far from random!

That's a really good point, I hadn't considered that at all. Though in this particular case, I think that might not have been an issue, since the audio stream was just the input from the mic port, without any mic or anything plugged into it (no actual audio input signal), and I was using Linux (I doubt there'd be code in the linux kernel audio drivers for putting watermarks on audio input/output signals) and this was a very cheap USB audio dongle so the circuitry inside is probably simple and probably doesn't look for watermarks or generate them.

Admittedly these days watermarks are likely to be much more sophisticated than that, but not back in the days of analogue transmission (the BBC's television broadcasts were watermarked for many years, one of the best-kept secrets in the business and I was one of only a handful of people who knew about it).

Wow, that's really cool! I love that. I've always been interested in steganography and hiding messages and signals in unexpected places.

[Hated Moron]

Though in this particular case, I think that might not have been an issue, since the audio stream was just the input from the mic port, without any mic or anything plugged into it (no actual audio input signal)

You are assuming that in the absence of any signal what you will receive is white noise. That will rarely be anywhere close to being the case, much more likely is that it will consist mostly of interference picked up by coupling (capacitive or inductive) from other signals on the PCB. Such interference is likely to have a spectrum which is far from flat.

Using a source of white noise is a legitimate way of acquiring 'random' data but you need to be sure it really is 'white'. That might mean using something as simple (and cheap) as a noise diode, but I have seen proposals for using the Cosmic Microwave Background as a more reliable, 'off-world', source.

Wow, that's really cool! I love that. I've always been interested in steganography and hiding messages and signals in unexpected places.

The BBC's video watermark was hidden in the Fukinuki Hole.