A Random Question

[DavidM]

(06-10-2017 05:18 AM)Paul Dale Wrote:  To get an unbiased output you need to deal with the issue of the number of random values (here 10^12) modulo the size of the integer you want is not zero.

Thanks for the explanation, that helps to clarify what you meant to do in your code (yes, I saw the warning ). I believe you probably meant to use IQUOT where you currently have IDIV. When I first looked at the code, I thought IDIV was a typo for IDIV2, which returns both the quotient and the remainder. So I didn't catch the full meaning the first time around.

(06-10-2017 05:18 AM)Paul Dale Wrote:  If you've not picked an algorithm for the shuffle yet, use Fisher-Yates. This would be well suited to sys-RPL implementation. Deconstruct the list onto the stack, loop n-1 times swapping the chosen value with the nth stack level.

Fisher-Yates (more specifically the "modern algorithm" version) is exactly the approach I had already used, and my previous implementation simply used the equivalent of "RAND n * IP" to select the random swap index. My revision was an attempt to speed up the process by keeping the random index selection in the integer domain and doing the math involved in Saturn code instead of SysRPL.

The extra range check for the seed will slow things down, but obviously not for every iteration. So there's still likely to be a performance boost, just not as much as I had originally hoped.

(06-10-2017 12:57 PM)John Keith Wrote:  As a side note, since you are going to the trouble of writing SysRPL/assembly code for random number generation, it occurs to me that the HP50's internal PRNG code is beginning to look a bit old-fashioned. The XORSHIFT+ algorithm seems to be fast and robust, and looks fairly easy to implement in Saturn assembly.

At one point I played around with an alternative method that used a combination of TIMER bits with the current CRC, and it was the fastest thing I tested. While the results appeared nicely shuffled, I realized that I lacked the knowledge and tools to validate them. Then there's also the issue of non-repeatability... it was a good exercise, but not something I'd pursue. I ultimately decided to stick with RAND for the very reason that I didn't want to reinvent the PRNG wheel (and fall into all the traps inherent with that). XORSHIFT+ does look interesting, but I'll put that on my list of things to revisit later.