What are good PRNG for calculators?

[Namir]

In your opinion, what are very good algorithms for pseudo-random number generators (uniformly distributed) for programmable calculators? I am talking about algorithms that you and I can program ourselves to generate uniform random numbers between 0 and 1. So saying that the Rand# in the HP-15C is very good does not count, because it is already hardwired in the firmware.

Balancing between simplicity and efficiency (i.e good numeric distribution and long cycles) is very good!

Namir

[TomC]

See Knuth for algorithms and Pickover for testing (not with my specific sources right now).

TomC

[Thomas Klemm]

This is from the Games Pac:

LBL "RNDM"
RCL 00
9821
*
.211327
+
FRC
STO 00
END

Quote:Another interesting portion of this program is the random number generator:
r_n+1 = FRC (9821 × r_n + .211327)
This generator was developed by Don Malm as part of an HP-65 Users’ Library program. It passes the spectral test (Knuth, V.2, § 3.4) and, because its parameters satisfy Theorem A (op. cit., p. 15), it generates one million distinct random numbers between 0 and 1 regardless of the value selected for r₀.

-- ARITHMETIC TEACHER / HP-41C STANDARD APPLICATIONS

Cheers
Thomas

[Dieter]

(08-21-2014 03:25 PM)Namir Wrote:  Balancing between simplicity and efficiency (i.e good numeric distribution and long cycles) is very good!

In terms of simplicity it will not get much simpler than a good old linear congruential RNG, i.e. something like r_n+1 = (a · r_n + b) mod c. However, the cycle length obviously is limited.

So a good idea might be the combination of several RNGs of this kind. A well-known method using this approach is the Wichmann-Hill generator that was introduced in Applied Statistics, vol. 31 (1982). But caveat lector: the original paper included an error that was corrected in 1984. ;-) The cycle length of this RNG is approx. 7 · 10¹².

Dieter

[Thomas Klemm]

(08-21-2014 03:25 PM)Namir Wrote:  So saying that the Rand# in the HP-15C is very good does not count, because it is already hardwired in the firmware.

This Python program simulates the RAN# function of the HP-15C:

Code:

seed = 7365289446 # or any other number

def rand():
    global seed
    seed = (1574352261 * seed + 1017980433) % 10000000000
    return seed

Of course in the HP-15C the value will be e.g. 0.7365289446 instead.

Cheers
Thomas

PS: It's similar in the HP-48. How RAND Works

[Thomas Klemm]

(08-21-2014 06:35 PM)Dieter Wrote:  In terms of simplicity it will not get much simpler than a good old linear congruential RNG,

You might be interested in this paper: Xorshift RNGs. But they aren't suited well for programmable calculators.

[Namir]

(08-21-2014 04:28 PM)Thomas Klemm Wrote:  This is from the Games Pac:

LBL "RNDM"
RCL 00
9821
*
.211327
+
FRC
STO 00
END

Quote:Another interesting portion of this program is the random number generator:
r_n+1 = FRC (9821 × r_n + .211327)
This generator was developed by Don Malm as part of an HP-65 Users’ Library program. It passes the spectral test (Knuth, V.2, § 3.4) and, because its parameters satisfy Theorem A (op. cit., p. 15), it generates one million distinct random numbers between 0 and 1 regardless of the value selected for r₀.

-- ARITHMETIC TEACHER / HP-41C STANDARD APPLICATIONS

Cheers
Thomas

Thomas,

This algorithm is used in the RN label of the PPC ROM. The book "Enter" by Jean-Daniel Dodin does mention it too!

Namir

[Namir]

(08-21-2014 07:21 PM)Thomas Klemm Wrote:  

(08-21-2014 06:35 PM)Dieter Wrote:  In terms of simplicity it will not get much simpler than a good old linear congruential RNG,

You might be interested in this paper: Xorshift RNGs. But they aren't suited well for programmable calculators.

How do you do bit shifting in the HP-25, HP-67, HP-41C?

Namir

[Paul Dale]

(08-21-2014 09:23 PM)Namir Wrote:  How do you do bit shifting in the HP-25, HP-67, HP-41C?

Shift left: 2 *
Shift right: 2 / IP

The problem here is the exclusive or operations.


- Pauli

[John R. Graham]

(08-21-2014 09:56 PM)Paul Dale Wrote:  

(08-21-2014 09:23 PM)Namir Wrote:  How do you do bit shifting in the HP-25, HP-67, HP-41C?

Shift left: 2 *
Shift right: 2 / IP

The problem here is the exclusive or operations.

It would be quite slow, but you can do XOR a bit at a time with addition and modulus. If X and Y contain a single bit then

Code:

+ 2 MOD

leaves the XOR in X.

- John

[Namir]

I have been comparing several simple PRNGs for calculators. I conducted a series of long runs and found the following algorithms to do well:

1) u = frac(997 * u)
2) u = frac(GoldenRatio + u)^5) (it does better than frac(pi+u)^5).
3) u = Frac(u * 99821 + 0.211327)

Namir

[Gene]

I always use the 997 * RNG because it is shorter than the others.

Of course, if you're using the 41CL, then I use the ones Angel wrote into his ROMs. :-)

[Ángel Martin]

(08-22-2014 02:52 AM)Gene Wrote:  Of course, if you're using the 41CL, then I use the ones Angel wrote into his ROMs. :-)

Which (to demystify it) is just the same one referred above (used in the Games Pac and the PPC), plus a time-module based seed - that's the nice part - all conveniently stored in a buffer for repeat usage.

[Paul Dale]

(08-21-2014 10:55 PM)John R. Graham Wrote:  It would be quite slow, but you can do XOR a bit at a time with addition and modulus. If X and Y contain a single bit then

Code:

+ 2 MOD

leaves the XOR in X.

I thought of this method & have used it in the past, it would be very very slow.


- Pauli

[Pekis]

Hello,

On the ZX Spectrum was used this formula:
x = ( x * 75 ) mod 65537

See also
x = ( x * 279470273 ) mod 4294967291
http://en.wikipedia.org/wiki/Lehmer_rand..._generator

[John R. Graham]

(08-22-2014 02:52 AM)Gene Wrote:  I always use the 997 * RNG because it is shorter than the others.

I don't know where this originally came from, but it was described by HP at least as far back as the HP-67 user's guide.

On the "less than short" side, just for fun I implemented the Mersenne Twister on my HP 50g.

- John

[Namir]

(08-22-2014 01:45 PM)John R. Graham Wrote:  

(08-22-2014 02:52 AM)Gene Wrote:  I always use the 997 * RNG because it is shorter than the others.

I don't know where this originally came from, but it was described by HP at least as far back as the HP-67 user's guide.

On the "less than short" side, just for fun I implemented the Mersenne Twister on my HP 50g.

- John

Listing for the HP-50G implementation?

Namir

[John R. Graham]

I'll post this weekend. No connectivity kit at work.

- John

[Les Bell]

(08-21-2014 09:56 PM)Paul Dale Wrote:  The problem here is the exclusive or operations.

Exactly. I think Namir needs to define "good" in this context, as different PRNG algorithms tend to have different properties.

The linear congruential RNG's commonly used are fine for small simulations, Monte Carlo techniques, seeding games, etc. because they are a) simple and b) provide reasonable uniformity. But they're highly predictable.

Linear Feedback Shift Registers, which depend upon lots of XOR'ing, have the additional property of being much less predictable, which makes them ideal for cryptographic applications.

Fortunately, performing crypto on a scientific calculator is rarely required, and when it is done, it's rather like a singing dog - not remarkable because it's bad (slow), more remarkable that it's done at all.

[Marcus von Cube]

The TI SR-51(A) has a RAN# function that returns a two digit random number. I couldn't find more info about it but I have the feeling that it's not a pseudo random number generator but a real random number function. Can someone confirm this? To support my assumption, there is no seed function.