Improving on QBasic's Random Number Generator | Hacker News Reader

Improving on QBasic's Random Number Generator

nullprogram.com

63 pointstodsacerdoti28 comments

I have no QBasic at hand right now, but the random generator was realy bad. I started programming with QBasic in my teens and so I just would do so fun with the random generator. When you set the SCREEN 16 (640x480 16colors) use the first random number for the X position, the second for Y, the third random number just generate, but don't use and random number 4 is for the color 0-16. Then just draw a point and loop. The result is a picture with just diagonal lines. The line borders are a bit blurry, but else really straight, no curves or other artefacts. The third random numer was for circle size, as I said, I learnd programming with it.

Incredible. I did the same thing decades ago and got the same diagonal lines. I couldn't work out what was going wrong.

I knew already computer random is not really random, but expected a bit more randomness than just diagonal lines :-)

I remember the Spectrum Basic Programming (the book included when buying ZX Spectrum, famous UK home computer) by Steven Vickers, 1982, 38 years ago:

The quote from the Charpter 16: Colours

"Run this program:

   10 POKE 22527+RND*704,RND*l27
   20 GO TO 10

Never mind how this works; it is changing the colours of squares on the television screen and the RNDs should ensure that this happens randomly. The diagonal stripes that you eventually see are a manifestation of the hidden pattern in RND - the pattern that makes it pseudorandom instead of truly random." (1) (2)

In another part of the manual it also explains the mathematical properties of the built-in random generator:

"(For mathematicians only.) Let p be a (large) prime, and let a be a primitive root modulo p. Then if bi is the residue of a’ modulo p (1 <= bi <= p-1), the sequence

(bi-1)/(p-1)

is a cyclical sequence of p-1 distinct numbers in the range 0 to 1 (excluding 1). By choosing a suitably, these can be made to look fairly random.

65537 is a Fermat prime, 2^16+1. Because the multiplicative group of non-zero residues modulo 65537 has a power of 2 as its order, a residue is a primitive root if and only if it is not a quadratic residue. Use Gauss’ law of quadratic reciprocity to show that 75 is a primitive root modulo 65537." (3)

---

1) It works by directly changing the "attributes" part of the memory which is directly mapped to the color of the 8x8 pixel part of the screen used for different characters (22 rows of 32 characters == 704), randomly selecting both the position on the screen and the value of the attribute, two calls per one loop pass. It's beautiful in how short the program is.

2) The appearance of "the diagonal stripes": https://ibb.co/kB2qS2L

3) Is the suggested proof online now somewhere?

And the author of that book is a mathematician:

https://en.wikipedia.org/wiki/Steve_Vickers_(computer_scient...

https://www.cs.bham.ac.uk/~sjv/

"My particular interest is in toposes as generalized spaces, with the connection between logic (specifically, geometric logic) and topology. These are areas of mathematics that have connections with computer science, although my work in them is often purely mathematical. Over 2017-18 I formalized an approach to topos theory using Joyal's Arithmetic Universes (AUs) as a substitute for Grothendieck toposes, potentially implementable on computers, and showed how to use it to obtain constructive, base-free results for toposes. My current work is on developing the techniques of this approach and exploring the extent to which it can capture Grothendieck's original applications of topos theory."

"I was a computer programmer for several years. I wrote the ROM and user manuals for two Sinclair computers, the ZX81 and the ZX Spectrum. Then with Richard Altwasser I founded Jupiter Cantab Ltd, which produced the Forth-based Jupiter Ace microcomputer."

FYI, the ZX Spectrum Next is still available for pre-order until the end of the year. The original run was a successful Kickstarter campaign, so I had enough confidence to pony up $325 pounds for one. It is beautiful and has a lot of modern conveniences like USB/HDMI/VGA/WiFi...etc. People still make new games too. It's a cool scene.

Thank you and please note who submitted this 4 days ago:

https://news.ycombinator.com/item?id=25081121

However the topic in this thread is that the properties of the random number generators discussed in 2020 were a part of the user manual of the home computer in 1982, and I find that totally amazing and inspiring.

It is also explainable knowing who wrote both the ROM and the book, which I also mentioned.

I figured it might have been submitted, but didn't recall seeing it. Thanks for linking. I missed out on this entire era, so I've been excited about the potential to experience it with some modern advancements :).

I could only dig up QBasic 1.1 and maybe it was fixed there as I'm unable to reproduce the problem. I do recall discovering similar things myself at the time though! :-)

This is my code and the end result. Let me know if I should be making some tweaks: https://imgur.com/a/98x0soS

Let it run for a little bit longer (and increase DOSBox cycles to speed it up). The code is correct.

The caffeine hadn't kicked in enough earlier and I forgot you could just speed it up(!) .. having done that, I am now seeing what was speculated: https://imgur.com/a/hgWEA0H

BTW, for anyone else who wants in on this action. Download DOSBox then you can find various forms of BASIC at https://www.qbasic.net/en/top-ten-downloads/

Sorry, number 3 was the color and number 4 was spare. https://imgur.com/a/SSfaewf

Aha! Certainly more striking :-)

Leaving mine running did result in a pattern (though weaker) nonetheless though: https://imgur.com/a/hgWEA0H

He could have also written the thing in assembly, stored the machine code in DATA statements, loaded it into an array with a READ/POKE loop, and then called it with CALL ABSOLUTE.

I actually used this technique to replace Nibbles’ busy-waiting delay loop with an invocation of interrupt 0x15 service 0x86.

Great idea, I thought "too bad that QBasic didn't support assembly", on the other hand - I definitely wrote painting programs that used the mouse in QBasic, so I must have used it one way or another. QuickBasic had support for inline assembly though if I remember correctly?

I remember the "show the cursor on the screen and grab mouse position and clicks" was a common copy/paste bit of assembly back in the day. Looks like both qbasic and quickbasic supported it:

- dim asm as string

- concatenate your assembly together

- DEF SEG = VARSEG(ASM)

- CALL ABSOLUTE(SADD(ASM))

QuickBasic could load external libraries (potentially written in C or Assembly), but there was no inline assembly - just CALL ABSOLUTE on binary blobs as with QBasic 1.1.

> QuickBasic had support for inline assembly though if I remember correctly?

No but BBC Basic did!

> I soon got the impression that QBasic community has usually been another case of the blind leading the blind.

I have a feeling this was especially the case in the 90s, but there have been some great people sharing high-quality works in the early 2000s QBasic scene.

> especially the case in the 90s

You're in for a shock, we're still in the "blind leading the blind" phase as GitHub stars and Twitter followers currently dictate who's a "leader" in the software engineering world. With the invention of social media and their likes, our work and "innovation" is driven by hype more than ever before.

I was specifically talking about QBasic here. Given how much the user base of that language has shrinked in the last 20 years, there's less blind leaders. :) If you are still working with QBasic these days, then it's probably either because that's what you have always been doing (and you are probably "blind" in that regard), or you are exploring retro tech that you grew up with as a teenager and are highly experienced now, like the writer of this blog post.

> the implementation is a full 32-bit multiply using 16-bit limbs

> (note: the LCG constants listed here are wrong)

It's a buggy 24-bit multiply and the constants are accessed wrongly.

Look at the code https://www.qb64.org/forum/index.php?topic=1414.0:

The third MUL computes the same value as the first but it should be [RndA+2] * [RndVar] and not [RndA] * [RndVar] hence a=0fd43fdh instead of a=0343fdh. Also carries are not taken into account in the first two ADDs.

The addition of c is similarly buggy.

I wrote a mistake. Carries can be ignored as the additions are made on the high-order word of the result.

Does the original implementation bias towards/against certain initial positions in the array? Could an 'attacker' try to insert himself at a specific location to gain more fame? My gut feeling is that any change in the rng would not fix the fundamental problem that a low iteration count biases towards the initial ordering. But does that even matter after hundreds of thousands of iterations? Is any improvement in rng just a performance improvement, in that it might give high quality results after fewer iterations?

Hummm... It would be interesting comparing against Turbo Basic implementation. Turbo Basic was the Borland copy/response to QBasic. It's totally source code compatible with QBasic.

> Turbo Basic was the Borland copy/response to QBasic.

Turbo Basic predates QBasic (but was after and responded to QBasic's predecessor, QuickBasic.)

> It's totally source code compatible with QBasic.

I don't think that that is true of any version of Turbo/PowerBasic and any version Quick/QBasic.

Fascinating. I had no bad the original function was, the intent behind such functions has completely changed (simple --> secure)

The original Microsoft BASICS as used on early PC's had a number of interesting aspects, that would shock a lot of todays programmers :-) (not that I want to go full four Yorkshire men )

Having to manually set the exit condition of a loop to avoid memory leaks

Reply on news.ycombinator.com