What are good PRNG for calculators?
08-21-2014, 03:25 PM (This post was last modified: 08-21-2014 03:27 PM by Namir.)
Post: #1
 Namir Senior Member Posts: 1,052 Joined: Dec 2013
What are good PRNG for calculators?
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
08-21-2014, 04:19 PM
Post: #2
 TomC Senior Member Posts: 315 Joined: Dec 2013
RE: What are good PRNG for calculators?
See Knuth for algorithms and Pickover for testing (not with my specific sources right now).

TomC
08-21-2014, 04:28 PM (This post was last modified: 08-21-2014 04:58 PM by Thomas Klemm.)
Post: #3
 Thomas Klemm Senior Member Posts: 2,078 Joined: Dec 2013
RE: What are good PRNG for calculators?
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:
rn+1 = FRC (9821 × rn + .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 r0.
-- ARITHMETIC TEACHER / HP-41C STANDARD APPLICATIONS

Cheers
Thomas
08-21-2014, 06:35 PM (This post was last modified: 08-21-2014 06:38 PM by Dieter.)
Post: #4
 Dieter Senior Member Posts: 2,397 Joined: Dec 2013
RE: What are good PRNG for calculators?
(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 rn+1 = (a · rn + 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 · 1012.

Dieter
08-21-2014, 07:05 PM
Post: #5
 Thomas Klemm Senior Member Posts: 2,078 Joined: Dec 2013
RE: What are good PRNG for calculators?
(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
08-21-2014, 07:21 PM
Post: #6
 Thomas Klemm Senior Member Posts: 2,078 Joined: Dec 2013
RE: What are good PRNG for calculators?
(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.
08-21-2014, 09:22 PM
Post: #7
 Namir Senior Member Posts: 1,052 Joined: Dec 2013
RE: What are good PRNG for calculators?
(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:
rn+1 = FRC (9821 × rn + .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 r0.
-- 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
08-21-2014, 09:23 PM
Post: #8
 Namir Senior Member Posts: 1,052 Joined: Dec 2013
RE: What are good PRNG for calculators?
(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
08-21-2014, 09:56 PM (This post was last modified: 08-21-2014 09:56 PM by Paul Dale.)
Post: #9
 Paul Dale Senior Member Posts: 1,837 Joined: Dec 2013
RE: What are good PRNG for calculators?
(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
08-21-2014, 10:55 PM
Post: #10
 John R. Graham Member Posts: 76 Joined: Dec 2013
RE: What are good PRNG for calculators?
(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
08-21-2014, 11:54 PM
Post: #11
 Namir Senior Member Posts: 1,052 Joined: Dec 2013
RE: What are good PRNG for calculators?
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
08-22-2014, 02:52 AM
Post: #12
 Gene Moderator Posts: 1,375 Joined: Dec 2013
RE: What are good PRNG for calculators?
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. :-)
08-22-2014, 05:32 AM
Post: #13
 Ángel Martin Senior Member Posts: 1,443 Joined: Dec 2013
RE: What are good PRNG for calculators?
(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.

"To live or die by your own sword one must first learn to wield it aptly."
08-22-2014, 06:01 AM
Post: #14
 Paul Dale Senior Member Posts: 1,837 Joined: Dec 2013
RE: What are good PRNG for calculators?
(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
08-22-2014, 06:20 AM
Post: #15
 Pekis Member Posts: 157 Joined: Aug 2014
RE: What are good PRNG for calculators?
Hello,

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

x = ( x * 279470273 ) mod 4294967291
http://en.wikipedia.org/wiki/Lehmer_rand..._generator
08-22-2014, 01:45 PM
Post: #16
 John R. Graham Member Posts: 76 Joined: Dec 2013
RE: What are good PRNG for calculators?
(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
08-22-2014, 02:16 PM
Post: #17
 Namir Senior Member Posts: 1,052 Joined: Dec 2013
RE: What are good PRNG for calculators?
(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
08-22-2014, 02:43 PM
Post: #18
 John R. Graham Member Posts: 76 Joined: Dec 2013
RE: What are good PRNG for calculators?
I'll post this weekend. No connectivity kit at work.

- John
08-24-2014, 01:06 AM
Post: #19
 Les Bell Member Posts: 188 Joined: Dec 2013
RE: What are good PRNG for calculators?
(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.

--- Les
[http://www.lesbell.com.au]
08-25-2014, 05:15 PM
Post: #20
 Marcus von Cube Senior Member Posts: 760 Joined: Dec 2013
RE: What are good PRNG for calculators?
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.

Marcus von Cube
Wehrheim, Germany
http://www.mvcsys.de
http://wp34s.sf.net
http://mvcsys.de/doc/basic-compare.html
 « Next Oldest | Next Newest »

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