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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
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:-- 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
|
|||
|
|||
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
|
|||
|
|||
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 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
|
|||
|
|||
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
|
|||
|
|||
RE: What are good PRNG for calculators?
(08-21-2014 04:28 PM)Thomas Klemm Wrote: This is from the Games Pac: 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
|
|||
|
|||
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, 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
|
|||
|
|||
RE: What are good PRNG for calculators? | |||
08-21-2014, 10:55 PM
Post: #10
|
|||
|
|||
RE: What are good PRNG for calculators?
(08-21-2014 09:56 PM)Paul Dale 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(08-21-2014 09:23 PM)Namir Wrote: How do you do bit shifting in the HP-25, HP-67, HP-41C? Code: + 2 MOD - John |
|||
08-21-2014, 11:54 PM
Post: #11
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
RE: What are good PRNG for calculators? | |||
08-22-2014, 06:20 AM
Post: #15
|
|||
|
|||
RE: What are good PRNG for calculators?
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 |
|||
08-22-2014, 01:45 PM
Post: #16
|
|||
|
|||
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
|
|||
|
|||
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. Listing for the HP-50G implementation? Namir |
|||
08-22-2014, 02:43 PM
Post: #18
|
|||
|
|||
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
|
|||
|
|||
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
|
|||
|
|||
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: