Groups > comp.lang.forth > #26916 > unrolled thread

LC53, a respectable random generator?

Started by	albert@spenarnc.xs4all.nl (Albert van der Horst)
First post	2013-11-23 16:25 +0000
Last post	2013-11-28 18:14 -0800
Articles	20 on this page of 62 — 13 participants

Back to article view | Back to comp.lang.forth

  LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-23 16:25 +0000
    Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-23 17:34 -0800
      Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-23 19:03 -0800
      Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-24 04:58 +0000
    Re: LC53, a respectable random generator? "Rod Pemberton" <dont_use_email@xnohavenotit.cnm> - 2013-11-24 04:57 -0500
      Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-24 14:17 +0000
        Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-24 08:12 -0800
          Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-24 16:46 +0000
          Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-24 23:53 +0100
            Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-24 15:41 -0800
              Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 17:57 -0800
              Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-25 19:32 +0000
                Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-25 14:22 -0800
                Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-26 00:20 +0100
                  Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-26 03:29 +0000
                    Re: LC53, a respectable random generator? thomas.bartscher@gmail.com - 2013-11-25 23:08 -0800
                      Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 05:06 -0800
                        Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-26 14:03 +0000
                        Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-26 21:59 +0100
                        Re: LC53, a respectable random generator? thomas.bartscher@gmail.com - 2013-11-28 01:32 -0800
                  Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-25 19:43 -0800
                Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-25 19:31 -0800
                Re: LC53, a respectable random generator? "Elizabeth D. Rather" <erather@forth.com> - 2013-11-25 19:24 -1000
                  Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 05:17 -0800
                  Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-26 14:21 +0000
                  Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-28 18:49 -0800
              Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-25 13:52 -0800
            Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 18:03 -0800
            Re: LC53, a respectable random generator? Matthias Koch <matthias.koch@hot.uni-hannover.de> - 2013-11-25 13:41 +0100
              Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-25 10:23 -0800
                Re: LC53, a respectable random generator? Howerd <howerdo@yahoo.co.uk> - 2013-11-25 13:43 -0800
                  Re: LC53, a respectable random generator? mhx@iae.nl - 2013-11-25 15:16 -0800
                    Re: LC53, a respectable random generator? Howerd <howerdo@yahoo.co.uk> - 2013-11-26 13:38 -0800
                      Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 20:42 -0800
                        Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 11:46 +0000
                          Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-27 18:35 -0800
                      Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 21:41 -0800
                        Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-27 03:21 -0600
                          Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 15:37 +0000
                            Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-27 23:01 +0100
                              Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 23:39 +0000
                              Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-28 05:41 -0600
                                Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-28 13:47 +0000
                                  Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-28 09:10 -0600
                                Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-28 16:22 +0100
                                  Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-28 09:34 -0600
                                  Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-28 18:39 -0800
                        Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 16:44 +0000
              Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-25 19:51 +0100
        Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 11:13 -0800
          Re: LC53, a respectable random generator? Hans Bezemer <the.beez.speaks@gmail.com> - 2013-11-25 09:52 +0100
    Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 13:07 -0800
      Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-25 02:18 +0000
        Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-24 19:36 -0800
    Re: LC53, a respectable random generator? "Ed" <invalid@invalid.com> - 2013-11-26 12:57 +1100
      Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-26 21:25 -0800
      Re: LC53, a respectable random generator? albert@spenarnc.xs4all.nl (Albert van der Horst) - 2013-11-27 15:48 +0000
    Re: LC53, a respectable random generator? Mark Wills <markrobertwills@yahoo.co.uk> - 2013-11-27 01:10 -0800
      Re: LC53, a respectable random generator? Andrew Haley <andrew29@littlepinkcloud.invalid> - 2013-11-27 03:29 -0600
        Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-27 19:49 -0800
          Re: LC53, a respectable random generator? Bernd Paysan <bernd.paysan@gmx.de> - 2013-11-28 15:57 +0100
            Re: LC53, a respectable random generator? hughaguilar96@yahoo.com - 2013-11-28 18:14 -0800

Page 2 of 4 — ← Prev page 1 [2] 3 4 Next page →

#26960

From	hughaguilar96@yahoo.com
Date	2013-11-25 19:43 -0800
Message-ID	<f187fe39-481d-476a-8668-7d9c934cacb5@googlegroups.com>
In reply to	#26956

On Monday, November 25, 2013 4:20:14 PM UTC-7, Bernd Paysan wrote:
> Albert van der Horst wrote:
> > \ Comma for clarity, not a double number.
> > : LC53  -5 um* -333,333,333 + nip ;
> 
> Hm, wasn't Hugh's LC53
> 
> : lc53  -333333333 um* -5 um/mod drop ;
> 
> ?  Don't make Hugh look more stupid than he actually is ;-).

I have removed LC53 from the Wikipedia LCG article. This means that there is no evidence anywhere (except the novice package itself, which is irrelevant on C.L.F.) as to what LC53 is (was). It is irrelevant how you define LC53 on C.L.F. now. Albert can make up anything that he wants --- getting me to remove LC53 was a total victory for Albert --- and, as you know, history is written by the victors.

I don't really care --- it took me only one day to write all of that prng stuff in the novice package, and most of the day was spent writing the support code --- I have already wasted more time than that posting in his thread.

[toc] | [prev] | [next] | [standalone]

#26959

From	hughaguilar96@yahoo.com
Date	2013-11-25 19:31 -0800
Message-ID	<f7f6850e-ffb1-42f6-b8ea-1e0d0b89fc38@googlegroups.com>
In reply to	#26950

On Monday, November 25, 2013 12:32:44 PM UTC-7, Albert van der Horst wrote:
> Hugh suggests that the only difference with his LC53 is that
> Anton Ertl and Elizabeth Rather inspire more confidence than he does.

You specifically asked for a "respectable" LCG from a "trusted source" with great "standing in the Forth community."

This is from SwiftForth:

VARIABLE BUD 

: RAND  ( -- u )  BUD @  3141592621 *  1+  DUP BUD ! ; 

Now that I've removed LC53 from the Wikipedia LCG list, there is no Forth representative in there. I recommend that you put the SwiftForth LCG in LC53's place. If you fail to do this, that would imply that you don't consider Forth Inc. to be a respectable trusted-source with great standing in the Forth community. It is not a big deal to offend me, but I don't think you want to offend Elizabeth Rather --- now that you have gone so far as to demand that I remove LC53, you are pretty much obliged to replace it with the Forth Inc. LCG. To fail to replace mine with hers implies that you think Elizabeth Rather is at the same level of stupidity as myself --- she is going to be offended!

There doesn't need to be any discussion of the technical aspects at all --- you just replace my LCG with Forth Inc.'s and you've got your respectable trusted-source --- it is as simple as that!

[toc] | [prev] | [next] | [standalone]

#26961

From	"Elizabeth D. Rather" <erather@forth.com>
Date	2013-11-25 19:24 -1000
Message-ID	<ivudnSVTlIfurQnPnZ2dnUVZ_gSdnZ2d@supernews.com>
In reply to	#26950

On 11/25/13 9:32 AM, Albert van der Horst wrote:
...
> I see that gForth as well as SwiftForth use a simple LCG.
> As far as I can see, they don't supply a reference, testset, testdata
> or other motivation.
>
> I fear neither of those fare too well on the harsh tests you use.
> Hugh suggests that the only difference with his LC53 is that
> Anton Ertl and Elizabeth Rather inspire more confidence than he does.

Thank you, but I never wrote a random number generator and don't intend 
to! I've been blessed by having some brilliant programmers around me. 
But most of FORTH, Inc.'s customers aren't in fields where a strong RNG 
is a necessity, so we keep it simple.

Cheers,
Elizabeth

-- 
==================================================
Elizabeth D. Rather   (US & Canada)   800-55-FORTH
FORTH Inc.                         +1 310.999.6784
5959 West Century Blvd. Suite 700
Los Angeles, CA 90045
http://www.forth.com

"Forth-based products and Services for real-time
applications since 1973."
==================================================

[toc] | [prev] | [next] | [standalone]

#26970

From	hughaguilar96@yahoo.com
Date	2013-11-26 05:17 -0800
Message-ID	<c0fd364b-447a-495e-8e87-48ce8baa7d9d@googlegroups.com>
In reply to	#26961

On Monday, November 25, 2013 10:24:00 PM UTC-7, Elizabeth D. Rather wrote:
> On 11/25/13 9:32 AM, Albert van der Horst wrote:
> > Hugh suggests that the only difference with his LC53 is that
> > Anton Ertl and Elizabeth Rather inspire more confidence than he does.

> Thank you, but I never wrote a random number generator and don't intend 
> to! I've been blessed by having some brilliant programmers around me. 

Well, that settles it! Albert can post the SwiftForth LCG on the Wikipedia LCG page:

VARIABLE BUD 

: RAND  ( -- u )  BUD @  3141592621 *  1+  DUP BUD ! ; 

If anybody objects, he can justify this by saying that it was written by a "brilliant programmer" (Wil Baden) and accepted as being brilliant by the "respectable" Elizabeth Rather.

If Albert will go ahead and update the Wikipedia LCG page with the brilliant SwiftForth code, then I think that we are done with this thread.

Cheers!

[toc] | [prev] | [next] | [standalone]

#26972

From	albert@spenarnc.xs4all.nl (Albert van der Horst)
Date	2013-11-26 14:21 +0000
Message-ID	<5294ae60$0$3200$e4fe514c@dreader36.news.xs4all.nl>
In reply to	#26961

In article <ivudnSVTlIfurQnPnZ2dnUVZ_gSdnZ2d@supernews.com>,
Elizabeth D. Rather <erather@forth.com> wrote:
>On 11/25/13 9:32 AM, Albert van der Horst wrote:
>...
>> I see that gForth as well as SwiftForth use a simple LCG.
>> As far as I can see, they don't supply a reference, testset, testdata
>> or other motivation.
>>
>> I fear neither of those fare too well on the harsh tests you use.
>> Hugh suggests that the only difference with his LC53 is that
>> Anton Ertl and Elizabeth Rather inspire more confidence than he does.
>
>Thank you, but I never wrote a random number generator and don't intend
>to! I've been blessed by having some brilliant programmers around me.
>But most of FORTH, Inc.'s customers aren't in fields where a strong RNG
>is a necessity, so we keep it simple.

Hugh can learn something from this.

Why does this answer inspire confidence?
1. Offloading work to experts
2. A conscious decision about quality
3. polite, well formulated and to the point

Am I prejudiced?  (Impression before this discussion.)
Seeing the FORTH inc. rng:
"It can be too shabby. Surely someone has looked into this."
Seeing LC53 in the wikipedia:
"Someone is promoting his crap abusing wikipedia."


>
>Cheers,
>Elizabeth

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#27059

From	hughaguilar96@yahoo.com
Date	2013-11-28 18:49 -0800
Message-ID	<b44ec046-5723-4e5c-abc4-ac3e938ad2b1@googlegroups.com>
In reply to	#26961

On Monday, November 25, 2013 10:24:00 PM UTC-7, Elizabeth D. Rather wrote:
> On 11/25/13 9:32 AM, Albert van der Horst wrote:
> > Hugh suggests that the only difference with his LC53 is that
> > Anton Ertl and Elizabeth Rather inspire more confidence than he does.
>
> Thank you, but I never wrote a random number generator and don't intend 
> to! I've been blessed by having some brilliant programmers around me. 
> But most of FORTH, Inc.'s customers aren't in fields where a strong RNG 
> is a necessity, so we keep it simple.

The mark of a great sales-person is the ability to say "thank you" with a straight face for work done by somebody else.

Today is Thanksgiving! A day when we are supposed to count our blessings! Elizabeth Rather has been blessed by having brilliant programmers around her --- she can thank God for that.

I have never had any brilliant programmers around me (I was working at Testra when I wrote MFX) --- and I don't believe that God (the creator of the universe) cares if I succeed as a programmer, or write code that doesn't work, or get run over by a cement-truck --- so I just rely on my own programming skills to make my code work, and look both ways before crossing the street.

BTW: My own tradition is to fast throughout the whole Thanksgiving weekend, as I think that fasting is good for the soul --- am I the only person in the world who does this on the Thanksgiving holiday?

[toc] | [prev] | [next] | [standalone]

#26953

From	mhx@iae.nl
Date	2013-11-25 13:52 -0800
Message-ID	<59f886cb-9532-4967-a9b4-5988ee25ec84@googlegroups.com>
In reply to	#26932

On Monday, November 25, 2013 12:41:23 AM UTC+1, m...@iae.nl wrote:
> On Sunday, November 24, 2013 11:53:14 PM UTC+1, Bernd Paysan wrote:
> > mhx@iae.nl wrote:
> For a Forth random generator many sources are available, 
> e.g. this is a list from the past 10 years:
[..]

And don't forget to read Skip's papers here :- ftp://ftp.taygeta.com/pub/Forth/Literature/ .

-marcel

[toc] | [prev] | [next] | [standalone]

#26935

From	hughaguilar96@yahoo.com
Date	2013-11-24 18:03 -0800
Message-ID	<7df666f7-c017-4752-8697-95e37466fcd5@googlegroups.com>
In reply to	#26931

On Sunday, November 24, 2013 3:53:14 PM UTC-7, Bernd Paysan wrote:
> If Hugh wants a better, yet still very simple PRNG in his novice suite that 
> does pass a reasonable test suite and is fast and easy to implement, he 
> should implement that one; the German Wikipedia has even (relatively good) 
> variants for 32 and 64 bits:

Don't tell me what I "should" do --- you're nobody that I consider worth listening to on any subject.

[toc] | [prev] | [next] | [standalone]

#26941

From	Matthias Koch <matthias.koch@hot.uni-hannover.de>
Date	2013-11-25 13:41 +0100
Message-ID	<l6vgn6$8ee$1@newsserver.rrzn.uni-hannover.de>
In reply to	#26931

Bernd Paysan:
> the German Wikipedia has even (relatively good) 
> variants for 32 and 64 bits:
> 
> http://de.wikipedia.org/wiki/Xorshift

\ Xorshift Random Number Generator, 32 Bits

314159265 variable seed

: random ( -- x )
  seed @
  dup 13 lshift xor
  dup 17 rshift xor
  dup  5 lshift xor
  dup seed !
;

[toc] | [prev] | [next] | [standalone]

#26945

From	mhx@iae.nl
Date	2013-11-25 10:23 -0800
Message-ID	<66c50ce4-22c5-4c83-821b-b827e6a85def@googlegroups.com>
In reply to	#26941

On Monday, November 25, 2013 1:41:17 PM UTC+1, Matthias Koch wrote:
> Bernd Paysan:
> 
> > the German Wikipedia has even (relatively good) 
> > variants for 32 and 64 bits:
> > 
> > http://de.wikipedia.org/wiki/Xorshift
> 
> \ Xorshift Random Number Generator, 32 Bits
> 
> 314159265 variable seed
> 
> : random ( -- x )
>   seed @
>   dup 13 lshift xor
>   dup 17 rshift xor
>   dup  5 lshift xor
>   dup seed !
> ;

( I'll call it shrandom )
The gorilla certainly doesn't like it.

-marcel

-- ----------------------
FORTH> init-seeds diehard
DIEHARD is checking shrandom..

        .---------------------------------------------------------------.
        |           This is the "tough" BIRTHDAY SPACINGS TEST          |
        | Choose 4096 birthdays in a "year" of 2^32 days. Thus each     |
        | birthday is a 32-bit integer and the test uses 2^12 of them,  |
        | so that j, the number of duplicate spacings, is asympotically |
        | Poisson distributed with lambda=4.  Generators that pass the  |
        | earlier tests for m=1024 and n=2^24 often fail this test, yet |
        | those that pass this test seem to pass the "weaker" test.     |
        | Each set of 4096 birthdays provide a Poisson variate j, and   |
        | 500 such j's lead to a chisquare test to see if the result    |
        | is consistent with the Poisson distribution with lambda=16.   |
        `---------------------------------------------------------------'
            Table of Expected versus Observed counts:
Duplicates    0     1     2     3     4     5     6     7     8     9  >=10
Expected     91   366   732   976   976   781   520   297   148    66    40
Observed     83   377   746   952   970   759   528   308   179    64    34
(O-E)^2/E   0.8   0.3   0.2   0.6   0.0   0.6   0.1   0.4   6.1   0.1   1.1
            Birthday Spacings: Sum(O-E)^2/E =  10.404, p =  0.600
 ( 4.870 seconds elapsed. )

        .-------------------------------------------------------------.
        | This is the GCD TEST.   Let the (32-bit) RNG produce two    |
        | successive integers u,v.  Use Euclids algorithm to find the |
        | gcd, say x, of u and v. Let k be the number of steps needed |
        | to get x.   Then k is approximately binomial with p=.376    |
        | and n=50,  while the distribution of x is very close to     |
        | Pr(x=i)=c/i^2, with c=6/pi^2.   The gcd test uses ten       |
        | million such pairs u,v to see if the resulting frequencies  |
        | of k's and x's are consistent with the above distributions. |
        | Congruential RNG's---even those with prime modulus---fail   |
        | this test for the distribution of k, the number of steps,   |
        | and often for the distribution of gcd values x as well.     |
        `-------------------------------------------------------------'
Euclid's algorithm:
 p-value, steps to gcd: 0.494869
 p-value, distance of gcd's: 0.162701
 ( 2.104 seconds elapsed. )

        .---------------------------------------------------------------.
        |   This is the GORILLA test, a strong version of the monkey    |
        |   tests that I developed in the 70's. It concerns strings     |
        |   formed from specified bits in 32-bit integers from the RNG. |
        |   We specify the bit position to be studied, from 0 to 31,    |
        |   say bit 3. Then we generate 67,108,889 (2^26+25) numbers    |
        |   from the generator and form a string of 2^26+25 bits by     |
        |   taking bit 3 from each of those numbers. In that string of  |
        |   2^26+25 bits we count the number of 26-bit segments that    |
        |   do not appear. That count should be approximately normal    |
        |   with mean 24687971 and std. deviation 4170. This leads to   |
        |   a normal z-score and hence to a p-value. The test is        |
        |   applied for each bit position 0 (leftmost) to 31.           |
        |   (Some older tests use Fortran's 1-32 for most- to least-    |
        |   significant bits. Gorilla and newer tests use C's 0 to 31.) |
        `---------------------------------------------------------------'
Gorilla test for 2^26 bits, positions 0 to 31:
Note: lengthy test -- ~20 minutes for 900 MHz PC
Bits  0 to  7 || 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
Bits  8 to 15 || 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
Bits 16 to 23 || 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
Bits 24 to 31 || 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
ADKS test for the above 32 p values:  1.000
 ( 28.597 seconds elapsed. )

        .---------------------------------------------------------------.
        |           THE OVERLAPPING 5-PERMUTATION TEST                  |
        | This is the OPERM5 test.  It looks at a sequence of ten       |
        | million 32-bit random integers.  Each set of five consecutive |
        | integers can be in one of 120 states, for the 5! possible     |
        | orderings of five numbers.  Thus the 5th, 6th, 7th,...numbers |
        | each provide a state. As many thousands of state transitions  |
        | are observed,  cumulative counts are made of the number of    |
        | occurences of each state.  Then the quadratic form in the     |
        | weak inverse of the 120x120 covariance matrix yields a test   |
        | that the 120 cellcounts came from the specified (asymptotic)  |
        | distribution with the specified means and 120x120 covariance. |
        `---------------------------------------------------------------'
      The OPERM5 test for 10 million (overlapping) 5-tuples for shrandom.
      p-values for 5 runs: 0.2900 0.6235 0.7778 0.8739 0.7441
 ( 6.842 seconds elapsed. ) ok

[toc] | [prev] | [next] | [standalone]

#26952

From	Howerd <howerdo@yahoo.co.uk>
Date	2013-11-25 13:43 -0800
Message-ID	<3048c4d8-b8e4-4253-92a2-e4439a81da35@googlegroups.com>
In reply to	#26945

On Monday, 25 November 2013 18:23:12 UTC, m...@iae.nl  wrote:
> On Monday, November 25, 2013 1:41:17 PM UTC+1, Matthias Koch wrote:
> 
> > Bernd Paysan:
> 
> > 
> 
> > > the German Wikipedia has even (relatively good) 
> 
> > > variants for 32 and 64 bits:
> 
> > > 
> 
> > > http://de.wikipedia.org/wiki/Xorshift
> 
> > 
> 
> > \ Xorshift Random Number Generator, 32 Bits
> 
> > 
> 
> > 314159265 variable seed
> 
> > 
> 
> > : random ( -- x )
> 
> >   seed @
> 
> >   dup 13 lshift xor
> 
> >   dup 17 rshift xor
> 
> >   dup  5 lshift xor
> 
> >   dup seed !
> 
> > ;
> 
> 
> 
> ( I'll call it shrandom )
> 
> The gorilla certainly doesn't like it.
> 
> 
> 
> -marcel
> 
> 
> 
> -- ----------------------
> 
> FORTH> init-seeds diehard
> 
> DIEHARD is checking shrandom..
> 
> 
> 
>         .---------------------------------------------------------------.
> 
>         |           This is the "tough" BIRTHDAY SPACINGS TEST          |
> 
>         | Choose 4096 birthdays in a "year" of 2^32 days. Thus each     |
> 
>         | birthday is a 32-bit integer and the test uses 2^12 of them,  |
> 
>         | so that j, the number of duplicate spacings, is asympotically |
> 
>         | Poisson distributed with lambda=4.  Generators that pass the  |
> 
>         | earlier tests for m=1024 and n=2^24 often fail this test, yet |
> 
>         | those that pass this test seem to pass the "weaker" test.     |
> 
>         | Each set of 4096 birthdays provide a Poisson variate j, and   |
> 
>         | 500 such j's lead to a chisquare test to see if the result    |
> 
>         | is consistent with the Poisson distribution with lambda=16.   |
> 
>         `---------------------------------------------------------------'
> 
>             Table of Expected versus Observed counts:
> 
> Duplicates    0     1     2     3     4     5     6     7     8     9  >=10
> 
> Expected     91   366   732   976   976   781   520   297   148    66    40
> 
> Observed     83   377   746   952   970   759   528   308   179    64    34
> 
> (O-E)^2/E   0.8   0.3   0.2   0.6   0.0   0.6   0.1   0.4   6.1   0.1   1.1
> 
>             Birthday Spacings: Sum(O-E)^2/E =  10.404, p =  0.600
> 
>  ( 4.870 seconds elapsed. )
> 
> 
> 
>         .-------------------------------------------------------------.
> 
>         | This is the GCD TEST.   Let the (32-bit) RNG produce two    |
> 
>         | successive integers u,v.  Use Euclids algorithm to find the |
> 
>         | gcd, say x, of u and v. Let k be the number of steps needed |
> 
>         | to get x.   Then k is approximately binomial with p=.376    |
> 
>         | and n=50,  while the distribution of x is very close to     |
> 
>         | Pr(x=i)=c/i^2, with c=6/pi^2.   The gcd test uses ten       |
> 
>         | million such pairs u,v to see if the resulting frequencies  |
> 
>         | of k's and x's are consistent with the above distributions. |
> 
>         | Congruential RNG's---even those with prime modulus---fail   |
> 
>         | this test for the distribution of k, the number of steps,   |
> 
>         | and often for the distribution of gcd values x as well.     |
> 
>         `-------------------------------------------------------------'
> 
> Euclid's algorithm:
> 
>  p-value, steps to gcd: 0.494869
> 
>  p-value, distance of gcd's: 0.162701
> 
>  ( 2.104 seconds elapsed. )
> 
> 
> 
>         .---------------------------------------------------------------.
> 
>         |   This is the GORILLA test, a strong version of the monkey    |
> 
>         |   tests that I developed in the 70's. It concerns strings     |
> 
>         |   formed from specified bits in 32-bit integers from the RNG. |
> 
>         |   We specify the bit position to be studied, from 0 to 31,    |
> 
>         |   say bit 3. Then we generate 67,108,889 (2^26+25) numbers    |
> 
>         |   from the generator and form a string of 2^26+25 bits by     |
> 
>         |   taking bit 3 from each of those numbers. In that string of  |
> 
>         |   2^26+25 bits we count the number of 26-bit segments that    |
> 
>         |   do not appear. That count should be approximately normal    |
> 
>         |   with mean 24687971 and std. deviation 4170. This leads to   |
> 
>         |   a normal z-score and hence to a p-value. The test is        |
> 
>         |   applied for each bit position 0 (leftmost) to 31.           |
> 
>         |   (Some older tests use Fortran's 1-32 for most- to least-    |
> 
>         |   significant bits. Gorilla and newer tests use C's 0 to 31.) |
> 
>         `---------------------------------------------------------------'
> 
> Gorilla test for 2^26 bits, positions 0 to 31:
> 
> Note: lengthy test -- ~20 minutes for 900 MHz PC
> 
> Bits  0 to  7 || 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
> 
> Bits  8 to 15 || 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
> 
> Bits 16 to 23 || 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
> 
> Bits 24 to 31 || 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000
> 
> ADKS test for the above 32 p values:  1.000
> 
>  ( 28.597 seconds elapsed. )
> 
> 
> 
>         .---------------------------------------------------------------.
> 
>         |           THE OVERLAPPING 5-PERMUTATION TEST                  |
> 
>         | This is the OPERM5 test.  It looks at a sequence of ten       |
> 
>         | million 32-bit random integers.  Each set of five consecutive |
> 
>         | integers can be in one of 120 states, for the 5! possible     |
> 
>         | orderings of five numbers.  Thus the 5th, 6th, 7th,...numbers |
> 
>         | each provide a state. As many thousands of state transitions  |
> 
>         | are observed,  cumulative counts are made of the number of    |
> 
>         | occurences of each state.  Then the quadratic form in the     |
> 
>         | weak inverse of the 120x120 covariance matrix yields a test   |
> 
>         | that the 120 cellcounts came from the specified (asymptotic)  |
> 
>         | distribution with the specified means and 120x120 covariance. |
> 
>         `---------------------------------------------------------------'
> 
>       The OPERM5 test for 10 million (overlapping) 5-tuples for shrandom.
> 
>       p-values for 5 runs: 0.2900 0.6235 0.7778 0.8739 0.7441
> 
>  ( 6.842 seconds elapsed. ) ok

Hi Marcel,

Albert pointed out that you seem to have a test setup - how do encryption algorithms perform when used as a PRNG? I am assuming by incrementing a 64 bit value and encrypting it.

For example the Tiny Encryption Algorithm?

If you get a minute I would love to see the results for TEAN (appended below).

Best regards * TIA,
Howerd


The full file is available from http://www.inventio.co.uk/tean.f :

\ tean.f 2006 Jan 04
\ TEA is the Tiny Encryption Algorithm - a shared private key system
\ based on many iterations of a simple hashing function.
\ Created by David J. Wheeler and Roger M. Needham.
\ TEAN ( TEA New ) is an improved version of TEA which includes modifications
\ to TEA made after David Wagner discovered weaknesses in the key scheduling.
\ Based on C code from http://www.simonshepherd.supanet.com/source.htm#new_ansi
\ See also http://www.ftp.cl.cam.ac.uk/ftp/papers/djw-rmn/djw-rmn-tea.html
\ TEA and TEAN are 64-bit block Feistel cyphers using a 128-bit key.

\ +tean  encrypts d to d' using the given number of rounds and initial key
\ -tean  decrypts d' to d using the same parameters.
\ You can use these to encrypt an array, adjusting the parameters
\ after each 64 bit value is encrypted if required.

\ This is a 32 bit Little Endian ANS Forth version ( PC ).
\ Usage : 123456. +tean  2dup d.  -tean d.

decimal

\ user inputs - you choose the number of rounds and initial key :
\ #rounds holds the number of times round the loop :
\ should be > 8, increase for stronger encryption ( say 32 )
variable #rounds
4 cells Buffer: MyKey   \ load this with the shared private key

\ The Golden Ratio ( 5 sqrt 1+ 2/ ) = 1.618033989, - 1 , scaled up to 32 bits
$9e3779b9 constant delta    \ could be anything except "bad" values...

\ working variables
variable delta#rounds@* \ pre-calculated value, for speed
variable MySum
variable MyVar1
variable MyVar2

\ get a new key value ( two flavours )
: GetKey1 ( - u)   MySum @  dup 3 and cells MyKey + @ + ;
: GetKey2 ( - u)   MySum @  dup 11 rshift 3 and cells MyKey + @ + ;

\ mix the bits of the variables ( two flavours again )
: Mangle1 ( - u)   MyVar1 @ 4 lshift  MyVar1 @ 5 rshift xor  MyVar1 @ + ;
: Mangle2 ( - u)   MyVar2 @ 4 lshift  MyVar2 @ 5 rshift xor  MyVar2 @ + ;

\ one round of the encryption algorithm
: (+tean) ( a b - a' b' )
   Mangle1
   GetKey1      \ key
   xor              \ mangled 1 and key
   MyVar2 +!        \ add to 2
   delta MySum +!   \ add to sum
   Mangle2
   GetKey2          \ key
   xor              \ mangled 2 and key
   MyVar1 +!        \ add to 1
;

\ encrypt d to d' using the number of rounds and private key values
: +tean ( d - d' )
   MyVar2 !  MyVar1 !
   0 MySum !
   #rounds @ 0 do  (+tean)  loop
   MyVar1 @  MyVar2 @
;

[toc] | [prev] | [next] | [standalone]

#26955

From	mhx@iae.nl
Date	2013-11-25 15:16 -0800
Message-ID	<0e36a61a-722f-428c-bdab-0d2fa8d1b629@googlegroups.com>
In reply to	#26952

On Monday, November 25, 2013 10:43:36 PM UTC+1, Howerd wrote:
> On Monday, 25 November 2013 18:23:12 UTC, m...@iae.nl  wrote:
[..] 
> Albert pointed out that you seem to have a test setup - how do 
> encryption algorithms perform when used as a PRNG? I am assuming 
> by incrementing a 64 bit value and encrypting it.
> 
> For example the Tiny Encryption Algorithm?
> 
> If you get a minute I would love to see the results for TEAN (appended below).
[..]

For 1 SetRounds it is not better than the LCGs,
but upwards of 4 it starts to become acceptable. 
Unfortunately, I didn't muster enough patience to 
document it properly -- the thing is DOG-SLOW.

-marcel
-- ----------------
FORTH> 4 SetRounds diehard
DIEHARD is checking RAN-TEAN..

        .---------------------------------------------------------------.
        |           This is the "tough" BIRTHDAY SPACINGS TEST          |
        | Choose 4096 birthdays in a "year" of 2^32 days. Thus each     |
        | birthday is a 32-bit integer and the test uses 2^12 of them,  |
        | so that j, the number of duplicate spacings, is asympotically |
        | Poisson distributed with lambda=4.  Generators that pass the  |
        | earlier tests for m=1024 and n=2^24 often fail this test, yet |
        | those that pass this test seem to pass the "weaker" test.     |
        | Each set of 4096 birthdays provide a Poisson variate j, and   |
        | 500 such j's lead to a chisquare test to see if the result    |
        | is consistent with the Poisson distribution with lambda=16.   |
        `---------------------------------------------------------------'
            Table of Expected versus Observed counts:
Duplicates    0     1     2     3     4     5     6     7     8     9  >=10
Expected     91   366   732   976   976   781   520   297   148    66    40
Observed     87   377   746   934  1001   778   523   287   151    63    53
(O-E)^2/E   0.2   0.3   0.2   1.9   0.6   0.0   0.0   0.4   0.0   0.2   3.7
            Birthday Spacings: Sum(O-E)^2/E =   7.595, p =  0.354
 ( 5.364 seconds elapsed. )

        .-------------------------------------------------------------.
        | This is the GCD TEST.   Let the (32-bit) RNG produce two    |
        | successive integers u,v.  Use Euclids algorithm to find the |
        | gcd, say x, of u and v. Let k be the number of steps needed |
        | to get x.   Then k is approximately binomial with p=.376    |
        | and n=50,  while the distribution of x is very close to     |
        | Pr(x=i)=c/i^2, with c=6/pi^2.   The gcd test uses ten       |
        | million such pairs u,v to see if the resulting frequencies  |
        | of k's and x's are consistent with the above distributions. |
        | Congruential RNG's---even those with prime modulus---fail   |
        | this test for the distribution of k, the number of steps,   |
        | and often for the distribution of gcd values x as well.     |
        `-------------------------------------------------------------'
Euclid's algorithm:
 p-value, steps to gcd: 1.000000
 p-value, distance of gcd's: 0.166675
 ( 2.703 seconds elapsed. )

        .---------------------------------------------------------------.
        |   This is the GORILLA test, a strong version of the monkey    |
        |   tests that I developed in the 70's. It concerns strings     |
        |   formed from specified bits in 32-bit integers from the RNG. |
        |   We specify the bit position to be studied, from 0 to 31,    |
        |   say bit 3. Then we generate 67,108,889 (2^26+25) numbers    |
        |   from the generator and form a string of 2^26+25 bits by     |
        |   taking bit 3 from each of those numbers. In that string of  |
        |   2^26+25 bits we count the number of 26-bit segments that    |
        |   do not appear. That count should be approximately normal    |
        |   with mean 24687971 and std. deviation 4170. This leads to   |
        |   a normal z-score and hence to a p-value. The test is        |
        |   applied for each bit position 0 (leftmost) to 31.           |
        |   (Some older tests use Fortran's 1-32 for most- to least-    |
        |   significant bits. Gorilla and newer tests use C's 0 to 31.) |
        `---------------------------------------------------------------'
Gorilla test for 2^26 bits, positions 0 to 31:
Note: lengthy test -- ~20 minutes for 900 MHz PC
Bits  0 to  7 || 1.000 1.000 1.000 0.534 0.840 0.304 0.564 0.925
Bits  8 to 15 || 0.889 0.986 0.128 0.864 0.383 0.085 0.472 0.150
Bits 16 to 23 || 0.322 0.535 0.017 0.394 0.681 0.643 0.568 0.768
Bits 24 to 31 || 0.447 0.326 0.886 0.585 0.376 0.303 0.506 0.209
ADKS test for the above 32 p values:  1.000
 ( 109.599 seconds elapsed. )

        .---------------------------------------------------------------.
        |           THE OVERLAPPING 5-PERMUTATION TEST                  |
        | This is the OPERM5 test.  It looks at a sequence of ten       |
        | million 32-bit random integers.  Each set of five consecutive |
        | integers can be in one of 120 states, for the 5! possible     |
        | orderings of five numbers.  Thus the 5th, 6th, 7th,...numbers |
        | each provide a state. As many thousands of state transitions  |
        | are observed,  cumulative counts are made of the number of    |
        | occurences of each state.  Then the quadratic form in the     |
        | weak inverse of the 120x120 covariance matrix yields a test   |
        | that the 120 cellcounts came from the specified (asymptotic)  |
        | distribution with the specified means and 120x120 covariance. |
        `---------------------------------------------------------------'
      The OPERM5 test for 10 million (overlapping) 5-tuples for RAN-TEAN.
      p-values for 5 runs: 1.0000 1.0000 1.0000 1.0000 1.0000
 ( 8.469 seconds elapsed. ) ok

[toc] | [prev] | [next] | [standalone]

#26984

From	Howerd <howerdo@yahoo.co.uk>
Date	2013-11-26 13:38 -0800
Message-ID	<3870406b-a252-4876-a794-7461e75ddd7e@googlegroups.com>
In reply to	#26955

On Monday, 25 November 2013 23:16:36 UTC, m...@iae.nl  wrote:
> On Monday, November 25, 2013 10:43:36 PM UTC+1, Howerd wrote:
> 
> > On Monday, 25 November 2013 18:23:12 UTC, m...@iae.nl  wrote:
> 
> [..] 
> 
> > Albert pointed out that you seem to have a test setup - how do 
> 
> > encryption algorithms perform when used as a PRNG? I am assuming 
> 
> > by incrementing a 64 bit value and encrypting it.
> 
> > 
> 
> > For example the Tiny Encryption Algorithm?
> 
> > 
> 
> > If you get a minute I would love to see the results for TEAN (appended below).
> 
> [..]
> 
> 
> 
> For 1 SetRounds it is not better than the LCGs,
> 
> but upwards of 4 it starts to become acceptable. 
> 
> Unfortunately, I didn't muster enough patience to 
> 
> document it properly -- the thing is DOG-SLOW.
> 
> 
> 
> -marcel
> 
> -- ----------------
> 
> FORTH> 4 SetRounds diehard
> 
> DIEHARD is checking RAN-TEAN..
> 
> 
> 
>         .---------------------------------------------------------------.
> 
>         |           This is the "tough" BIRTHDAY SPACINGS TEST          |
> 
>         | Choose 4096 birthdays in a "year" of 2^32 days. Thus each     |
> 
>         | birthday is a 32-bit integer and the test uses 2^12 of them,  |
> 
>         | so that j, the number of duplicate spacings, is asympotically |
> 
>         | Poisson distributed with lambda=4.  Generators that pass the  |
> 
>         | earlier tests for m=1024 and n=2^24 often fail this test, yet |
> 
>         | those that pass this test seem to pass the "weaker" test.     |
> 
>         | Each set of 4096 birthdays provide a Poisson variate j, and   |
> 
>         | 500 such j's lead to a chisquare test to see if the result    |
> 
>         | is consistent with the Poisson distribution with lambda=16.   |
> 
>         `---------------------------------------------------------------'
> 
>             Table of Expected versus Observed counts:
> 
> Duplicates    0     1     2     3     4     5     6     7     8     9  >=10
> 
> Expected     91   366   732   976   976   781   520   297   148    66    40
> 
> Observed     87   377   746   934  1001   778   523   287   151    63    53
> 
> (O-E)^2/E   0.2   0.3   0.2   1.9   0.6   0.0   0.0   0.4   0.0   0.2   3.7
> 
>             Birthday Spacings: Sum(O-E)^2/E =   7.595, p =  0.354
> 
>  ( 5.364 seconds elapsed. )
> 
> 
> 
>         .-------------------------------------------------------------.
> 
>         | This is the GCD TEST.   Let the (32-bit) RNG produce two    |
> 
>         | successive integers u,v.  Use Euclids algorithm to find the |
> 
>         | gcd, say x, of u and v. Let k be the number of steps needed |
> 
>         | to get x.   Then k is approximately binomial with p=.376    |
> 
>         | and n=50,  while the distribution of x is very close to     |
> 
>         | Pr(x=i)=c/i^2, with c=6/pi^2.   The gcd test uses ten       |
> 
>         | million such pairs u,v to see if the resulting frequencies  |
> 
>         | of k's and x's are consistent with the above distributions. |
> 
>         | Congruential RNG's---even those with prime modulus---fail   |
> 
>         | this test for the distribution of k, the number of steps,   |
> 
>         | and often for the distribution of gcd values x as well.     |
> 
>         `-------------------------------------------------------------'
> 
> Euclid's algorithm:
> 
>  p-value, steps to gcd: 1.000000
> 
>  p-value, distance of gcd's: 0.166675
> 
>  ( 2.703 seconds elapsed. )
> 
> 
> 
>         .---------------------------------------------------------------.
> 
>         |   This is the GORILLA test, a strong version of the monkey    |
> 
>         |   tests that I developed in the 70's. It concerns strings     |
> 
>         |   formed from specified bits in 32-bit integers from the RNG. |
> 
>         |   We specify the bit position to be studied, from 0 to 31,    |
> 
>         |   say bit 3. Then we generate 67,108,889 (2^26+25) numbers    |
> 
>         |   from the generator and form a string of 2^26+25 bits by     |
> 
>         |   taking bit 3 from each of those numbers. In that string of  |
> 
>         |   2^26+25 bits we count the number of 26-bit segments that    |
> 
>         |   do not appear. That count should be approximately normal    |
> 
>         |   with mean 24687971 and std. deviation 4170. This leads to   |
> 
>         |   a normal z-score and hence to a p-value. The test is        |
> 
>         |   applied for each bit position 0 (leftmost) to 31.           |
> 
>         |   (Some older tests use Fortran's 1-32 for most- to least-    |
> 
>         |   significant bits. Gorilla and newer tests use C's 0 to 31.) |
> 
>         `---------------------------------------------------------------'
> 
> Gorilla test for 2^26 bits, positions 0 to 31:
> 
> Note: lengthy test -- ~20 minutes for 900 MHz PC
> 
> Bits  0 to  7 || 1.000 1.000 1.000 0.534 0.840 0.304 0.564 0.925
> 
> Bits  8 to 15 || 0.889 0.986 0.128 0.864 0.383 0.085 0.472 0.150
> 
> Bits 16 to 23 || 0.322 0.535 0.017 0.394 0.681 0.643 0.568 0.768
> 
> Bits 24 to 31 || 0.447 0.326 0.886 0.585 0.376 0.303 0.506 0.209
> 
> ADKS test for the above 32 p values:  1.000
> 
>  ( 109.599 seconds elapsed. )
> 
> 
> 
>         .---------------------------------------------------------------.
> 
>         |           THE OVERLAPPING 5-PERMUTATION TEST                  |
> 
>         | This is the OPERM5 test.  It looks at a sequence of ten       |
> 
>         | million 32-bit random integers.  Each set of five consecutive |
> 
>         | integers can be in one of 120 states, for the 5! possible     |
> 
>         | orderings of five numbers.  Thus the 5th, 6th, 7th,...numbers |
> 
>         | each provide a state. As many thousands of state transitions  |
> 
>         | are observed,  cumulative counts are made of the number of    |
> 
>         | occurences of each state.  Then the quadratic form in the     |
> 
>         | weak inverse of the 120x120 covariance matrix yields a test   |
> 
>         | that the 120 cellcounts came from the specified (asymptotic)  |
> 
>         | distribution with the specified means and 120x120 covariance. |
> 
>         `---------------------------------------------------------------'
> 
>       The OPERM5 test for 10 million (overlapping) 5-tuples for RAN-TEAN.
> 
>       p-values for 5 runs: 1.0000 1.0000 1.0000 1.0000 1.0000
> 
>  ( 8.469 seconds elapsed. ) ok

Thanks :-)
H.

[toc] | [prev] | [next] | [standalone]

#26992

From	hughaguilar96@yahoo.com
Date	2013-11-26 20:42 -0800
Message-ID	<4b2f456f-3bcc-4bda-b1df-14cd8cbe41a3@googlegroups.com>
In reply to	#26984

On Tuesday, November 26, 2013 7:21:20 AM UTC-7, Albert van der Horst wrote:
> In article <ivudnSVTlIfurQnPnZ2dnUVZ_gSdnZ2d@supernews.com>,
> Elizabeth D. Rather <erather@forth.com> wrote:
> >On 11/25/13 9:32 AM, Albert van der Horst wrote:
> >> Hugh suggests that the only difference with his LC53 is that
> >> Anton Ertl and Elizabeth Rather inspire more confidence than he does.
> 
> >Thank you, but I never wrote a random number generator and don't intend
> >to! I've been blessed by having some brilliant programmers around me.
> >But most of FORTH, Inc.'s customers aren't in fields where a strong RNG
> >is a necessity, so we keep it simple.

> Hugh can learn something from this.
> 
> Why does this answer inspire confidence?
> 1. Offloading work to experts
> 2. A conscious decision about quality
> 3. polite, well formulated and to the point
>
> Am I prejudiced?  (Impression before this discussion.)
> Seeing the FORTH inc. rng:
> "It can be too shabby. Surely someone has looked into this."
> Seeing LC53 in the wikipedia:
> "Someone is promoting his crap abusing wikipedia."

I think you meant "can't be too shabby." 

Anyway, what are you waiting for? Put the SwiftForth LCG on the Wikipedia LCG article in place of my "crap" which I have already removed.

When you started this thread, I assumed that you had invented your own LCG that you wanted to replace mine with in the Wikipedia list, but you apparently haven't done so. You are quite impressed by Elizabeth Rather's LCG however --- so that is obviously the one that you should replace mine with.

As I said before, all that you have to do is post the SwiftForth LCG on the Wikipedia LCG page, and your work here will be complete. Once again, here it is:

VARIABLE BUD 

: RAND  ( -- u )  BUD @  3141592621 *  1+  DUP BUD ! ; 

To make it easy for you:
You set Source to: SwiftForth (make this a link to www.forth.com)
You set M to: 2^32
You set A to: 3141592621
You set C to: 1

I promise not to undo your addition to the Wikipedia LCG article --- I have no intention of getting into an "edit war" on Wikipedia. Your victory will be complete --- a new kind of alchemy in which you turn crap into gold!

[toc] | [prev] | [next] | [standalone]

#26999

From	albert@spenarnc.xs4all.nl (Albert van der Horst)
Date	2013-11-27 11:46 +0000
Message-ID	<5295dba4$0$3202$e4fe514c@dreader36.news.xs4all.nl>
In reply to	#26992

In article <4b2f456f-3bcc-4bda-b1df-14cd8cbe41a3@googlegroups.com>,
 <hughaguilar96@yahoo.com> wrote:

<SNIP>
>
>I promise not to undo your addition to the Wikipedia LCG article --- I
>have no intention of getting into an "edit war" on Wikipedia. Your
>victory will be complete --- a new kind of alchemy in which you turn
>crap into gold!

Will you keep that promise also in case of the following:

I intend to add a balanced view of Forth LCG's plus some
general comments about LCG's. This will include your LCG
and not as an example of a bad lcg.

Promised?

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#27021

From	hughaguilar96@yahoo.com
Date	2013-11-27 18:35 -0800
Message-ID	<948262f2-b6d9-4932-8827-36272564076d@googlegroups.com>
In reply to	#26999

On Wednesday, November 27, 2013 4:46:44 AM UTC-7, Albert van der Horst wrote:
> In article <4b2f456f-3bcc-4bda-b1df-14cd8cbe41a3@googlegroups.com>,
>  <hughaguilar96@yahoo.com> wrote:
> >I promise not to undo your addition to the Wikipedia LCG article
> ...
> Will you keep that promise also in case of the following:
> 
> I intend to add a balanced view of Forth LCG's plus some
> general comments about LCG's. This will include your LCG
> and not as an example of a bad lcg.
> 
> Promised?

I intend to remove any reference to myself or my code from any Wikipedia article.

I'm not going to touch anything that doesn't involve me directly --- because I'm not a Wikipedia editor --- I already said that I consider Wikipedia editors to be people who know nothing about anything but who for psychological reasons want to be experts on everything.

Enjoy your career as a Wikipedia editor --- write all of the "balanced views" that you want to, about any subject that you want to be an expert on --- except myself or my work.

[toc] | [prev] | [next] | [standalone]

#26994

From	hughaguilar96@yahoo.com
Date	2013-11-26 21:41 -0800
Message-ID	<07bc57a5-4595-4c58-baac-169c10635c18@googlegroups.com>
In reply to	#26984

On Tuesday, November 26, 2013 2:38:09 PM UTC-7, Howerd wrote:
> On Monday, 25 November 2013 23:16:36 UTC, m...@iae.nl  wrote:
> >  [a lot of statistics]
> 
> Thanks :-)
> 
> H.

This whole thread is joke, because none of us know anything about the subject. Who cares about statistical analysis, if we don't know how the LCG parameters are derived? This has been a remarkably lengthy thread, without even a tiny flicker of intelligence yet...

I'll tell you how I invented LC53. I just set the size of the field to a big prime number (2*32-5). Then I guessed at various multipliers until I found one that provided a full period. I had a lucky guess early on, so the whole invention only took about 1 or 2 hours.

This only works for a 32-bit LCG. The field is approximately 4.2 billion, so it is possible to cycle through the whole period of the LCG in a few minutes on a fast computer. This "by guess and by golly" method doesn't work with a 64-bit LCG however, because modern computers aren't fast enough to cycle through the whole period in a reasonable amount of time. 

I notice that Donald Knuth has a 64-bit LCG in his MMIX project. How did he come up with those numbers? How can we verify that they provide a full period? I don't know, and nobody else here does either. Running the Gorilla or the DieHard or what-not statistical tests, is just pseudo-intellectual baloney --- none of this makes the tester an expert on the subject of how an LCG works --- it makes the person an ignoramus.

But I suppose that saying this makes me an "incurable troublemaker" --- so shoot the messenger!

[toc] | [prev] | [next] | [standalone]

#26996

From	Andrew Haley <andrew29@littlepinkcloud.invalid>
Date	2013-11-27 03:21 -0600
Message-ID	<o8ednS474d0GJAjPnZ2dnUVZ_hSdnZ2d@supernews.com>
In reply to	#26994

hughaguilar96@yahoo.com wrote:

> I notice that Donald Knuth has a 64-bit LCG in his MMIX project. How
> did he come up with those numbers? How can we verify that they
> provide a full period? I don't know, and nobody else here does
> either.

Yes we do, because he wrote a book about it.  If you want to know how
to choose a multiplier so as to produce a period of maximum length,
that's in 3.2.1.2.  It's Theorem A, and here it is:

The LC sequence defined by the modulus m, multiplier a, increment c,
and starting value X[0] has period length m if and only if:

1. c is relatively prime to m.

2. b = a - 1 is a multiple of p, for every prime dividing m.

3. b is a multiple of 4 if m is a multiple of 4.

> Running the Gorilla or the DieHard or what-not statistical tests, is
> just pseudo-intellectual baloney --- none of this makes the tester
> an expert on the subject of how an LCG works --- it makes the person
> an ignoramus.

More of an ignoramus than a person who publishes a random number
generator without testing it or reading Knuth?  I don't think so.

Andrew.

@book{knuth2012art,
  title={The Art of Computer Programming: Seminumerical algorithms. Vol. 2},
  author={Knuth, D.E.},
  isbn={9780321751041},
  url={http://books.google.co.uk/books?id=BpBRlAEACAAJ},
  year={2012},
  publisher={Addison-Wesley}
}

[toc] | [prev] | [next] | [standalone]

#27004

From	albert@spenarnc.xs4all.nl (Albert van der Horst)
Date	2013-11-27 15:37 +0000
Message-ID	<529611d4$0$26887$e4fe514c@dreader37.news.xs4all.nl>
In reply to	#26996

In article <o8ednS474d0GJAjPnZ2dnUVZ_hSdnZ2d@supernews.com>,
Andrew Haley  <andrew29@littlepinkcloud.invalid> wrote:
>hughaguilar96@yahoo.com wrote:
>
>> I notice that Donald Knuth has a 64-bit LCG in his MMIX project. How
>> did he come up with those numbers? How can we verify that they
>> provide a full period? I don't know, and nobody else here does
>> either.
>
>Yes we do, because he wrote a book about it.  If you want to know how
>to choose a multiplier so as to produce a period of maximum length,
>that's in 3.2.1.2.  It's Theorem A, and here it is:
>
>The LC sequence defined by the modulus m, multiplier a, increment c,
>and starting value X[0] has period length m if and only if:
>
>1. c is relatively prime to m.
>
>2. b = a - 1 is a multiple of p, for every prime dividing m.
>
>3. b is a multiple of 4 if m is a multiple of 4.

If you look into LC53 you will see that it has a c of 0 which
makes the theorem inapplicable.

Now it is even simpler:

The rng cycles through the numbers a^0 a^1 a^2 a^3 .. a^(p-1) a^p ..
mod p.  By Fermats theorem a^(p-1)=1=a^0 so we're back home.
E.g. 3^(5-1)=81 = 1 (mod 5). (Trust me it works all the time.)

Now it may be that a^n = 1 for 0<n<p-1. Then the multiplier is not
so good.
If they are all different a is called a primitive root.
The way to find a primitive root is basically trial and error,
and that is what Hugh did.
Or at least that is what I expected him to do...

But 333,333,333 is not a p.r.

I do a simple test with x^x which does powers modulo.
p-1 is divisable by 10. This makes (p-1)/10 a potential period.
Guess what?

"
   AMDX86 ciforth beta $RCSfile: ci86.gnr,v $ $Revision: 5.112 $

    OK
   1 32 LSHIFT 5 - CONSTANT P
    OK
   P .
   4294967291  OK
   1 LOAD
    OK
   WANT x^x
    OK
   333,333,333 P 1- .S

   S[ 333333333 4294967290 ] OK
   10 / .S
   S[ 333333333 429496729 ] OK
   P x^x
    OK
   .

   1 OK

"

So after (p-1)/10 cycles we are back at 1. It may be worse
but it is sufficient to shoot the multiplier down in view of
the fact that p.r. are abundant and easy to come by.

(I cancelled a post where I said that an LC53 type always has
a period of p-1. What was I thinking?)

<SNIP>

>
>Andrew.

Groetjes Albert
-- 
Albert van der Horst, UTRECHT,THE NETHERLANDS
Economic growth -- being exponential -- ultimately falters.
albert@spe&ar&c.xs4all.nl &=n http://home.hccnet.nl/a.w.m.van.der.horst

[toc] | [prev] | [next] | [standalone]

#27012

From	Bernd Paysan <bernd.paysan@gmx.de>
Date	2013-11-27 23:01 +0100
Message-ID	<l75q3m$fq9$1@online.de>
In reply to	#27004

Albert van der Horst wrote:

> (I cancelled a post where I said that an LC53 type always has
> a period of p-1. What was I thinking?)

Don't know, but actually it is pretty simple to check candidates for 
primitive roots of LC53.  Faktor p-1:

22605091*19*5*2 = 2^32-5

So for all four prime factors q, you have to test if your candidate g is

g^{(p-1)/q} mod p !== 1.

This can be done quickly.  You don't have to search that long to find a 
primitive root.

Note that Hugh's g is 2^32-333333333, don't confuse things, the sign matters 
(writing it as a negative number as Hugh does is confusing, though).  It 
*is* a primitive root of 2^32-5.  If you want to find primitive roots for 
LC53-style generators quickly, here's some code (factoring done by an 
external program, you migth want to add a sieve up to 2^16 to do the 
factoring right in the program itself):

\ Check primitive roots for lc53

$100000000 5 - Constant m

: *z ( a b -- c ) um* m um/mod drop ;
: a^b ( a b -- result ) >r 1 swap
    BEGIN  r@ 1 and IF  tuck *z swap  THEN
	dup *z r> 2/ dup WHILE  >r  REPEAT
    2drop ;

: u/ ( a b -- q )  0 swap um/mod nip ;

: checkprim ( a -- flag )
    dup m 1- 22605091 u/ a^b 1 = >r
    dup m 1-       19 u/ a^b 1 = r> or >r
    dup m 1-        5 u/ a^b 1 = r> or >r
        m 1-        2 u/ a^b 1 = r> or 0= ;

BTW: Chances are good that the prime factors of p-1 are primitive roots.  In 
this case, only 5 isn't a primitive root.  This is why people who calculate 
numbers for Diffie Hellman key exchange use a prime p in the form that 
(p-1)/2 is another prime, *and* a primitive root of p (that's just one check 
more).  This reduces the search space, and you can transmit the two 
parameters needed for Diffie Hellman in just one number - you derive the 
root g from the modulus p.

In these cases, p is a number with several thousand bits, and we still know 
that (p-1)/2 is a primitive root, and can check that quite fast.

LC53 is a maximum period linear congruent random number generator - so far, 
so good.  It has the usual problems of LCGs, so it doesn't pass any serious 
randomness test suite.  It is certainly not worse than others, but it 
definitely is slower than the mod 2^cellbits ones.  It is just a bit faster 
as the hash-based PRNG I use in Gforth-git now (benchmarked on 64 bit 
machines), which does return 64 bit numbers on a 64 bit machine, and so far 
passed all randomness tests I ran from the TestU01 suite (I didn't run the 
very time consuming DieHarder test).

-- 
Bernd Paysan
"If you want it done right, you have to do it yourself"
http://bernd-paysan.de/

[toc] | [prev] | [next] | [standalone]

Page 2 of 4 — ← Prev page 1 [2] 3 4 Next page →

csiph-web

LC53, a respectable random generator?

Contents

#26960

#26959

#26961

#26970

#26972

#27059

#26953

#26935

#26941

#26945

#26952

#26955

#26984

#26992

#26999

#27021

#26994

#26996

#27004

#27012