![]() |
![]() |
#21 |
Registered User
![]() Join Date: May 2013
Location: Kleppe / Norway
Posts: 274
|
In short, the use case is to randomize a list of mod and other music files, before playback in that random order.
I initially though of generating a random number list, which could be used to index a file-list, and while this perhaps is over the top for this use case, I want it to be able to handle a list of tens of thousands of entries if needed. What I want is this: Produce a random sequence of numbers within a given range, without any duplicate numbers. If this can be done without generating a list (just one-shot call the rng for each new file), and the sequence can be continued from session to session by saving the internal state of the rng for each session, I am fine with that. If however a random number sequence file needs to be generated to ensure no duplicates, the routine should be as efficient as possible, I do not need the rng to be perfect. Considering the 32 bit xorshift in post #6, if called enough times after the seed has been initialized, it will return all the numbers from 1 to 4.294.967.295 without any duplicates? Suppose you only want numbers from 1 to 10000, without any duplicates? Can you do that with some math tricks, or do you need to use a predefined table and Fisher/Yates shuffle it? For shuffle you can always re-call the rng if the given number is a duplicate due to limiting. |
![]() |
![]() |
#22 |
Computer Nerd
Join Date: Sep 2007
Location: Rotterdam/Netherlands
Age: 48
Posts: 3,958
|
Also, LCGs need big multiplies (96+ bits) to be really good.
Last edited by Thorham; 18 June 2024 at 00:46. |
![]() |
![]() |
#23 | |
Registered User
Join Date: Jan 2019
Location: Germany
Posts: 3,490
|
Quote:
IOWs, the random generator needs neither to be very good, nor does it need to be very fast. The rand implementation in your C library, or even the one from amiga.lib might be good enough for something simple. It is "by tradition" not a very good generator, but for this it should really be sufficient. To get every time a new sequence, just provide a good seed to it, e.g. the current date should do it. Don't create problems were there are none. |
|
![]() |
![]() |
#24 | |
Registered User
Join Date: Jan 2008
Location: Warsaw/Poland
Age: 56
Posts: 2,125
|
Quote:
For your case, I will create empty 10000 bytes long file. And with and.l or/and lsr.l I will get any number up to 10000. Later I will check if this numbered byte in this file/memory is empty. If empty then this is new value/module. And addq.b #1,(A0,D0.L) (if you need any stats) or st (A0,D0.L) used (if you dont need stats) If not empty then addq.l #1,D0 and repeat check. Of course you must remember about loop if D0=10000 then clear D0. Edit. And if I remember right some file systems dont like too many files in same directory. |
|
![]() |
![]() |
#25 |
Registered User
Join Date: Jan 2019
Location: Germany
Posts: 3,490
|
Huh, why? Note that something different is asked for, namely not a set of random numbers, but a random permutation of a finite set of objects. That is, for N objects there are N! possible permutations, and each should happen equally likely. So it is random, but on a different probability space (that is, for a random permutation, the likelyness of finding object k at position i is not independent from the likelyness of the populations of the objects at other positions, but this wasn't really asked for.).
|
![]() |
![]() |
#26 |
Registered User
Join Date: Apr 2021
Location: Sydney
Posts: 8
|
Generate the numbers 0 to 99 in an array
First iteration: using your rng, pick a random number N between 0 and 99. swap the number at location 0 with the number at location N Second iteration: using your rng, pick a random number N between 1 and 99. swap the number at location 1 with the number at location N Third iteration: using your rng, pick a random number N between 2 and 99. swap the number at location 2 with the number at location N etc Repeat 100 times Now your array has the numbers 0-99 in it, permuted in a random order. Last edited by jimshaw; 18 June 2024 at 13:39. |
![]() |
![]() |
#27 |
Registered User
Join Date: Jun 2016
Location: europe
Posts: 1,096
|
Well, the fact that you want a very high rate of non-duplicates chages the things significantly.
Needing only one random every once in a while helps a lot, because that process can be made as complex as needed to meet your requirements as best as possible. You also mentioned shuffling, but the problem is you will be adding new songs, so that complicates it. So... LGCs is what you normally want, they have already been mentioned by meynaf, but for such a small max_rand (~10k, and even if you add a few bits of depth to that) the math fails and they don't work that well. That's why all the rand() stuff in c libraries is using much larger max, 32 bits or so. So, I would just use the standard srand()/rand() with a simple extendable bitfield (Don Adan said bytes, but a single bit is sufficient) and a direction flag. You generate a random, take top N bits (for 10k, that's 14 bits, but you can also determine that dynamically), calculate index, and check the bitfield if bit is set. If so, retry up to say 50 times. If that fails and you picked 50 duplicates, pick the first unset bit from either the start or the end (depending on direction flag, so when you append new songs with very few left to play you don't end up playing those in a row) and invert the flag. Or you could do a bisection to make it more non-linear, or... In a state file you track the last random (unmodified, use it with srand() next time), dir_flag, num_played (to know when to reset, you could even do it earlier because newly added songs probably won't be randomized that good) and a bitfield. |
![]() |
![]() |
#28 |
Registered User
Join Date: Jan 2008
Location: Warsaw/Poland
Age: 56
Posts: 2,125
|
This is not my program.
But if I understand correctly, he want this for 68000. Then bytes are better/faster than bits for handling. 1. For me bytes are easy changable/expandable for adding/removing favorite mods from list. 2. Addq.b #1,(A0,D0.L) can be used as extra random routine too. After 256 calls/accesess it will be again 0, and this module can be played again. |
![]() |
![]() |
#29 | |
Registered User
Join Date: Jan 2008
Location: Warsaw/Poland
Age: 56
Posts: 2,125
|
Quote:
I told already im not expert. But calling f.e $ffffffff times random routine and receiving $ffffffff different results is for me similar random like addq.l #1,D0. Only in different rotation. |
|
![]() |
![]() |
#30 | |
Registered User
Join Date: Sep 2019
Location: Finland
Posts: 378
|
Quote:
![]() |
|
![]() |
![]() |
#31 |
Registered User
Join Date: Jun 2016
Location: europe
Posts: 1,096
|
Yeah, but speed is apparently not that important because he needs a single random:
- when song ends, - when user clicks on next (at most a couple of times a second if they recognize song name and want to skip it immediately). I think these are all of his use cases. So, with a bitfield you have 8x lower memory requirement for tracking. And I/O times, well about the same since you can use fseek() and only update what's been changed, which I admit *would be* more straightforward with bytes. But you could just keep it simple and write the whole thing in one go since it would only be a couple of KBs. |
![]() |
![]() |
#32 |
Registered User
Join Date: Jan 2008
Location: Warsaw/Poland
Age: 56
Posts: 2,125
|
Then perhaps I will use different method for handling similar case.
One ascii list (editable) with favourite user mods with full paths (with filename) ready to load. And second small file (up to 10000 bytes long for this case) with random access handling. D0 is known, then searching D0 times for new line inside ascii list file. Of course ascii list can be big, but in old days I never seen favorite mods list greater than 200-300 mods. And of course I mean about loading mods from different disks/directory etc. Not only from one directory. |
![]() |
![]() |
#33 |
Registered User
![]() Join Date: May 2013
Location: Kleppe / Norway
Posts: 274
|
I appreciate all suggestions, I will try and implement some of them to test out.
|
![]() |
Currently Active Users Viewing This Thread: 1 (0 members and 1 guests) | |
Thread Tools | |
![]() |
||||
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 |
|
|