Random-number generation

[Arlet]

Alex1 wrote:

When I announce a period for my algorithms, they remain random throughout the period. You have to do the same otherwise it's cheating for the challenge I too can create an algorithm with a period of 2^1024 but which will only be random on 100 KB :

It's not cheating. It's just a different category. I mention both the period as well as the PractRand results. The minimum period is important if you want to be sure to avoid bad seeds where the period is really short. For instance, if you initialize an LFSR with all-zero value, it gets stuck there, which is highly undesirable. When I say that the period is guaranteed to be 2^48, it means you don't have to worry about any bad seeds. As far as random quality is concerned, most 6502 users would happily pick a decent algorithm that's smaller & faster over one that's super high quality. When PractRand says it's good until 1 GB, it doesn't mean that it suddenly gets really bad. It just means that it's getting enough data that subtle patterns start to emerge. If you toss a coin that's heads for 50.00001% of the time, and you throw it billions of times, you start to realize that the coin is bad, but that doesn't mean it's useless. There are many applications where such a coin would be perfectly acceptable.

Quote:

I let my Raspberry PI (only one core used) run for 70 days to prove that my LFSR64 + LCG64 passed the 16 TB

That's fine if you only want to test one particular algorithm. If I'm trying to optimize for cycles, I run hundreds of different trials, sometimes thousands. I can't run hundreds of variations if each attempt takes weeks to run.

Quote:

1TB seems to me very little to prove that an algorithm is random

1TB for a 6502 system is exceptionally good.

Quote:

Time is not an issue, just use a system that can stay on for a long time because it does something else in the meantime.

It's an issue for me, because having the test running on my PC slows it down for other things, including other random generators that I'm testing.

[Alex1]

All you have to do is test your final generator, the one you propose as the best. For example, I proposed only two algorithms: LFSR64+LCG64 and ACR4. Not all intermediate test algorithms need to be tested for as long, only the last one should be.

[Arlet]

Off topic, but may be interesting to some. I've (finally) released a version of a pseudo random generator for Microchip AVR / Arduino.

[barrym95838]

Arlet wrote:

If you just wanted something super simple that produces every single 16 bit value exactly once, in random order, you could use something like this. 16 bit output in A,X:

Code: Select all

    CLC
    LDA #1 ; any odd value
    ADC s+0
    STA s+0
    ADC s+1
    STA s+1
    ASL A
    ADC s+0
    TAX
    EOR s+0
    RTS

Good enough for games where you need a random action for a monster, but it's not going to pass any randomness tests.

Arlet, superficially, this looks very promising with an immediate of #39:

I wondered what the ASL was doing to help, and TBH it looks pretty good without it:

These images are of an Apple ][ hi-res screen after filling the screen approximately 30% full of "random" dots. The one without the ASL seems to have a slightly coarser "texture", but I think either one suits my purposes just fine. Do you (or anyone else) have any further comments before I add it to VTLC02? It's going to have a net cost of nine bytes, but I think the improved quality and slightly improved performance outweigh the cost.

[Arlet]

The ASL is used to clear the carry flag, so that the output function is bijective (invertible). The first part of the code

Code: Select all

CLC
LDA #1 ; any odd value
ADC s+0
STA s+0
ADC s+1
STA s+1

has a cycle length of 65536, going through each 16 bit value exactly once before repeating. However, the random quality is poor, so this is followed by an output function to make it more random. In order to keep the property that each value appears exactly once, this extra output function must be invertible. Now, an EOR operation is invertible, if you know one of the operands, however, an ADC is only invertible if you also know the carry state before the ADC. Since the code above leaves the carry in a random state, we need to define it. That's what the ASL does, in a tricky way.

ASL followed by ADC #0 performs an 8 bit rotate left of the accumulator, and clears the carry. The rotate left is invertible, and helps with the randomness. In the code, there's no ADC #0, but ADC s+0, which does the same thing as ADC #0, but also adds s+0 as a bonus.

If you remove the ASL, there will be 256 values that appear twice in the 65536 cycle period, and 256 other values that don't appear at all.

[barrym95838]

Thank you, Arlet! At a net cost of ten bytes, VTLC02 now has a pseudo-random number generator that never gets stuck in a short cycle, and overall performance is slightly improved. I can't say that I fully understand it, but it acts like a pre-shuffled deck of 65536 unique cards ... the VTL program can "cut the deck" wherever it wants, but it can't reshuffle, and that's good enough for me, because shuffling is expensive, relatively speaking.

Code: Select all

rnd:
    clc             ; (accumulator = $27)
    adc  tick       ; pseudo-random number generator
    sta  tick       ;   with no short cycles,
    adc  tick+1     ;   courtesy of Arlet Ottens
    sta  tick+1     ;
    asl             ;
    adc  tick       ;
    pha             ;
    eor  tick       ;
    bra  getval4a   ; (spend ten clocks, save two bytes)
;;; stuff ;;;
getval4a:
    sta  1,x        ; store high-byte of term value
    pla             ;
getval5:
    sta  0,x        ; store low-byte of term value
    rts             ;

On entry, A=$27 and carry is set. Can you think of a way to use sbc instead of adc to help me eliminate the clc? My amateur attempts resulted in short cycles.

[BigEd]

Some investigations going on over on stardot
PRNG's experiment(s)
(Arlet's scheme is mentioned early in the thread)

Also perhaps notable, a reddit comment about shuffling a card deck.