MCODE: random numbers

04202019, 09:43 PM
Post: #1




MCODE: random numbers
While playing around with 41C MCODE, I've found a need for generating random numbers. Currently, I use the classic
Code: ran = INT(seed * n) I've recently been pondering the inefficiency of all that and wondering if there is a better way to implement random numbers in MCODE using binary directly. Of course, the 41C CPU doesn't have multiplication or division as part of it's repertoire, and I know that it can be simulated with shifting, repeated addition and repeated subtraction, but I haven't gone down those rabbit holes very far. I was considering doing some form of XORSHIFT algorithm for the random number generation, and then (and this is the part I'm really unsure of) some smart version of shifting and subtraction to do the modulo portion, and wondering if anyone has experience or ideas about random number generation in binary, particularly without multiply/divide? I'm considering this for "simulation" usage, so I don't need a super long period, or cryptographically safe algorithm. 

04202019, 10:12 PM
Post: #2




RE: MCODE: random numbers
XORSHIFT+ should meet your needs. It may need some testing to make sure there are no unwanted sideeffects of the 41's 56bit word size.


04202019, 10:40 PM
Post: #3




RE: MCODE: random numbers
(04202019 10:12 PM)John Keith Wrote: XORSHIFT+ should meet your needs. It may need some testing to make sure there are no unwanted sideeffects of the 41's 56bit word size. Thanks John. I had looked at that, and wasn't sure I wanted to figure out the proper shift values (23/17/26) for a 56 bit word. I was actually thinking of just the simple XORSHIFT32 (inside a 56 bit word). Any thoughts on the how to algorithmically implement the "modulo(n)" portion without a div instruction? 

04212019, 01:35 AM
Post: #4




RE: MCODE: random numbers
(04202019 10:40 PM)RobertM Wrote: Any thoughts on the how to algorithmically implement the "modulo(n)" portion without a div instruction? If you don't mind tiny nonbiased random modulo, it can be done with a multiply and a shift. see first version of random_bounded() in https://lemire.me/blog/2016/06/30/fastr...shuffling/ Nonbiased modulo is not much harder, see the second version. This required some random number samples to be rejected. Also, I had conversations with Lemire about how divisionless random code work. On the last post, there is a link to a paper about it. 

04212019, 02:03 AM
Post: #5




RE: MCODE: random numbers
(04212019 01:35 AM)Albert Chan Wrote: If you don't mind tiny nonbiased random modulo, it can be done with a multiply and a shift. Albert, Thanks for this information. Just what I was looking for! 

05032019, 09:21 PM
Post: #6




RE: MCODE: random numbers
I wrote this up for HPCC Datafile Volume 6 Number 8 December 1987. It might be of some use.
My apologies for the scan, but it seems like it is the only electronic copy of the article that I have. 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)