6502.org • View topic - Random-number generation

View unanswered posts | View active topics

Board index » 6502.org Users Forum » Programming

All times are UTC

Random-number generation

Page 14 of 17

[ 245 posts ]

Go to page Previous 1 ... 11, 12, 13, 14, 15, 16, 17 Next

Previous topic | Next topic

Author

Message

Arlet

Post subject: Re: Random-number generation

Posted: Fri Apr 21, 2023 11:31 pm

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

Alex1 wrote:

Arlet, you conclude that practrand is not good on 1 KB sets but there is no warning in the README file.

Here's what it says in the documentation:

Quote:

(PractRand attempts to set its false-positive rate for "FAIL" messages
low enough to make it unlikely that any user will ever see a false-
positive from it. The effectiveness of this strategy is limited by
two things: 1. I did say "attempts" to set the false-positive rate
that low. In practice, for the standard test set, I think I've even
succeeded. The expanded test set, and tests not used in either,
don't necessarily meet the same standards though. 2. users rightly
pay attention to the number of less extreme result evaluations as
well, as a kind of informal done-by-eye metatest, for which there is
no quantified false-positive rate.)

If I run the standard test set for 1 kB on /dev/random or chacha(8), the erratic behavior at 1 kB disappears.

The documentation also gives this advice:

Quote:

Most failures on the core tests (other thatn BRank) should have
started small and gotten steadily worse as more bytes were tested
until failure was reached. Thus, if "FAIL" was reported at 2**36
bytes then at the previous results summary (at 2**35 bytes) there
should have been some kind of anomaly on the same subtest, maybe a
"suspicious" or "very suspicious" test result. If there was no
preceding warning and the failure was particularly extreme, that may
mean that the RNG somehow worsened its behavior in some way shortly
before the failure was reported, similar to exhausting the cycle
length, but perhaps in some way detectable to only one of the tests
in PractRand.

Top

Arlet

Post subject: Re: Random-number generation

Posted: Sat Apr 22, 2023 4:43 am

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

BigEd wrote:

It feels clear to me that testing the randomness of small chunks of data is more likely to come up with unusual situations.
If I make 10 coin tosses, the number of heads will vary from 5 by quite a bit, quite often. If I make 1000 coin tosses, the number of heads will vary from 500 by proportionally less.

Yes, and you have to keep in mind that the we're not just looking for number of heads & tails, but also at certain patterns. If we have a coin that goes H,T,H,T,H,T, in alternating fashion, we would still like to reject it. If a coins goes HHTHTHHTTTHHTHTTTH then we also want to reject it, because it's just a 3 bit counter: HHT/HTH/HTT/THH/THT/TTH. Imagine you have 1024 different coins, and toss them all 10 times in a row, and you end up with 1024 different patterns, all equally probable, which of those 1024 patterns would you reject? Well, none of them, of course, because they are just normal random possibilities. The more advanced a randomness tester is, the more different regular patterns it looks for, but that also means it could get more false positives, because each pattern is something that can also happen statistically in a perfect random generator.

The solution is to test with more data, and see if a pattern persists for much longer than expected.

Top

Alex1

Post subject: Re: Random-number generation

Posted: Sat Apr 22, 2023 10:45 pm

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

Practrand is a bad tester of random number generator on large data sets.The more data there is to test, the less it detects things.

Here is the test i did.

I created a 8GB file with all 0x00:

8 GB
8 589 934 592 bytes

I encrypted this file with AES 128 and a random key.

I encrypted this result file with AES 128 and an other key. I named this file : file1.

Tests with this file:

Quote:

type file1 | RNG_test.exe stdin8

Quote:

RNG_test using PractRand version 0.94
RNG = RNG_stdin8, seed = unknown
test set = core, folding = standard (8 bit)

rng=RNG_stdin8, seed=unknown
length= 32 megabytes (2^25 bytes), time= 2.3 seconds
no anomalies in 93 test result(s)

rng=RNG_stdin8, seed=unknown
length= 64 megabytes (2^26 bytes), time= 5.4 seconds
no anomalies in 99 test result(s)

rng=RNG_stdin8, seed=unknown
length= 128 megabytes (2^27 bytes), time= 10.4 seconds
no anomalies in 108 test result(s)

rng=RNG_stdin8, seed=unknown
length= 256 megabytes (2^28 bytes), time= 17.8 seconds
Test Name Raw Processed Evaluation
[Low1/8]Gap-16:B R= -4.1 p =1-1.8e-3 unusual
...and 117 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 512 megabytes (2^29 bytes), time= 33.4 seconds
Test Name Raw Processed Evaluation
[Low1/8]DC6-9x1Bytes-1 R= -4.3 p =1-3.8e-3 unusual
...and 125 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 62.9 seconds
no anomalies in 135 test result(s)

rng=RNG_stdin8, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 123 seconds
no anomalies in 144 test result(s)

rng=RNG_stdin8, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 234 seconds
no anomalies in 151 test result(s)

Quote:

type file1 | rng_test stdin8 -te 1 -tlmin 10 -tlmax 50 -tlmaxonly

Quote:

RNG_test using PractRand version 0.94
RNG = RNG_stdin8, seed = unknown
test set = expanded, folding = standard (8 bit)

rng=RNG_stdin8, seed=unknown
length= 1 kilobyte (2^10 bytes), time= 0.3 seconds
Test Name Raw Processed Evaluation
FPF-14+6/64:all R= +13.2 p~= 1e-3 unusual
...and 15 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 2 kilobytes (2^11 bytes), time= 1.1 seconds
Test Name Raw Processed Evaluation
DC6-9x1Bytes-1 R= +6.0 p = 0.013 unusual
...and 20 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 4 kilobytes (2^12 bytes), time= 2.0 seconds
no anomalies in 29 test result(s)

rng=RNG_stdin8, seed=unknown
length= 8 kilobytes (2^13 bytes), time= 3.0 seconds
no anomalies in 52 test result(s)

rng=RNG_stdin8, seed=unknown
length= 16 kilobytes (2^14 bytes), time= 4.7 seconds
no anomalies in 62 test result(s)

rng=RNG_stdin8, seed=unknown
length= 32 kilobytes (2^15 bytes), time= 6.4 seconds
no anomalies in 76 test result(s)

rng=RNG_stdin8, seed=unknown
length= 64 kilobytes (2^16 bytes), time= 8.2 seconds
no anomalies in 91 test result(s)

rng=RNG_stdin8, seed=unknown
length= 128 kilobytes (2^17 bytes), time= 10.0 seconds
Test Name Raw Processed Evaluation
DC6-9x1Bytes-1 R= -4.7 p =1-5.0e-3 unusual
...and 101 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 256 kilobytes (2^18 bytes), time= 11.8 seconds
Test Name Raw Processed Evaluation
[Low1/8]FPF-14+6/16:all R= +6.7 p = 2.8e-4 unusual
...and 114 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 512 kilobytes (2^19 bytes), time= 13.7 seconds
no anomalies in 129 test result(s)

rng=RNG_stdin8, seed=unknown
length= 1 megabyte (2^20 bytes), time= 15.5 seconds
no anomalies in 142 test result(s)

rng=RNG_stdin8, seed=unknown
length= 2 megabytes (2^21 bytes), time= 17.5 seconds
Test Name Raw Processed Evaluation
[Low1/8]BCFN(0+1,13-8,T) R= +12.3 p = 4.6e-4 unusual
...and 155 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 4 megabytes (2^22 bytes), time= 19.6 seconds
no anomalies in 169 test result(s)

rng=RNG_stdin8, seed=unknown
length= 8 megabytes (2^23 bytes), time= 22.0 seconds
no anomalies in 183 test result(s)

rng=RNG_stdin8, seed=unknown
length= 16 megabytes (2^24 bytes), time= 25.0 seconds
no anomalies in 198 test result(s)

rng=RNG_stdin8, seed=unknown
length= 32 megabytes (2^25 bytes), time= 29.0 seconds
no anomalies in 212 test result(s)

rng=RNG_stdin8, seed=unknown
length= 64 megabytes (2^26 bytes), time= 34.8 seconds
no anomalies in 225 test result(s)

rng=RNG_stdin8, seed=unknown
length= 128 megabytes (2^27 bytes), time= 44.0 seconds
Test Name Raw Processed Evaluation
[Low1/8]DC6-6x2Bytes-1 R= +5.6 p = 2.0e-3 unusual
...and 239 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 256 megabytes (2^28 bytes), time= 61.5 seconds
no anomalies in 254 test result(s)

rng=RNG_stdin8, seed=unknown
length= 512 megabytes (2^29 bytes), time= 93.1 seconds
Test Name Raw Processed Evaluation
[Low1/8]DC6-9x1Bytes-1 R= -4.3 p =1-3.8e-3 unusual
...and 267 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 158 seconds
no anomalies in 287 test result(s)

rng=RNG_stdin8, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 281 seconds
no anomalies in 304 test result(s)

rng=RNG_stdin8, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 516 seconds
no anomalies in 318 test result(s)

Then i modified file1
At offset 0x3BA5BB24 i replaced 10 bytes with 0x00 :
00 00 00 00 00 00 00 00 00 00
and i did the test again and the 10 zero bytes are not detected :

Quote:

type file1 | RNG_test.exe stdin8

Quote:

RNG_test using PractRand version 0.94
RNG = RNG_stdin8, seed = unknown
test set = core, folding = standard (8 bit)

rng=RNG_stdin8, seed=unknown
length= 32 megabytes (2^25 bytes), time= 2.2 seconds
no anomalies in 93 test result(s)

rng=RNG_stdin8, seed=unknown
length= 64 megabytes (2^26 bytes), time= 4.4 seconds
no anomalies in 99 test result(s)

rng=RNG_stdin8, seed=unknown
length= 128 megabytes (2^27 bytes), time= 8.6 seconds
no anomalies in 108 test result(s)

rng=RNG_stdin8, seed=unknown
length= 256 megabytes (2^28 bytes), time= 17.0 seconds
Test Name Raw Processed Evaluation
[Low1/8]Gap-16:B R= -4.1 p =1-1.8e-3 unusual
...and 117 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 512 megabytes (2^29 bytes), time= 31.9 seconds
Test Name Raw Processed Evaluation
[Low1/8]DC6-9x1Bytes-1 R= -4.3 p =1-3.8e-3 unusual
...and 125 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 58.6 seconds
no anomalies in 135 test result(s)

rng=RNG_stdin8, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 116 seconds
no anomalies in 144 test result(s)

rng=RNG_stdin8, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 224 seconds
no anomalies in 151 test result(s)

Quote:

type file1 | rng_test stdin8 -te 1 -tlmin 10 -tlmax 50 -tlmaxonly

Quote:

RNG_test using PractRand version 0.94
RNG = RNG_stdin8, seed = unknown
test set = expanded, folding = standard (8 bit)

rng=RNG_stdin8, seed=unknown
length= 1 kilobyte (2^10 bytes), time= 0.2 seconds
Test Name Raw Processed Evaluation
FPF-14+6/64:all R= +13.2 p~= 1e-3 unusual
...and 15 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 2 kilobytes (2^11 bytes), time= 1.1 seconds
Test Name Raw Processed Evaluation
DC6-9x1Bytes-1 R= +6.0 p = 0.013 unusual
...and 20 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 4 kilobytes (2^12 bytes), time= 1.9 seconds
no anomalies in 29 test result(s)

rng=RNG_stdin8, seed=unknown
length= 8 kilobytes (2^13 bytes), time= 2.9 seconds
no anomalies in 52 test result(s)

rng=RNG_stdin8, seed=unknown
length= 16 kilobytes (2^14 bytes), time= 4.6 seconds
no anomalies in 62 test result(s)

rng=RNG_stdin8, seed=unknown
length= 32 kilobytes (2^15 bytes), time= 6.3 seconds
no anomalies in 76 test result(s)

rng=RNG_stdin8, seed=unknown
length= 64 kilobytes (2^16 bytes), time= 8.1 seconds
no anomalies in 91 test result(s)

rng=RNG_stdin8, seed=unknown
length= 128 kilobytes (2^17 bytes), time= 9.9 seconds
Test Name Raw Processed Evaluation
DC6-9x1Bytes-1 R= -4.7 p =1-5.0e-3 unusual
...and 101 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 256 kilobytes (2^18 bytes), time= 11.8 seconds
Test Name Raw Processed Evaluation
[Low1/8]FPF-14+6/16:all R= +6.7 p = 2.8e-4 unusual
...and 114 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 512 kilobytes (2^19 bytes), time= 13.6 seconds
no anomalies in 129 test result(s)

rng=RNG_stdin8, seed=unknown
length= 1 megabyte (2^20 bytes), time= 15.5 seconds
no anomalies in 142 test result(s)

rng=RNG_stdin8, seed=unknown
length= 2 megabytes (2^21 bytes), time= 17.5 seconds
Test Name Raw Processed Evaluation
[Low1/8]BCFN(0+1,13-8,T) R= +12.3 p = 4.6e-4 unusual
...and 155 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 4 megabytes (2^22 bytes), time= 19.6 seconds
no anomalies in 169 test result(s)

rng=RNG_stdin8, seed=unknown
length= 8 megabytes (2^23 bytes), time= 22.0 seconds
no anomalies in 183 test result(s)

rng=RNG_stdin8, seed=unknown
length= 16 megabytes (2^24 bytes), time= 24.9 seconds
no anomalies in 198 test result(s)

rng=RNG_stdin8, seed=unknown
length= 32 megabytes (2^25 bytes), time= 28.8 seconds
no anomalies in 212 test result(s)

rng=RNG_stdin8, seed=unknown
length= 64 megabytes (2^26 bytes), time= 34.8 seconds
no anomalies in 225 test result(s)

rng=RNG_stdin8, seed=unknown
length= 128 megabytes (2^27 bytes), time= 44.7 seconds
Test Name Raw Processed Evaluation
[Low1/8]DC6-6x2Bytes-1 R= +5.6 p = 2.0e-3 unusual
...and 239 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 256 megabytes (2^28 bytes), time= 62.9 seconds
no anomalies in 254 test result(s)

rng=RNG_stdin8, seed=unknown
length= 512 megabytes (2^29 bytes), time= 95.8 seconds
Test Name Raw Processed Evaluation
[Low1/8]DC6-9x1Bytes-1 R= -4.3 p =1-3.8e-3 unusual
...and 267 test result(s) without anomalies

rng=RNG_stdin8, seed=unknown
length= 1 gigabyte (2^30 bytes), time= 169 seconds
no anomalies in 287 test result(s)

rng=RNG_stdin8, seed=unknown
length= 2 gigabytes (2^31 bytes), time= 300 seconds
no anomalies in 304 test result(s)

rng=RNG_stdin8, seed=unknown
length= 4 gigabytes (2^32 bytes), time= 546 seconds
no anomalies in 318 test result(s)

I did the same on a 8MB file and 10 zeros at offset 3BA5BB -> no detection
I did the same on a 1MB file and 10 zeros at offset 3BA5B -> no detection
I did the same on a 1MB file and 20 zeros at offset 3BA5B -> no detection
I did the same on a 1MB file and 30 zeros at offset 3BA5B -> detection with "midly suspicious" or "very suspicious"

Quote:

Here are 3 files AES 128 modified at 0x3BA5B :
file1: 10 zero bytes -> no detection
file2: 20 zero bytes -> no detection
file3: 30 zero bytes -> detection

Attachment:

random.zip [3 MiB]
Downloaded 41 times

I did the same test on 8GB file.

Test on 8GB at offset 0x3BA5BB24
-20 zero bytes - >no detection
-30 zero bytes -> unusual
-40 zero bytes -> very suspicious

Other people also find that Practrand is not a good detector :
https://crypto.stackexchange.com/questi ... -generator

I remind you that arlet-minimal FAIL on 8kb:

Quote:

state: .byte $00,$00,$00,$00,$01
length= 8 kilobytes (2^13 bytes), time= 6.3 seconds
Test Name Raw Processed Evaluation
[Low1/8]FPF-14+6/64:all R= +49.9 p~= 6e-23 FAIL !!
...and 51 test result(s) without anomalies

and arlet-big is MIDLY SUSPICIOUS on 8kb :

Quote:

with s: .byte $00,$00,$00,$00,$00,$01

length= 8 kilobytes (2^13 bytes), time= 6.3 seconds
Test Name Raw Processed Evaluation
FPF-14+6/16:all R= +10.3 p = 3.2e-5 mildly suspicious
[Low1/8]FPF-14+6/64:all R= +16.3 p~= 1e-4 unusual
...and 50 test result(s) without anomalies

Top

wayfarer

Post subject: Re: Random-number generation

Posted: Sat May 13, 2023 3:54 am

Joined: Sun Mar 19, 2023 2:04 pm
Posts: 137
Location: about an hour outside of Springfield

the C specification for random(0)/rand() and srand() all require that "This value is library-dependent, but is guaranteed to be at least 32767 on any standard library implementation."
https://cplusplus.com/reference/cstdlib/RAND_MAX/

in most cases a 4GB 32-bit random number is more than sufficient.

Further, in the C specification, the previously uninitialized function rand() must return a value as if it were set with srand(1), and a value of srand(X) must always return the same value for X.

Quote:

For every different seed value used in a call to srand, the pseudo-random number generator can be expected to generate a different succession of results in the subsequent calls to rand.

Two different initializations with the same seed will generate the same succession of results in subsequent calls to rand.

so a deterministic approach is required here by the C language spec.

personally, Id prefer something based off the RTC and then Binary Rotated based on some other factor unlikely to be reproducible or able to be manipulated easily externally. an RTC, timer and values on a port are much more approachable than say a Cesium can in your laptop (you can get these now, atomic decay clocks in IC form... super $$). however, this kind of non-deterministic signal is not desirable in many cases.

Statistic is from the word stochastic or 'stick arrow'. A stick would be placed and arrows fired at it, their distances averaged to determine the accuracy of the archer.
Immediately you must consider two methods here, if the arrows are left in place each shot, or removed. If the playing field is open, and all possible positions are available, hitting the same spot is likely the more arrows are fired.

So that there are repetitions or patterns in a sample of several billion is no reason to discount the 'randomness' of the method. I had a friend, a retired TV repairman much my elder. My old buddy and I would hang out and bum smokes all night at his place. He wrote in GW-Basic and was trying to win some math prize or another. One of the programs he wrote looked for the largest string of repeating digits in Pi. I saw like 4x4s, and 3x5s and I think 5x7s or something. It was decades ago, both of these people long deceased now; even Pi has sets of repeating digits, the same 'number' in a row. What matters, is can it be manipulated or predicted.

I prefer non-deterministic randomness myself and I have great interest in this topic. I was reading on a chip with an RNG that used XORs repeatedly to generate random bits. I want to include the RTC, and since one of them I am using uses BCD, I want to do something with that and ROL or some other step with the BIT op and creation of 2-bit fuzz.

@Arlet, your method seems simplistic at first, though vaguely familiar... is this a 'Twister'?
it appears adequate for a C90 implementation however. I did spot someone saying there is a bit of a pattern/error in a Seed value of "01", and this needs to be verified or addressed in the case of 'rand()' being the same as 'srand(1)' if uninitialized or set. I intend to look at this further myself; though if it is not a concern or easily altered; your method is plenty for a spec C random. Thank you for putting this up on Git, it is quite eloquent... I swear I have seen this somewhere before. :lol:

Top

Arlet

Post subject: Re: Random-number generation

Posted: Sat May 13, 2023 5:26 am

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

wayfarer wrote:

@Arlet, your method seems simplistic at first, though vaguely familiar... is this a 'Twister'?
it appears adequate for a C90 implementation however. I did spot someone saying there is a bit of a pattern/error in a Seed value of "01", and this needs to be verified or addressed in the case of 'rand()' being the same as 'srand(1)' if uninitialized or set. I intend to look at this further myself; though if it is not a concern or easily altered; your method is plenty for a spec C random. Thank you for putting this up on Git, it is quite eloquent... I swear I have seen this somewhere before. :lol:

I have no idea if this method has a name. I haven't seen it before, but, while I have looked at a bunch of different techniques, I did not do an exhaustive search to see if this idea has been used before. The ideas are borne out of necessity because the 6502 has so few good instructions for random generation. I just played around with whatever few instructions are available, and testing the results.

By the way, I'm still working on this, but mostly it's my PC doing the work trying all kinds of combinations in a script and seeing which works best. The problem is when you get to a stage where it is reasonably good, and it takes an hour to reject it.

Top

wayfarer

Post subject: Re: Random-number generation

Posted: Sun May 14, 2023 3:00 am

Joined: Sun Mar 19, 2023 2:04 pm
Posts: 137
Location: about an hour outside of Springfield

looking over it more, there are the xor of a LFSR, and these incremented steps, like you are moving the frame of the XOR rather than moving the contents, I'll have to look it over more, and I am just getting the hang of 65-asm, much less whatever shorthand some of the code you posted is that doesnt load in the emulator Im using... I was able to test in the BBC-Micro emulator site though, it works 'well enough' as a starting point for many things. Certainly on my list of references moving forward.

Is your design basically an inside out LSFR?
(edit) at the end there, you do have that ASL...
my curiosity is academic; what you have seems to work fine for basic noise, or to determine which direction a spaceship might zig or zag in a game. +1

Top

Arlet

Post subject: Re: Random-number generation

Posted: Sun May 14, 2023 4:30 am

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

No, it's nothing like an LFSR. The structure always consists of a basic core from a chain of ADCs. The behavior of the ADC chain is more like a LCG. If you replace the initial constant with 1, it is actually an exact LCG. The output of the ADC chain is then mixed around to improve randomness. There's no structure to the mixer. The overall style of having these two parts is similar to the design of PCG, which has some nice explanation here: https://www.pcg-random.org/

Top

wayfarer

Post subject: Re: Random-number generation

Posted: Sun May 14, 2023 2:03 pm

Joined: Sun Mar 19, 2023 2:04 pm
Posts: 137
Location: about an hour outside of Springfield

Oh cool!!
so I was digging on wikipedia and this didnt come up yesterday.
this was not taught in the classes I took and reading that site (especially) the part on the paper, it seems it slipped through the cracks of the academic publishing world. Given there seems to be some drama there with the earlier paper, this all tracks. Tons of interconnected links on 4-5 PRNG methods, none linked directly to the LCG page.

I did finally find the page on wikipedia, thank you, this is a really cool and very fast method.
I am no cryptologist, merely interested in maths and art so a method this simple and this useful is very beautiful.

+1

Top

Alex1

Post subject: Re: Random-number generation

Posted: Tue May 16, 2023 1:30 pm

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

wayfarer wrote:

looking over it more, there are the xor of a LFSR, and these incremented steps, like you are moving the frame of the XOR rather than moving the contents

LFSRs have been studied mathematically so that there is no short cycle, if you change the XOR of an LFSR, you will get short cycles.

By the way, @Arlet did you find a better random tester rather than practrand ?

Top

wayfarer

Post subject: Re: Random-number generation

Posted: Tue May 16, 2023 1:38 pm

Joined: Sun Mar 19, 2023 2:04 pm
Posts: 137
Location: about an hour outside of Springfield

Alex1 wrote:

wayfarer wrote:

looking over it more, there are the xor of a LFSR, and these incremented steps, like you are moving the frame of the XOR rather than moving the contents

yes I completely misread his code; I had thought he was offsetting the address by +1, +2, +3, ... and then doing the XOR.
Rather he is adding to the values and XORing after each iteration there. It is a very eloquent method I pulled up some articles on, I want to see if it satisfies a free-standing C implementation myself.

Top

sark02

Post subject: Re: Random-number generation

Posted: Mon May 29, 2023 9:04 pm

Joined: Tue Nov 10, 2015 5:46 am
Posts: 230
Location: Kent, UK

A fun diversion for this topic: Retro Game Mechanics Explained, on youtube, just posted a video on Pac Man's RNG.

https://www.youtube.com/watch?v=eFP0_rkjwlY

Top

Arlet

Post subject: Re: Random-number generation

Posted: Tue May 30, 2023 6:52 am

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

Here's a new random number generator. It produces 32 bit outputs, and is a few cycles shorter than my previous version. It does use a bit more RAM for the state. There's 8 bytes of state, and 4 bytes of output. The interesting part is that the code sequence has been generated semi-automatically. I made a program that tries out various permutations, checks the random output quality using PractRand, and then makes small modifications to the code in an attempt to find better results. For this run, I only let it use the ADC instruction to see how far that would get it.

This version passes PractRand (using "stdin") up to 256GB of data, produces some warnings at 512GB, and then fails at 1TB.

Code takes 118 cycles (excluding JSR/RTS overhead), or 29.5 cycles/byte.

Code:

        ; s0-s7 contains state
        ; o3-o0 contains output
        CLC
        LDA #$45
        ADC s0
        STA s0
        ADC s1
        STA s1
        ADC s2
        STA s2
        ADC s3
        STA s3
        ADC s4
        STA s4
        ADC s5
        STA s5
        LDA s3
        ADC s6
        STA s6
        ADC s3
        STA o1
        ADC s4
        STA o2
        ADC s6
        STA s6
        ADC o1
        STA o1
        ADC s7
        STA s7
        ADC o2
        STA o2
        ADC s6
        STA s6
        ADC s5
        STA o3
        ADC s0
        ADC o1
        STA o1 
        ADC s6
        STA s6 
        ADC s2
        STA o0
        RTS

Owlet code

Top

barrym95838

Post subject: Re: Random-number generation

Posted: Tue May 30, 2023 8:05 am

Joined: Sun Jun 30, 2013 10:26 pm
Posts: 1948
Location: Sacramento, CA, USA

Arlet, would you be willing to do me a small favor and take a few minutes to focus your brilliance on a 16-bit output? I need to do something for VTLC02, but I don't presently have sufficient skill or tooling. White Flame's LFSR routine is the back-up plan. My goals are to look at least somewhat "sprinkly" and guarantee that Super Star Trek won't get stuck in an infinite loop waiting for a sub-range that can never arrive.

Code:

) FIND RANDOM HOLE X IN QUADRANT R
.=!
X='/1024
#=:R+X)=0*.
#=8610

_________________
Got a kilobyte lying fallow in your 65xx's memory map? Sprinkle some VTL02C on it and see how it grows on you!

Mike B. (about me) (learning how to github)

Top

Arlet

Post subject: Re: Random-number generation

Posted: Tue May 30, 2023 8:33 am

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

Yes, I was already thinking about doing a 16 bit version.

Top

Arlet

Post subject: Re: Random-number generation

Posted: Tue May 30, 2023 10:22 am

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

Here's a first shot at a 16 bit output. Uses 6 bytes of state, 2 bytes of output, 80 cycles (ex JSR/RTS). Minimum period of 4GB. It's a bit slower than the White Flame LFSR code, but that really only produces 1 new bit per call.

It's possible to optimize in various directions. Using more/less ZP, code size, cycles, or period/quality. Let me know what you care about most.

Code:

CLC
LDA #$45
ADC seed+0
STA seed+0
ADC seed+1
STA seed+1
ADC seed+2
STA seed+2
ADC seed+3
STA seed+3
LDA seed+4
ADC seed+2
STA outp+0
ADC seed+4
STA seed+4
ADC seed+3
STA outp+1
ADC seed+0
ADC outp+0
STA outp+0
ADC seed+4
ROL A
ROL A
STA seed+4
ADC outp+1
STA outp+1
ADC seed+5
STA seed+5
RTS

Owlet code

Top

Page 14 of 17

[ 245 posts ]

Go to page Previous 1 ... 11, 12, 13, 14, 15, 16, 17 Next

Board index » 6502.org Users Forum » Programming

All times are UTC

Who is online

Users browsing this forum: No registered users and 11 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum