how random is RND in Basic and Turbo Basic? (seems to be different)

[danwinslow]

Not sure you can do anything about it via normal programming using the stock RNG algorithm. What you need is a source of more entropy and probably implement a custom RNG that takes full advantage of it. You can think of entropy as sources of randomness from the environment, things you can sample as a number and preferably that are themselves considered random.

[thorfdbg]

On 1/31/2023 at 2:42 PM, danwinslow said:

The odd thing about randomness is that it impossible to prove, or even define completely. If you could, then by definition it wouldn't be random.

It's not quite as bad. There are a couple of well-understood statistical tests that provide you with the quality of a random generator, and how likely it is that a random source is IID. (identically independently distributed). In particular, see the "chi-squared test" and the "spectral test".

 

As scientific source, I recommend "Donald Knuth: The Art of Programming, Vol.2 Numerical and semi-numerical algorithms". You find (almost) everything about random generators you dared or never dared to ask there.

 

 

[danwinslow]

I meant in more of a philosophical nature. Consider: any such run of numbers and the tests you mention are for, by necessity,  a limited run. Proving a normal distribution over a subset of iterations is not the same as saying something is actually inherently random, it's just one way of detecting if your particular algorithm favors certain outcomes over others. The nature of your algorithm is digital - you may input some analog entropy along the way but there's no escaping the fact that your are running a deterministic routine, and you need to run it forever to prove anything. Even sampling only a natural random event such as the decay of a particle is necessarily limited in span, and a run of all 5's, say, for any given amount of time is perfectly possible. To prove randomness is proving a negative- you have to say that no causes can ever be provided for a certain outcome.

This is why these algorithms are always called pseudo random generators. The actual existence of true inherent randomness is by definition impossible to prove algorithmically.

Edited February 1, 2023 by danwinslow

[thorfdbg]

Even on this question, you find a chapter in the above book. (-;

 

[danwinslow]

Yes, I'm familiar with Knuth. It's a great book.

Edited February 1, 2023 by danwinslow

[ClausB]

Atari's use of POKEY's RANDOM register is fundamentally different from any software RNG. POKEY cycles though a pseudo-random sequence very quickly while the CPU is doing other things, so the randomness comes from sampling that sequence at non-deterministic times. The POKEY chip has no RESET input, and so that sequence won't be aligned with the boot process. That, together with all the interrupts going on, plus the waiting for human input and the waiting for SIO peripherals, all combine to make it completely non-deterministic.

Edited February 2, 2023 by ClausB

[thorfdbg]

Careful! It does not make its samples non-decorrelated, in particular if you take samples from it quickly one after another, such as what TurboBasic does. Also, the samples it generates are not completely equal-distributed over the range 0..255. 0 does not occur at all, for example. If you want high-quality RND, it would probably be better to combine this approach with a well-researched pseudo-RND, e.g. use pokey only as a seed.

[Rybags]

I'm fairly sure the sequence will be aligned - Pokey coming out of INIT state should reset the LFSR sequence.  Due to how the hw registers are cleared on cold/warmstart, you have WSync being hit which will align the CPU relative to horizontal scan position.  Though I do suspect on a warmstart the VCount value would be non deterministic which should be sufficient to not repeat sampled values too often.

[ClausB]

1 hour ago, thorfdbg said:

if you take samples from it quickly one after another, such as what TurboBasic does.

Even that won't be repeatable due to DMA timing.

[ClausB]

1 hour ago, thorfdbg said:

0 does not occur at all, for example

Are you sure? RANDOM is the high 8 bits of the 17-bit poly, so I doubt 0 is excluded.

[ClausB]

1 hour ago, Rybags said:

I'm fairly sure the sequence will be aligned - Pokey coming out of INIT state should reset the LFSR sequence.  Due to how the hw registers are cleared on cold/warmstart, you have WSync being hit which will align the CPU relative to horizontal scan position.  Though I do suspect on a warmstart the VCount value would be non deterministic which should be sufficient to not repeat sampled values too often.

WSYNC and VCOUNT are ANTIC functions which are independent of POKEY. Since one chip has a RESET input and the other does not, they will start at different times depending on power up transients.

[Rybags]

RANDOM can have 00 value since it is just a subsample of the LFSR.

 

The other thing - need phaeron's input here.

The register clear on cold/warmstart hits WSync which is sufficient to give us deterministic timing (Pokey will come out of Init mode at the same time).  So in theory we could get a repeatable random sequence though you'd only experience it with a machine code program.

It could be tested easily enough - a cartrdige in diag mode.  Just have it read and print several samples on startup.

[ivop]

On 2/1/2023 at 8:40 AM, Marius said:

but I am talking here about a theoretical situation where every result (1-6) has the same frequency.

That's not enough. If you did not understand the above explanation by danwinslow about distribution and all, consider a sequence like this:

 

1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,6,6,6

 

1's -> 5/30 = 0.166...

2's -> 5/30 = 0.166...

3's -> 5/30 = 0.166...

4's -> 5/30 = 0.166...

5's -> 5/30 = 0.166...

6's -> 5/30 = 0.166...

 

Your metric would say it is perfectly balanced, even though it is completely predictable. Generating pseudo random numbers is hard

 

Edited February 2, 2023 by ivop

[Marius]

44 minutes ago, ivop said:

That's not enough. If you did not understand the above explanation by danwinslow about distribution and all, consider a sequence like this:

 

1,1,1,1,1,2,2,2,2,2,3,3,3,3,3,4,4,4,4,4,5,5,5,5,5,6,6,6,6,6

 

1's -> 5/30 = 0.166...

2's -> 5/30 = 0.166...

3's -> 5/30 = 0.166...

4's -> 5/30 = 0.166...

5's -> 5/30 = 0.166...

6's -> 5/30 = 0.166...

 

Your metric would say it is perfectly balanced, even though it is completely predictable. Generating pseudo random numbers is hard

 

My question is impossible for me to ask jn English. You are Dutch, I will send you a private message to explain my question in Dutch. I do not want to write in Dutch on a forum where one is supposed to write English haha.

 

The answer you give is not about what I asked, so probably I wrote the question wrong haha. Is it okay for you to get a private message in Dutch?

[ivop]

38 minutes ago, Marius said:

My question is impossible for me to ask jn English. You are Dutch, I will send you a private message to explain my question in Dutch. I do not want to write in Dutch on a forum where one is supposed to write English haha.

 

The answer you give is not about what I asked, so probably I wrote the question wrong haha. Is it okay for you to get a private message in Dutch?

Sure, no problem. I got it that what I wrote was not an answer to your question, but I just wanted to point out that frequency of occurrence is not enough to determine if a sequence is random

 

As for your question, I don't know the distribution of RANDOM, so it is impossible to say if using just RANDOM % 6 or using buckets of ABS(256/6) is better.

[ClausB]

6 hours ago, Rybags said:

The register clear on cold/warmstart hits WSync which is sufficient to give us deterministic timing

Oh, I see, you mean the low two bits in SKCTL which initialize POKEY circuits. So the question is, does that reset the 17-bit poly?

 

Excerpt from POKEY schematic at https://brainwagon.org/wp-content/uploads/2019/08/PokeyReSchem.pdf shows INIT signal going to a gate through an X, whatever that means.

 

[phaeron]

Initialization mode does reset the LFSR, and upon exiting init mode RANDOM will start a deterministic sequence beginning with $FF. This usually goes unnoticed because of the randomness introduced by an SIO boot or pressing a key, which is enough to avoid problems. But as Rybags notes, a cart start without user input could end up with a predictable sequence.

 

Although POKEY has no reset pin, a power-on can be somewhat deterministic if the machine is started cold as the circuits tend to have specific biases. This is similar to how uncleared DRAM will tend to have characteristic stripes from the internal memory bank layout of the DRAM chips. A "lukewarm start" from a recently powered off machine, though, will tend to preserve some state from the power-off.

 

 

[Rybags]

The other thing is user initiated warmstart.

I think that would introduce some randomness since you could be on any given scanline.

I'm fairly sure Antic Reset doesn't affect the active scanline count, so whatever pattern you attempted to read in software would be affected by the DMA steals having a different pattern each time.

[ClausB]

7 hours ago, ClausB said:

INIT signal going to a gate through an X, whatever that means.

X means it's an asynchronous input. So the poly counter is indeed reset.

[ClausB]

Just tried several power up cycles with Star Raiders on 1200XL. The star patterns start differently every time.

[thorfdbg]

There is still sufficient randomness because the startup is not exactly identical each time - for example, the location of the vertical blank relative to the initialization time of POKEY may be slightly different, causing a different number of CPU cycles until the CPU reaches the PC where star raiders reads pokey. If you load it from disk, the delay from the disk drive until the sector is under the drive head is slightly different each time, etc... IOWs, there is still sufficient entropy in the process to give you different numbers each time.

[phaeron]

Ah, yeah, I forgot about that. The initial vertical counter will vary, and while that might not otherwise be that significant, Star Raiders waits for vertical blank before initializing the starfield. We know from the decap that ANTIC does have reset circuitry for the H/V counters, but for whatever the reason it isn't effective.

 

[ClausB]

4 hours ago, thorfdbg said:

There is still sufficient randomness because the startup is not exactly identical each time - for example, the location of the vertical blank relative to the initialization time of POKEY may be slightly different, causing a different number of CPU cycles until the CPU reaches the PC where star raiders reads pokey. If you load it from disk, the delay from the disk drive until the sector is under the drive head is slightly different each time, etc... IOWs, there is still sufficient entropy in the process to give you different numbers each time.

That makes sense. Yes, I mentioned the effect of SIO in my first post. My test today was with the Star Raiders cart, no SIO involved.

[Rybags]

So the vertical scan position is random on powerup?

 

Maybe they didn't engage vertical reset because it could cause screen roll?  But that wouldn't have been relevant on the 800, only the XL since earlier machines only used Reset for power on.