RPL and 42S Random Number Generator

[Thomas Okken]

(Splitting this topic from the List Commands Library for 50g thread into its own...)

(10-04-2017 04:22 AM)Thomas Okken Wrote:  

(10-02-2017 08:58 AM)Werner Wrote:  eg. the early Random Number generator used for the 41c used
c=.211327, a=9821, m=1. (This is from memory, but I think I'm right ;-)

You're absolutely right, and I know that one from memory as well. :-D

That is also the RNG that I use in Free42. This thread got me thinking, though: maybe I should replace that RNG? Even if its properties are generally OK, the RNG in the real HP-42S generates numbers with 12 significant digits, while the one from the HP-41C manual generates numbers with only 6 significant digits.

And now I discover that the HP-42S RAN function behaves exactly like RAND in the 48G! Give it the same seed, and the same numbers pop out.

The behavior for seed 0 is different, but still, it looks like I've stumbled upon another way to make Free42 a bit truer to the original. Neat!

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 HP-42S.

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 15-digit internal number before returning it.

The RNG takes a 15-digit 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 15-digit 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 15-digit 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 boo-boo by HP, is there any other explanation why these functions work the way they do?

[ttw]

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 Box-Muller 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 rare-event sampling. With a cycle of 10^12, it's rare to get the 0 or 1 (but may crash a program if it happens.)

[toml_12953]

(10-04-2017 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!

[grsbanks]

(11-28-2017 04:32 AM)toml_12953 Wrote:  Oh boy! Does this mean we should be seeing another DM42 firmware version soon? Woo hoo!

I have little doubt that Free42 2.0.7 will make it into the DM42's firmware. Right now, however, the guys are concentrating on other things.

[Thomas Okken]

(11-28-2017 01:28 PM)grsbanks Wrote:  

(11-28-2017 04:32 AM)toml_12953 Wrote:  Oh boy! Does this mean we should be seeing another DM42 firmware version soon? Woo hoo!

I have little doubt that Free42 2.0.7 will make it into the DM42's firmware. Right now, however, the guys are concentrating on other things.

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 platform-specific: calculator key shortcut for Windows, p => PI and g => GTO shortcuts for Windows, Linux, and Mac, fixing menu icons for Android, and a work-around 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.