BBC BASIC implementation of RANDU

[Hated Moron]

I don't know if Acorn first used that algorithm in BBC BASIC or whether it was previously used in Atom BASIC. Either way it's a standard maximal-length LFSR, as for example can be found listed in this Xilinx application note.

Just to add that's there's an equally nice 65-bit maximal-length LFSR listed there (feedback from bits 64 and 47 - they count the bits from 1) which would have been a good choice for 64-bit BBC BASICs - had compatibility with earlier versions not been an overriding consideration.

[p_m21987]

I feel bad about 'cheating' my way back onto the Discussion Group - I never post there because it was made very clear that I am not welcome, but they nevertheless see the posts I make here because of the automatic forwarding.

I empathise that it may be difficult and uncomfortable to be present in a place where you feel that not everyone appreciates you. Though, I would say, I personally consider you to be welcome.
The way I see it is that your welcomeness should be defined by the OR function of the opinions of all the members, if you get what I mean. (Sorry if I'm not making much sense.)
Lots of the members highly value your presence and your expertise and authority on the subject of BBC BASIC, to me that's what matters. Screw the haters, as they say.

Eek, that wasn't me it was Sophie Wilson. Don't make that mistake at StarDot or the RISC OS forums.

Oops, sorry.
Though I would argue that you can take the credit for making BBC BASIC as good as it is.
I seem to remember reading that some of the features I value the most about the language were included at your insistence. My memory is failing me, I think it was something like being able to nest REPEAT loops, or make recursive PROCedures and/or functions, or something. Maybe you know what I'm referring to, but if not, sorry if I'm not making much sense.

PM

[p_m21987]

On the subject of RNG functions, I've recently been playing with and learning about the Sinclair ZX Spectrum.
The manual for the ZX Spectrum actually supplies the definition of the function behind its RND and RANDOMIZE features, so for fun I've implemented them in BBC BASIC now. It exhibits a similar kind of stripey pattern in the 3D test, though surprisingly in 3D it looks a little bit better than RANDU from most angles.

But if you test it by plotting random pixels in two dimensions, it becomes clear that it's very bad indeed; even at a low resolution you will see dotty stripes on the screen. Amazing!
Even on an original 48k Spectrum running at its unmodified speed, a simple Sinclair BASIC program that plots random pixels will reveal this pattern after running for just a few minutes.

This is an amazing function and a piece of computing history from a wonderful computer that changed so many people's lives, and I hope you'll find it as interesting and intriguing as I have.

The information about ZX Spectrum's RND was taken from this page of the ZX Spectrum BASIC manual: https://worldofspectrum.org/ZXBasicManu ... hap11.html

The 2D pixel plotting test for the ZX Spectrum RND function:

Code: Select all

      spectrum_b%=1

      PROCspectrum_randomize(0)

      REPEAT
        PLOT69, FNspectrum_rnd*1280, FNspectrum_rnd*1024
      UNTIL FALSE

      END

      REM: BBC BASIC implementation of RND and RANDOMIZE from Sinclair Basic on the ZX Spectrum

      DEFFNspectrum_rnd
      spectrum_b%=(75*spectrum_b%) MOD 65537
      =(spectrum_b%-1)/65536

      DEFPROCspectrum_randomize(n%)
      IF n%<0 OR n%>=65536 THEN ERROR 1, "Integer out of range"
      IF n%=0 THEN spectrum_b%=1 + TIME MOD 65536
      spectrum_b%=n%+1
      ENDPROC

The 3D spectral test for the ZX Spectrum RND function:

Code: Select all

      spectrum_b%=1

      PROCspectrum_randomize(0)

      n%=3100
      DIM p(n%,2), c(n%)
      FOR i%=0 TO n%
        FOR j%=0 TO 2
          p(i%,j%) = (FNspectrum_rnd-0.5)*700
        NEXT
        c(i%)=1+FNspectrum_rnd*14
      NEXT

      DIM r(2,2), r2(2,2), a(n%,2)

      MODE 8
      OFF
      ORIGIN 640,512
      *refresh off
      REPEAT
        MOUSE X%,Y%,B%
        a=X%/640*PI
        a2=Y%/-512*PI
        r(0,0)=COSa: r(2,0)=SINa: r(1,1)=1.0: r(0,2)=-SINa: r(2,2)=COSa
        r2(0,0)=1.0: r2(1,1)=COSa2: r2(2,1)=-SINa2: r2(1,2)=SINa2: r2(2,2)=COSa2
        a() = p() . r()
        a() = a() . r2()
        CLG
        FOR i%=0 TO n%
          GCOL 0, c(i%)
          PLOT 69, a(i%,0), a(i%,1)
        NEXT
        *refresh
        WAIT 1
      UNTIL FALSE

      END

      REM: BBC BASIC implementation of RND and RANDOMIZE from Sinclair Basic on the ZX Spectrum

      DEFFNspectrum_rnd
      spectrum_b%=(75*spectrum_b%) MOD 65537
      =(spectrum_b%-1)/65536

      DEFPROCspectrum_randomize(n%)
      IF n%<0 OR n%>=65536 THEN ERROR 1, "Integer out of range"
      IF n%=0 THEN spectrum_b%=1 + TIME MOD 65536
      spectrum_b%=n%+1
      ENDPROC

[Hated Moron]

The way I see it is that your welcomeness should be defined by the OR function of the opinions of all the members, if you get what I mean.

I am immovable in my opinion that even if only one member objects to me posting, then I must not. It's not a democracy, I don't care how many others may be happy for me to do so, if one person feels that strongly that's what matters to me. Look at it this way: if one person kills me, it doesn't matter how many didn't - I'm still dead!

I seem to remember reading that some of the features I value the most about the language were included at your insistence. My memory is failing me, I think it was something like being able to nest REPEAT loops, or make recursive PROCedures and/or functions, or something. Maybe you know what I'm referring to.

What you are no doubt referring to is that in the very earliest of Sophie's proposals for what became ARM BASIC V she suggested that multi-line IF...THEN...ENDIF clauses be added, but that they not be nestable. My reaction on behalf of the BBC was, not surprisingly, that this was unacceptable.

But if you suggest to BBC BASIC enthusiasts today that I (or the BBC) was responsible for IF...ENDIF clauses being nestable they will of course (and quite reasonably) retort that had the BBC not insisted on it Sophie would have in any case realised how silly not being nestable would be.

So you can read this any way you want really. If you like to think the BBC helped encourage Sophie to make the right decision you can, but if you prefer to think that ultimately she would have come to the same conclusion that's probably true too.

I can't, off hand, think of any feature of Acorn's BBC BASICs which I can claim to have any irrefutable responsibility for.

[KenDown]

I've just read a post - which I presume will be cross-posted to here eventually - in which user p_m21987 implements the code used by the Spectrum for its RND function. As he points out, it is astonishingly bad. Just how bad it is can be seen by comparing the results of the Spectrum function with the RND function in our own beloved BBC for WINDOWS.

Code: Select all

      REPEAT
        PLOT69,RND(1280),RND(1024)
      UNTILFALSE

This produces a fairly even scattering of dots with no detectable pattern to them. What did surprise me, though, was just how long it took for the final few white spots to be filled in. Clearly there are some numbers that RND is "reluctant" to return and others that it "favours", even though it does get there in the end.

Which, I suppose, is the important thing.

Running the same short program in BBC SD is astonishingly faster!

[KenDown]

Subsequent to my previous post, I conducted an experiment.

Code: Select all

      TIME=0
      REPEAT
        PLOT69,RND(1280),RND(1024)
      UNTILFALSE

When the area was completely black, with not a single white pixel to be seen, I pressed Escape and then typed PRINT TIME.

BBC SD 2712
BBC WIN 32340

The only thing I'm not sure about is whether SD is actually faster or just uses a better algorithm so that all possible numbers are dished up sooner. I got the feeling, watching the screens, that WIN was revisiting numbers an awful lot of the time and therefore repeatedly landing on points that had already been visited.

Does anyone know?

[Hated Moron]

The only thing I'm not sure about is whether SD is actually faster or just uses a better algorithm

I've noted here previously that the 32-bit x86 editions of BBC BASIC for SDL 2.0 use the same BASIC interpreter as BBC BASIC for Windows, they are to all intents and purposes the identical code; so there should be no significant difference in execution speed if run on the same machine.

Did you perform the 'obvious' test of comparing the time taken in generating the random numbers with the time taken in plotting them? To do that you would, of course, need to separate out the two steps in your code, then you could (for example) use the Profiler in both BB4W and BBCSDL:

Code: Select all

      TIME=0
      REPEAT
        X%=RND(1280):Y%=RND(1024)
        PLOT69,X%,Y%
      UNTILFALSE

I got the feeling, watching the screens, that WIN was revisiting numbers an awful lot of the time and therefore repeatedly landing on points that had already been visited.

I'm not sure whether you misunderstand what (pseudo-) random numbers are, but just for clarity they are not randomly sorted numbers, which it sounds from your description is what you were expecting them to be. Whereas in a randomly-sorted set of ordinal integers (say 1-100) the same value will not occur twice, in a 'random' set of integers in the range 1-100 it is highly likely that there will be repetitions.

Have you considered seeding the PRNG with a constant value in your program, so that exactly the same sequence of numbers is generated in both BB4W and BBCSDL?

Code: Select all

      TIME=0
      seed = RND(-123456)
      REPEAT
        X%=RND(1280):Y%=RND(1024)
        PLOT69,X%,Y%
      UNTILFALSE

The properties of BBC BASIC's PRNG have been discussed earlier in this thread, with links to other references with lots of detail, so I don't think it would be helpful to re-visit that. I'm also conscious that straying into the area of illusions caused by random numbers (whether visual or auditory!) is in danger of becoming contentious, so I would suggest drawing this to a close before that happens.

[Hated Moron]

repeatedly landing on points that had already been visited.

Also note that you are generating BBC BASIC graphics coordinates, not pixel coordinates, so there are four different pairs of values which correspond to the same pixel.

To add even more complication, in common screen modes (such as MODE 0 and MODE 8) PLOT 69 plots not one pixel but two (a rectangle one pixel wide by two pixels tall).

[Hated Moron]

Clearly there are some numbers that RND is "reluctant" to return and others that it "favours"

I didn't notice this comment before - it is of course nonsense. That some numbers are 'favoured' over others is the very antithesis of what a good Pseudo-Random Number Generator does, and is demonstrably not the case for BBC BASIC's RND function.

I find it sad that I have to defend BBC BASIC against this kind of false assertion, especially when so much information about the RND function is readily available.

[Hated Moron]

Running the same short program in BBC SD is astonishingly faster!

No follow-up from the OP, so I did the test myself. Running this program (1,000,000 iterations):

Code: Select all

      MODE 0
      seed = RND(-123456)
      FOR I% = 1 TO 1000000
        X%=RND(1280):Y%=RND(1024)
        PLOT69,X%,Y%
      NEXT
      QUIT

Gave the following profiler report in BBC BASIC for Windows:

Code: Select all

Time spent Profiling: 35864 milliseconds.

         8:     0.02      MODE 0
         0:               seed = RND(-123456)
         1:               FOR I% = 1 TO 1000000
       262:     0.73      X%=RND(1280):Y%=RND(1024)
     35513:    99.02      PLOT69,X%,Y%
        80:     0.22      NEXT

and this in BBC BASIC for SDL 2.0:

Code: Select all

Time spent profiling: 2.664 seconds.

         0:                   MODE 0
         0:                   seed = RND(-123456)
         0:                   FOR I% = 1 TO 1000000
       214:     8.03          X%=RND(1280):Y%=RND(1024)
      2436:    91.44          PLOT69,X%,Y%
        14:     0.53          NEXT

So a small difference in the time taken for the RND functions (probably measurement tolerance, because it's such a small proportion of the total in both cases) but a massive one in the time taken plotting (more than a factor of 14 times), as would be expected from BBCSDL using GPU-accelerated graphics.