MCODE: random numbers

[RobertM]

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) 
seed = FRC((seed * 9821) + .211327)

to get a random number between 1 <= ran <= n. I perform these calcs using the OS system calls (MP2-10, INTFRC), and because I'm using binary numbers (not BCD) I also have to convert to/from binary to bcd using OS system calls (BCDBIN and GENNUM).

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.

[John Keith]

XORSHIFT+ should meet your needs. It may need some testing to make sure there are no unwanted side-effects of the 41's 56-bit word size.

[RobertM]

(04-20-2019 10:12 PM)John Keith Wrote:  XORSHIFT+ should meet your needs. It may need some testing to make sure there are no unwanted side-effects of the 41's 56-bit 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?

[Albert Chan]

(04-20-2019 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 non-biased 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/fast-r...shuffling/

Non-biased 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.

[RobertM]

(04-21-2019 01:35 AM)Albert Chan Wrote:  If you don't mind tiny non-biased 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/fast-r...shuffling/

Non-biased 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.

Albert, Thanks for this information. Just what I was looking for!

[Mark Power]

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.