MCODE: random numbers - Printable Version +- HP Forums ( https://www.hpmuseum.org/forum)+-- Forum: HP Calculators (and very old HP Computers) ( /forum-3.html)+--- Forum: General Forum ( /forum-4.html)+--- Thread: MCODE: random numbers ( /thread-12838.html) |

MCODE: random numbers - RobertM - 04-20-2019 09:43 PM
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. RE: MCODE: random numbers - John Keith - 04-20-2019 10:12 PM
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. RE: MCODE: random numbers - RobertM - 04-20-2019 10:40 PM
(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? RE: MCODE: random numbers - Albert Chan - 04-21-2019 01:35 AM
(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-random-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. RE: MCODE: random numbers - RobertM - 04-21-2019 02:03 AM
(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. Albert, Thanks for this information. Just what I was looking for! RE: MCODE: random numbers - Mark Power - 05-03-2019 09:21 PM
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. |