16 June 2024, 21:37 | #1 |
Registered User
Join Date: May 2013
Location: Kleppe / Norway
Posts: 273
|
Random-list generator code
My next little project is to bring to life a code-snip that does the following:Given an input number X (max 16 bits large unsigned number), and the program should generate a list of numbers from 0 to X, in random sequence.The generator should put the numbers into a buffer as 16bit binary entries.The seed can be taken from scan line position or another hardware register which changes a lot. I would like suggestions / algorithms to how the random number generator itself could be designed, for maximum speed when generating a big list.I don't mind wasting lots of memory or using a large data table(s) instead of using costly instructions like mulu or divu to lower execution time. Target is MC68000.
|
16 June 2024, 22:25 | #2 |
Registered User
Join Date: Dec 2010
Location: Athens/Greece
Age: 53
Posts: 727
|
|
16 June 2024, 22:38 | #3 |
Registered User
Join Date: Jun 2016
Location: europe
Posts: 1,076
|
Look up xorshift for a very fast and high quality 2^N rng. For arbitratry X:
Y= (smallest 2^N that's larger than X)-1; rnd &= Y; if (rnd > X) rnd -= X; If you need a not-high quality rng, this is what I use (also 2^N) when I need speed: Code:
; d6=const modifer, d7=seed/rnd (both should be very large numbers, use all 32 bits) add.l d6,d7 eor.l d6,d7 ; swap d7 ; highest speed, lowest accuracy (depends *heavily* on selection of modifier/seed), use rol instead if you need better accuracy rol.l #R,d7 ; pick R based on your speed/accuracy requirements (odds are better) ; rnd = extract lowest N bits from d7 |
17 June 2024, 08:24 | #4 |
Registered User
Join Date: May 2013
Location: Kleppe / Norway
Posts: 273
|
Thanks both, will check it out.
|
17 June 2024, 08:25 | #5 |
Registered User
Join Date: Jan 2019
Location: Germany
Posts: 3,370
|
Random number generators should not be picked at random. You find a good collection at Knuth "The Art of Programming, Volume 2: Numerical and Seminumerical Algorithms". Lots of things are known and are provable on the algorithms listed there, and I would recommend against picking some "hardware register" for it as its contents are all but random. You can use a date or so as random seed initializer. Is there a particular reason why this needs to be "so fast"? How often is it called, and how many random numbers do you need?For the random permutation problem, there is already an algorithm cited for Wikipedia that works on random exchange. It requires a random generator underneath. See the reference above for a good collection of well-studied algorithms.
|
17 June 2024, 10:58 | #6 | ||
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 48
Posts: 3,888
|
Indeed.
Quote:
Quote:
Xoshiro128++: https://prng.di.unimi.it/xoshiro128plusplus.c Alternatively, there's Xorshift: https://en.wikipedia.org/wiki/Xorshift |
||
17 June 2024, 12:45 | #7 | |
Registered User
Join Date: Aug 2010
Location: Germany
Posts: 537
|
Yes, but they are also quite well-documented and well-tested. They won't let you down when it comes to randomness and sequence cycle lengths, but the integer arithmetics performed do not necessarily amount to well-spent CPU time.
Quote:
|
|
17 June 2024, 12:54 | #8 | ||
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,366
|
Quote:
Quote:
|
||
17 June 2024, 13:31 | #9 |
Registered User
Join Date: Jun 2016
Location: europe
Posts: 1,076
|
That's why there are variations of xorshift (*, +, shiro, ...). And that's why I said "look up" and not "use" ;P. Assess your speed vs. accuracy requirements and choose accordingly.
If speed is a lot more important, improvise (like I did above with a simplified xorshift). |
17 June 2024, 14:01 | #10 |
Registered User
Join Date: Dec 2010
Location: Athens/Greece
Age: 53
Posts: 727
|
This is tricky as well. OP said 0...X, where x is variable. I've seen many times that the lowest N bits are the "least" random. (I can easily admit that I don't know the behavior of xorshift on the matter though)
I think in the general form you can't avoid the division. Code:
int r = xorshift32(&rng) / (RAND_MAX / x + 1); |
17 June 2024, 14:14 | #11 | |
Registered User
Join Date: Jan 2008
Location: Warsaw/Poland
Age: 56
Posts: 2,070
|
Quote:
add.l A0,D7 or add.l (A0),D7 or add.l (A0)+,D7 ? |
|
17 June 2024, 14:18 | #12 | |
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,366
|
Quote:
However, another issue of xorshift is that it does not have good avalanche effect (i.e. a seed with few 1 will lead to a number with few 1). It is possible if you consider the result as a fixed-point number between 0 and 1, and simply multiply. |
|
17 June 2024, 14:18 | #13 |
Registered User
Join Date: Jun 2016
Location: europe
Posts: 1,076
|
The idea was to avoid a very slow division (due to X != 2^N), so instead I'd use a bitwise and to extract a sufficient number of bits (so their value is now lower than 2*X), and then cap them to X with a simple compare/sub. I don't think that position of those bits matters, but yeah, you could ultimately extract from the top, or at 16+ (swap), etc.
|
17 June 2024, 14:39 | #14 | |
Registered User
Join Date: Jun 2016
Location: europe
Posts: 1,076
|
Quote:
- d6 = modifier; d7 = seed; - repeat: d7 = rol((d6+d7)^d6,R); rnd = d7&1023; // for example - store d7 if you want to continue from the same rnd afterwards There's no need for additional external data (add (a0)+?), modifier and seed should be chosen "carefully" (don't use small or simple numbers) and you can keep going for a long while. Now if you're suggesting to use output address (a0?) as a modifier, the problem with that is if you are using non-absolute addresses, every time you start your code you will get a different series of random numbers. And we want pseudo-random, so you can easily repeat the series on demand by using the same seed. |
|
17 June 2024, 14:46 | #15 |
Registered User
Join Date: Jan 2008
Location: Warsaw/Poland
Age: 56
Posts: 2,070
|
No, my idea is/was to add total unknown value to generated result.
Last edited by Don_Adan; 17 June 2024 at 14:57. |
17 June 2024, 14:51 | #16 |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 48
Posts: 3,888
|
|
17 June 2024, 14:52 | #17 |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 48
Posts: 3,888
|
|
17 June 2024, 14:59 | #18 |
Registered User
Join Date: Jan 2008
Location: Warsaw/Poland
Age: 56
Posts: 2,070
|
|
17 June 2024, 17:05 | #19 | |
son of 68k
Join Date: Nov 2007
Location: Lyon / France
Age: 51
Posts: 5,366
|
Quote:
I'm doing that at initial seeding step only, though. Else it may be constant during the program and not useful. |
|
17 June 2024, 17:47 | #20 |
Registered User
Join Date: Feb 2017
Location: Denmark
Posts: 1,276
|
Is this just an academic exercise (which is fine of course!) or do you have an intended use case?
As is noted on previously linked Wikipedia page on Fisher-Yates shuffle, you actually need a very large internal RNG state even for very small N if you want to be able to generate all possible permutations. The example for a deck of cards (N=52) requiring > 225 bits of internal state is quite instructive. Presumably this is not an issue, and you won't be using an A500 to host an online casino. I ask, because having a concrete instance can usually bring forth interesting discussion / new ideas. For example the also mentioned xor-shift PRNG is based on LFSRs (https://en.wikipedia.org/wiki/Linear...shift_register), and for the case where N is some 2**M-1, and you just want some random looking permutation, a Galois LFSR can be extremely fast (~20 cycles/number). The "fizzlefade" screen in Wolfenstein is one such example (https://fabiensanglard.net/fizzlefade/). Obviously not useful for say a card game, but for some usecases (like a demo) it might come in handy as you can easily calculate the next value without having to store a big array in memory. |
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
Thread Tools | |
Similar Threads | ||||
Thread | Thread Starter | Forum | Replies | Last Post |
[ASM] Random number generator | LeCaravage | Coders. Asm / Hardware | 7 | 18 September 2018 15:32 |
Blitz Seed Random Number Generator | Ze Emulatron | Coders. Blitz Basic | 3 | 26 November 2017 11:08 |
asm code for a simple random generator | jotd | Coders. Asm / Hardware | 7 | 15 September 2017 09:14 |
VBCC 09d - bug in code generator ? | Asman | Coders. C/C++ | 7 | 04 January 2016 13:46 |
Help needed!!Random octal numbers generator(asm) | sheryn88 | Coders. General | 6 | 01 August 2010 07:19 |
|
|