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.
BBC BASIC implementation of RANDU
Re: BBC BASIC implementation of RANDU
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.KenDown wrote: ↑Thu 28 Sep 2023, 18:34 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.
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
- JeremyNicoll
- Posts: 72
- Joined: Sun 26 Jul 2020, 22:22
- Location: Edinburgh
Re: BBC BASIC implementation of RANDU
But why were you so sure that the remaining pixels would ever get filled in?
Re: BBC BASIC implementation of RANDU
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.JeremyNicoll wrote: ↑Fri 29 Sep 2023, 21:41 But why were you so sure that the remaining pixels would ever get filled in?
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
-
- Posts: 327
- Joined: Wed 04 Apr 2018, 06:36
Re: BBC BASIC implementation of RANDU
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
- Posts: 72
- Joined: Sun 26 Jul 2020, 22:22
- Location: Edinburgh
Re: BBC BASIC implementation of RANDU
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 wrote: ↑Sat 30 Sep 2023, 01:38 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.
Re: BBC BASIC implementation of RANDU
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.JeremyNicoll wrote: ↑Sat 30 Sep 2023, 08:01 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?
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
- Posts: 72
- Joined: Sun 26 Jul 2020, 22:22
- Location: Edinburgh
Re: BBC BASIC implementation of RANDU
Plugging 320k into n.log n gives 327,680 * (roughly) 12.7 = 4,161,536.Hated Moron wrote: ↑Sat 30 Sep 2023, 11:47 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.
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.
Re: BBC BASIC implementation of RANDU
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'.JeremyNicoll wrote: ↑Sat 30 Sep 2023, 14:35 What I don't understand is why the maths described in the Coupon Problem page guarantees all pixels would actually be targeted.
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.
-
- Posts: 327
- Joined: Wed 04 Apr 2018, 06:36
Re: BBC BASIC implementation of RANDU
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.
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.