Threaded Mode | Linear Mode

John R. Graham · (This post was last modified: 09-01-2014 07:26 PM by John R. Graham.)

(08-22-2014 02:16 PM)Namir Wrote:
(08-22-2014 01:45 PM)John R. Graham Wrote: ...On the "less than short" side, just for fun I implemented the Mersenne Twister on my HP 50g.

Listing for the HP-50G implementation?

Namir

Attached. Sorry for the delay. Short operating instructions:

Run Start to create the state variable structure.
Run SeedN or SeedT one or more times to seed the PRNG. SeedN takes a numeric argument but SeedT fetches a little bit of real entropy from the TICKS variables and uses that as a seed. You can seed the PRNG up to 624 times, which completely fills out the state variable, but typically you would seed it once, or just a few times.
Run Init to fully initialize the state variable and prepare the PRNG for use.
Use MtRnB or MtRnR to retrieve pseudo-random numbers. MtRnR returns traditional HP pseudo-random numbers (0 < n < 1) with 32 bits of precision. MtRnB returns the native 32-bit binary numbers that Mersenne Twister produces.

This implementation has been tested against the Math::Random::MT Perl library available from CPAN and demonstrated to produce identical results through 5,000 iterations.

- John

ttw · 09-04-2014, 04:41 AM

The appropriate PRNG for a calculator depends on the problem being solved. Computing an integral is quite different from playing a game or trying to encrypt something.

John R. Graham · 09-06-2014, 05:55 PM

When do you think it's inappropriate to use a really good PRNG? The only contraindication I can think of that is potentially valid is if the resource requirements and/or execution time is onerous on the platform.

- John

ttw · 09-06-2014, 06:03 PM

(09-06-2014 05:55 PM)John R. Graham Wrote: When do you think it's inappropriate to use a really good PRNG? The only contraindication I can think of that is potentially valid is if the resource requirements and/or execution time is onerous on the platform.

- John

A quasi-random generator is never worse when evaluating a (Riemann) integral. This is in terms of error-bounds rather than error estimates. Of course, QRNGs are useless (in general) for cryptography or in other cases where non-predictability is needed (in a gaming machine, for example.)

It's a bit more work to use QRNGs but the payoff can be big. The analysis is more like that of using traditional integration formulas.

John R. Graham · 09-06-2014, 07:05 PM

Interesting. What form does the payoff come in?

- John

jdimijian · 11-05-2014, 11:02 AM

(08-21-2014 07:05 PM)Thomas Klemm Wrote:
(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

Hi Thomas,

I'm so glad to find these 2 figures for the first time on the web ! 1017980433 and 1574352261.
I have a HP11C (now, I use an emulator on my iPhone) and I searched in the late 80's how the RAN function was generated. I finished to find an algorithm (not this you are using, but doing partial additions) and revealing these 2 figures.
I have programmed it in Turbo Pascal and used this as a Benchmark programm for the PCs (I was interested by numeric simulations).
Today, when I need a rand function, I always use this agorithm :-)

And you, where and how did you find it ?

Regards.

Joseph.

Thomas Klemm · 11-05-2014, 05:05 PM

(11-05-2014 11:02 AM)jdimijian Wrote: Hi Thomas,

I'm so glad to find these 2 figures for the first time on the web ! 1017980433 and 1574352261.
(...)
And you, where and how did you find it ?

Not affiliated with HP but I used the trace produced by the Nonpareil emulator of the HP-15C. IIRC you have to build the project with the correct settings. Then you can enable it via Debug -> ❐ Trace.
The output is huge but there's the assembler instruction lc to load a constant. Here's the part where 1574352261 is loaded:

Code:

 06120: 0120 lc 1                                  

cycle  2122  P=b q=4 carry=0  stat=.........9....  

 a=00000000000000 b=02592332694000 c=f1000000000000

 06121: 0520 lc 5                                  

cycle  2123  P=a q=4 carry=0  stat=.........9....  

 a=00000000000000 b=02592332694000 c=f1500000000000

 06122: 0720 lc 7                                  

cycle  2124  P=9 q=4 carry=0  stat=.........9....  

 a=00000000000000 b=02592332694000 c=f1570000000000

 06123: 0420 lc 4                                  

cycle  2125  P=8 q=4 carry=0  stat=.........9....  

 a=00000000000000 b=02592332694000 c=f1574000000000

 06124: 0320 lc 3                                  

cycle  2126  P=7 q=4 carry=0  stat=.........9....  

 a=00000000000000 b=02592332694000 c=f1574300000000

 06125: 0520 lc 5                                  

cycle  2127  P=6 q=4 carry=0  stat=.........9....  

 a=00000000000000 b=02592332694000 c=f1574350000000

 06126: 0220 lc 2                                  

cycle  2128  P=5 q=4 carry=0  stat=.........9....  

 a=00000000000000 b=02592332694000 c=f1574352000000

 06127: 0220 lc 2                                  

cycle  2129  P=4 q=4 carry=0  stat=.........9....  

 a=00000000000000 b=02592332694000 c=f1574352200000

 06130: 0620 lc 6                                  

cycle  2130  P=3 q=4 carry=0  stat=.........9....  

 a=00000000000000 b=02592332694000 c=f1574352260000

 06131: 0120 lc 1                                  

cycle  2131  P=2 q=4 carry=0  stat=.........9....  

 a=00000000000000 b=02592332694000 c=f1574352261000

And then I tried to figure out from the code and the rest of the trace what's going on. Fortunately it turned out not to be very complicated. On the basis of my posts it took me about two hours.

But I was not the first one to find these numbers:
Le Compte est bon - The Total Is Right - Numbers

Code:

*&---------------------------------------------------------------------*

*&      Form  HP11C_RAND                                               *

*&---------------------------------------------------------------------*

FORM hp11c_rand  USING value(p_lim_haute) TYPE i

                 CHANGING p_tirage  TYPE i.

  CONSTANTS : kincr TYPE p LENGTH 10 VALUE '1017980433',

              kbase TYPE p LENGTH 10 VALUE '1574352261',

              k10e10 TYPE p LENGTH 10 VALUE '10000000000'.

  DATA : lseed TYPE i.

  IF next = 0.

    IF ppartie = 0.

      CALL FUNCTION 'GENERAL_GET_RANDOM_INT'

        EXPORTING

          range  = 100000000

        IMPORTING

          random = lseed.

      next = lseed.

    ELSE.

      next = ppartie * 10000.

    ENDIF.

  ENDIF.

  next = ( next * kbase + kincr ) MOD k10e10.

  p_tirage = TRUNC( next / k10e10 * ( p_lim_haute + 1 ) ).

ENDFORM.                    " HP11C_RAND

How did you find these numbers?

Cheers
Thomas

Namir · 11-05-2014, 08:23 PM

(11-05-2014 05:05 PM)Thomas Klemm Wrote:
(11-05-2014 11:02 AM)jdimijian Wrote: Hi Thomas,

I'm so glad to find these 2 figures for the first time on the web ! 1017980433 and 1574352261.
(...)
And you, where and how did you find it ?

Not affiliated with HP but I used the trace produced by the Nonpareil emulator of the HP-15C. IIRC you have to build the project with the correct settings. Then you can enable it via Debug -> ❐ Trace.
The output is huge but there's the assembler instruction lc to load a constant. Here's the part where 1574352261 is loaded:

Code:

06120: 0120 lc 1 cycle 2122 P=b q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1000000000000 06121: 0520 lc 5 cycle 2123 P=a q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1500000000000 06122: 0720 lc 7 cycle 2124 P=9 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1570000000000 06123: 0420 lc 4 cycle 2125 P=8 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574000000000 06124: 0320 lc 3 cycle 2126 P=7 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574300000000 06125: 0520 lc 5 cycle 2127 P=6 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574350000000 06126: 0220 lc 2 cycle 2128 P=5 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574352000000 06127: 0220 lc 2 cycle 2129 P=4 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574352200000 06130: 0620 lc 6 cycle 2130 P=3 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574352260000 06131: 0120 lc 1 cycle 2131 P=2 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574352261000
And then I tried to figure out from the code and the rest of the trace what's going on. Fortunately it turned out not to be very complicated. On the basis of my posts it took me about two hours.

But I was not the first one to find these numbers:
Le Compte est bon - The Total Is Right - Numbers

Code:

*&---------------------------------------------------------------------* *& Form HP11C_RAND * *&---------------------------------------------------------------------* FORM hp11c_rand USING value(p_lim_haute) TYPE i CHANGING p_tirage TYPE i. CONSTANTS : kincr TYPE p LENGTH 10 VALUE '1017980433', kbase TYPE p LENGTH 10 VALUE '1574352261', k10e10 TYPE p LENGTH 10 VALUE '10000000000'. DATA : lseed TYPE i. IF next = 0. IF ppartie = 0. CALL FUNCTION 'GENERAL_GET_RANDOM_INT' EXPORTING range = 100000000 IMPORTING random = lseed. next = lseed. ELSE. next = ppartie * 10000. ENDIF. ENDIF. next = ( next * kbase + kincr ) MOD k10e10. p_tirage = TRUNC( next / k10e10 * ( p_lim_haute + 1 ) ). ENDFORM. " HP11C_RAND

How did you find these numbers?

Cheers
Thomas

According to the literature the modulo number should be 2^P or 2^P-1 for some P value. My guess is that using 10^Q would produce poor values.

Namir

Gilles · 11-05-2014, 09:37 PM

Here is a small program to "display" random numbers on the screen of the HP PRIME...

Code:

EXPORT PRNG()  

BEGIN

  //R:=FP(9821*R+0.211327);

  //R:=FP((PI+R)^5);

  //R:=FP(997*R);

  R:=FP(123*R);

END;

EXPORT PRNG_DSP(A)

BEGIN

 RECT();

 FOR I:=1 TO A DO

  PIXON_P(320*PRNG,240*PRNG);

 END;

 FREEZE;

END;

This program can't assure you that your PRNG program is a good one, but it can show you that it is bad ;D for example FP(123*R)

Don't forget to initialise R with a 0.xxxxxxx number , then :

PRNG_DSP(10000)

or TIME(PRNG_DSP(10000)) to evaluate the complexity of the algorithm

brouhaha · 11-05-2014, 09:51 PM

(08-25-2014 05:15 PM)Marcus von Cube Wrote: 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.

I expect it's a PRNG. There's no RNG hardware in the 51, so the only source of "random" numbers would be timing of key presses, and they can't get enough bits of entropy from a single key press for a two digit number. During a running program, using RAN# repeately would have no entropy input, so even if they time keypresses it would only be useful as a seed.

If the RAN# doesn't give the same results after each power-up, that could be due to not initializing the storage for the PRNG, which would act as a semi-random seed, though the entropy content would be very low.

Thomas Klemm · 11-06-2014, 12:06 AM

(11-05-2014 08:23 PM)Namir Wrote: According to the literature the modulo number should be 2^P or 2^P-1 for some P value.

[citation needed]

Quote:My guess is that using 10^Q would produce poor values.

These numbers fulfill the three requirements of the Hull-Dobell Theorem:

c = 1017980433 and m = 10000000000 are relatively prime
a - 1 = 1574352260 is divisible by all prime factors of m = 10000000000: 2 and 5
a - 1 = 1574352260 = 4*393588065 is a multiple of 4 if m = 10000000000 is a multiple of 4.

Thus we can conclude to have maximal period.

Cheers
Thomas

jdimijian · 11-06-2014, 09:36 AM

(11-05-2014 05:05 PM)Thomas Klemm Wrote:
(11-05-2014 11:02 AM)jdimijian Wrote: Hi Thomas,

I'm so glad to find these 2 figures for the first time on the web ! 1017980433 and 1574352261.
(...)
And you, where and how did you find it ?

Not affiliated with HP but I used the trace produced by the Nonpareil emulator of the HP-15C. IIRC you have to build the project with the correct settings. Then you can enable it via Debug -> ❐ Trace.
The output is huge but there's the assembler instruction lc to load a constant. Here's the part where 1574352261 is loaded:

Code:

06120: 0120 lc 1 cycle 2122 P=b q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1000000000000 06121: 0520 lc 5 cycle 2123 P=a q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1500000000000 06122: 0720 lc 7 cycle 2124 P=9 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1570000000000 06123: 0420 lc 4 cycle 2125 P=8 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574000000000 06124: 0320 lc 3 cycle 2126 P=7 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574300000000 06125: 0520 lc 5 cycle 2127 P=6 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574350000000 06126: 0220 lc 2 cycle 2128 P=5 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574352000000 06127: 0220 lc 2 cycle 2129 P=4 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574352200000 06130: 0620 lc 6 cycle 2130 P=3 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574352260000 06131: 0120 lc 1 cycle 2131 P=2 q=4 carry=0 stat=.........9.... a=00000000000000 b=02592332694000 c=f1574352261000
And then I tried to figure out from the code and the rest of the trace what's going on. Fortunately it turned out not to be very complicated. On the basis of my posts it took me about two hours.

But I was not the first one to find these numbers:
Le Compte est bon - The Total Is Right - Numbers

Code:

*&---------------------------------------------------------------------* *& Form HP11C_RAND * *&---------------------------------------------------------------------* FORM hp11c_rand USING value(p_lim_haute) TYPE i CHANGING p_tirage TYPE i. CONSTANTS : kincr TYPE p LENGTH 10 VALUE '1017980433', kbase TYPE p LENGTH 10 VALUE '1574352261', k10e10 TYPE p LENGTH 10 VALUE '10000000000'. DATA : lseed TYPE i. IF next = 0. IF ppartie = 0. CALL FUNCTION 'GENERAL_GET_RANDOM_INT' EXPORTING range = 100000000 IMPORTING random = lseed. next = lseed. ELSE. next = ppartie * 10000. ENDIF. ENDIF. next = ( next * kbase + kincr ) MOD k10e10. p_tirage = TRUNC( next / k10e10 * ( p_lim_haute + 1 ) ). ENDFORM. " HP11C_RAND

How did you find these numbers?

Cheers
Thomas

LOL ! The program extract that you have found is mine, it's written in ABAP (SAP development language)and as I told you, I use it every time I need random function.
It took me several years to find the algorithm, I was knowing nothing about these aglorithms and there was no Internet at this time ;-)
I was able to progress and find because I could fix the seed, I realized very soon that between 2 runs, the last digit (that is hidden but can appear with f-prefix) was incremented by 3. I explored this fact and progressively found all the stuff (without guessing that there is a simple multiplication !).
But today, knowing the existing algorthms, and having 2 or 3 successive random numbers, we can easyly retreive the different numbers.
Thanks for your attention Thomas.

Best regards.

Joseph.

Thomas Klemm · 11-06-2014, 08:03 PM

(11-06-2014 09:36 AM)jdimijian Wrote: But today, knowing the existing algorthms, and having 2 or 3 successive random numbers, we can easyly retreive the different numbers.

CLx
STO RAN#
RAN#
PREFIX
1017980433

STO 0
EEX 10 CHS
STO RAN#
RAN#
RCL - 0
PREFIX
1574352261

Cheers
Thomas

Shawn Gibson · 11-12-2014, 02:03 PM

I seem to recall early personal computers that created a random number in a game/program by using a very fast counter and the most random thing in the room.. a human. When the human presses the key it grabs whatever the number that the counter was set to, at the time of the keypress.
Shawn

Gerald H · (This post was last modified: 11-13-2014 10:54 AM by Gerald H.)

(09-06-2014 05:55 PM)John R. Graham Wrote: When do you think it's inappropriate to use a really good PRNG? The only contraindication I can think of that is potentially valid is if the resource requirements and/or execution time is onerous on the platform.

- John

Should you wish to eg find the area under a curve you would also want to avoid clumping, which clumping is a characteristic of a good PRNG. For such applications a Quasi Monte Carlo sequence of D-dimensional Halton sequence vectors is preferable, providing good spread within the set lower & upper limits & avoiding clumping.

For eg crypto purposes, QMCS is not so good.

In short, there are some uses where real randomness approxination is not the chief criterion of efficacy.

Namir · (This post was last modified: 11-14-2014 01:41 PM by Namir.)

(11-13-2014 10:52 AM)Gerald H Wrote:
(09-06-2014 05:55 PM)John R. Graham Wrote: When do you think it's inappropriate to use a really good PRNG? The only contraindication I can think of that is potentially valid is if the resource requirements and/or execution time is onerous on the platform.

- John

Should you wish to eg find the area under a curve you would also want to avoid clumping, which clumping is a characteristic of a good PRNG. For such applications a Quasi Monte Carlo sequence of D-dimensional Halton sequence vectors is preferable, providing good spread within the set lower & upper limits & avoiding clumping.

For eg crypto purposes, QMCS is not so good.

In short, there are some uses where real randomness approxination is not the chief criterion of efficacy.

Gerald,

You are the first person who discusses the negative aspects of very good PRNGs! It is very easy to have poor PRNGs and hard to develop good ones.

BTW .. I love your city and plan to visit my beloved Vienna in the fall of 2015. My wife and I usually stay at the Astoria hotel near the Opera house.