RPL and 42S Random Number Generator

11222017, 07:16 PM
Post: #1




RPL and 42S Random Number Generator
(Splitting this topic from the List Commands Library for 50g thread into its own...)
(10042017 04:22 AM)Thomas Okken Wrote:(10022017 08:58 AM)Werner Wrote: eg. the early Random Number generator used for the 41c used In Free42 2.0.7, I changed the implementation of the RAN and SEED functions according to https://groups.google.com/forum/m/#!msg/...tzMtZhlGoJ. Apart from their names, the 42S RAN and SEED functions are identical to their RPL counterparts, RAND and RDZ, the only remaining difference being the starting seed after a cold start, which is 999500333083533 in the RPL calculators, and 2787 in the HP42S. While I'm pleased to have been able to implement RAN and SEED so that they behave exactly like their counterparts on the original calculator, there is one thing that bothers me, namely, the way RAN behaves near zero. As was pointed out earlier in this thread, the RPL RAND function never returns zero (and neither does RAN on the 42S), which seems odd, given that the calculator's manual indicates that that functions returns numbers 0 <= x < 1 (apart from one place where the 48S AUR says 0 <= x <= 1, which is wrong but doesn't have anything to do with the behavior near zero). The 42S manual mentions the range of RAN twice, and states 0 <= x < 1 in both places. The reason why the RPL RAND and the 42S RAN functions never return zero is because of the way they truncate the 15digit internal number before returning it. The RNG takes a 15digit integer, multiplies it by 2851130928467 (a prime), takes the result of that multiplication modulo 10^15, keeps that as the next seed, and chops off the three least significant digits, and divides that result by 10^15, giving a uniformly distributed result that is >= 0 and < 1... except: when that final number is < 0.1, it only chops off the last two digits, and when it is < 0.01, it only chops off the last one digit, and when it is < 0.001, it doesn't chop off any digits... And because the least significant digit of the 15digit seed is never zero (it is always 1, 3, 7, or 9), this means that the number that is returned is never zero. This doesn't seem to make sense. The result of this algorithm is that RAN or RAND never return zero, which isn't necessary given that the documentation states that zero is a possible result, and it means that the distribution in the intervals [0, 0.001), [0.001, 0.01), and [0.01, 0.1) are all different, and don't match the distribution in [0.1, 1). As long as you truncate the result from RAN or RAND to 12 digits after the decimal, this is all fine... but it seems to me like you shouldn't have to. I think this behavior is wrong. RAN and RAND should just chop off the last 3 digits of the 15digit seed, divide the result by 10^15, and thus return a truly uniformly distributed number on the inverval [0, 1). Other than this being a rare mathematical booboo by HP, is there any other explanation why these functions work the way they do? 

11282017, 02:59 AM
Post: #2




RE: RPL and 42S Random Number Generator
For technical reasons, it's nice if a PRNG doesn't generate 0 or 1 exactly. The quick generation of exponential variates, y=A*Ln(u), and the BoxMuller method for normal variates, r=Sqrt(2Ln(u1)) and t=2*pi*u2 with x=r*Sin(t) and y=r*Cos(t) for independent pairs of normal, is faster if no tests for 0 or 1 are necessary in inner loops.
For binary computers, I always used the odd multiples of twice the base. For base 10, just odd numbers works with proper scaling. End cases near 0 or 1 should be sampled with special methods; these are usually covered in papers on rareevent sampling. With a cycle of 10^12, it's rare to get the 0 or 1 (but may crash a program if it happens.) 

11282017, 04:32 AM
Post: #3




RE: RPL and 42S Random Number Generator
(10042017 04:22 AM)Thomas Okken Wrote: In Free42 2.0.7, I changed the implementation of the RAN and SEED functions according to https://groups.google.com/forum/m/#!msg/...tzMtZhlGoJ. Oh boy! Does this mean we should be seeing another DM42 firmware version soon? Woo hoo! Tom L French phrases you rarely hear: "trop de beurre" (too much butter) 

11282017, 01:28 PM
Post: #4




RE: RPL and 42S Random Number Generator  
11282017, 03:40 PM
(This post was last modified: 11282017 03:44 PM by Thomas Okken.)
Post: #5




RE: RPL and 42S Random Number Generator
(11282017 01:28 PM)grsbanks Wrote:(11282017 04:32 AM)toml_12953 Wrote: Oh boy! Does this mean we should be seeing another DM42 firmware version soon? Woo hoo! Also note that the only changes in 2.0.7 that are relevant to DM42 are the new RNG, and one very minor cosmetic bug fix. Everything else is platformspecific: calculator key shortcut for Windows, p => PI and g => GTO shortcuts for Windows, Linux, and Mac, fixing menu icons for Android, and a workaround for display glitches with certain skins in iOS. It's such a grab bag of minor random (ha!) stuff that I would have happily waited some more to release it, but since it had been three months since the last release, it seemed about time. 

« Next Oldest  Next Newest »

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