BBC BASIC implementation of RANDU

[KenDown]

I simply ran the short program and then stared at the screen. You could see the scatter of dots gradually becoming denser until finally only half a dozen white pixels were left. It seemed to take an inordinate amount of time before those pixels were filled in one after the other. As I do not believe that the program had suspended operations during that time, I concluded that it was repeatedly plotting pixels that had already been plotted - that is, that some numbers were generated over and over again whereas the numbers represented by the white pixels were not being generated at all until much later in the process.

I certainly wouldn't claim that this fact represented a fault in RND. It did cover the whole area eventually, unlike the Spectrum version!

Your point about the plotting being faster with SD rather than the random number generator is interesting. Thanks.

[Hated Moron]

I concluded that it was repeatedly plotting pixels that had already been plotted - that is, that some numbers were generated over and over again whereas the numbers represented by the white pixels were not being generated at all until much later in the process.

Which is of course exactly what should happen, it's how 'random' numbers work! It's your implication that this is somehow surprising, or represents a shortcoming of some kind, that I don't understand. As I said previously, it's as though you are expecting random numbers to be randomly sorted numbers (so each pixel would be plotted just once, until all had been plotted), but that's not what they are at all.

Try it with a much smaller range of numbers, say RND(10). Here's a sample run up to the point where each number has been generated at least once:

Code: Select all

         3
         8
         5
         8
         4
         5
        10
        10
         5
         6
         5
         2
         7
         3
         7
         7
         5
         5
        10
         1
         2
         6
         3
         5
         4
         5
         2
         3
         5
         7
         8
         4
         3
         3
         6
         3
         2
         2
         4
         8
         3
         8
         4
         7
         5
         9

It took 46 calls of RND(10) before each number had been returned at least once, by which time there had been ten 5s, eight 3s, five 2s, 4s, 7s & 8s, three 6s & 10s, and one each of 1 & 9. All perfectly normal and expected.

[JeremyNicoll]

You could see the scatter of dots gradually becoming denser until finally only half a dozen white pixels were left. It seemed to take an inordinate amount of time before those pixels were filled in one after the other.

But why were you so sure that the remaining pixels would ever get filled in?

[Hated Moron]

But why were you so sure that the remaining pixels would ever get filled in?

With a total of 320K pixels to fill in and a RND cycle length of 2^33-1 there are more than 26,000 RND states per pixel available on average! I don't know whether that means every pixel is guaranteed to be filled in eventually (it may well be that it does), but it must at least mean that the probability is so close to 1.0 that it is certain for all practical purposes.

You could re-jig the code in such a way that it definitely is guaranteed, by calling RND once for each pair of coordinates rather than twice:

Code: Select all

      MODE 0
      seed = RND(-123456)
      FOR I% = 1 TO 1000000
        R% = RND(640*512)-1
        X% = R% MOD 640 : Y% = R% DIV 640
        PLOT 69,X%*2,Y%*2
      NEXT

[KenDown]

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.

[JeremyNicoll]

I don't know whether that means every pixel is guaranteed to be filled in eventually (it may well be that it does), but it must at least mean that the probability is so close to 1.0 that it is certain for all practical purposes.

Isn't the key word in that /eventually/? Why should one expect it to happen in the few minutes (or whatever, though from what he posted I doubt he waited hours or days ..) that Ken stared at his screen for?

[Hated Moron]

Isn't the key word in that /eventually/? Why should one expect it to happen in the few minutes (or whatever, though from what he posted I doubt he waited hours or days ..) that Ken stared at his screen for?

Rather than speculate, wouldn't it be better to calculate how long, roughly, it is likely to take to fill in every pixel? This is a technical forum and the properties of (pseudo-) random numbers are well understood, so the application of some mathematics - and knowing how fast the code runs in BB4W and BBCSDL - should tell you how long Kendall probably had to wait without the need for speculation.

If it helps, this particular calculation is called the Coupon Collector's Problem and there's a Wikipedia page about it. I look forward to seeing your answer.

[JeremyNicoll]

Rather than speculate, wouldn't it be better to calculate how long, roughly, it is likely to take to fill in every pixel? This is a technical forum and the properties of (pseudo-) random numbers are well understood, so the application of some mathematics - and knowing how fast the code runs in BB4W and BBCSDL - should tell you how long Kendall probably had to wait without the need for speculation.

If it helps, this particular calculation is called the Coupon Collector's Problem and there's a Wikipedia page about it. I look forward to seeing your answer.

Plugging 320k into n.log n gives 327,680 * (roughly) 12.7 = 4,161,536.

That's roughly four times the million iterations you timed on your machine, so presumably approx 4 times your 35 secs (BB4W) or your 2.6 secs (SDL) so 140 secs or 10 secs.

What I don't understand is why the maths described in the Coupon Problem page guarantees all pixels would actually be targeted. I can see that if you ran many trials and averaged the #iterations used for them all, they might be around what the formula predicts (*). To me, it's like the idea that in 36 rolls of two dice you're likely to get a double six once - but if you did that 36 rolls just once, you might very well not see any sixes, let alone a double.

* - give or take the fact that "O n.log n" only measures the biggest factor affecting #iterations. In the n=50 example on that wikipedia page, 50 * log 50 is about 195, but the expected #iterations is around 225.

[Hated Moron]

What I don't understand is why the maths described in the Coupon Problem page guarantees all pixels would actually be targeted.

Who says it does? I suggested that you use the maths to "calculate how long, roughly, it is likely to take to fill in every pixel". Obviously an exact estimate isn't possible, but as with anything with an element of randomness you can choose an arbitrary threshold beyond which you can call it 'certain, for all practical purposes'.

Of course the situation with BBC BASIC's RND() function is different. Because it returns pseudo-random numbers, which are predictable and repeatable, you can determine a number of iterations after which you can be 100% certain all pixels will have been filled. I don't know what that value is, but in principle it can be calculated.

[KenDown]

Just thinking about the statement that the RND() function is "pseudo-random". The usual way of introducing genuine randomness is to sample the time when the function is first called. This could, in theory, be defeated by the program setting the time variable before calling RND(), but I wonder if there is some internal clock which remains unaffected by such deliberate action?

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 - the number of people logged into Google or Amazon, perhaps? Indeed, one of those large companies could, perhaps, make such a source of randomness available either as a freebie or as a paid-for service.

Or, of course, one could detect the time taken to "ping" a particular internet site or to download a page or picture. It might be amusing to write a version of RND where the parameter is a URL - RND("http://www.amazon.com") and the user can set the website he thinks is most likely to be random!

However I remember reading years ago about some scientists who trained a camera on a lava lamp and somehow converted the patterns of rising and falling blobs into a random number. Most computers have a camera attached and we are always being warned about the dangers of the camera being remotely activated. A quick snapshot could be a source of randomness based either on the level of light the camera perceives or the colour balance of that light or even a combination of the two. (And even if the user is one of those paranoid individuals who has stuck black tape over the camera, there might be sufficient "noise" in the camera's response to nevertheless provide the required element of randomness.)

What about a camera pointed at an empty room? Not a problem. All lights flicker at 50hz (60 if you are in America) and unless the camera is sampled at exactly that rate, there will be tiny variations in the intensity of light, sufficient to give genuine randomness.

Computers with a camera almost always have a microphone, which could be sampled and again, even if the room was deserted and silent or the microphone disabled or missing, there would almost certainly be "noise" in the system that could be utilised.

Can anyone think of any other possible sources of randomness? We could think either of a genuine and continuing randomness - such as the lava lamp - or of a random seed sampled once and fed into the pseudo-random generator.