Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

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

Generate random number in SwiftForth & GForth

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

Contents

  Generate random number in SwiftForth & GForth Mark Wills <forthfreak@gmail.com> - 2011-12-13 13:36 -0800
    Re: Generate random number in SwiftForth & GForth "A. K." <akk@nospam.org> - 2011-12-13 22:49 +0100
      Re: Generate random number in SwiftForth & GForth Mark Wills <forthfreak@gmail.com> - 2011-12-13 14:14 -0800
        Re: Generate random number in SwiftForth & GForth Hans Bezemer <thebeez@xs4all.nl> - 2011-12-14 07:32 +0100
        Re: Generate random number in SwiftForth & GForth Arnold Doray <thinksquared@gmail.com> - 2011-12-17 05:12 +0000
          Re: Generate random number in SwiftForth & GForth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-17 03:23 -0600
            Re: Generate random number in SwiftForth & GForth Arnold Doray <thinksquared@gmail.com> - 2011-12-17 15:27 +0000
      Re: Generate random number in SwiftForth & GForth rickman <gnuarm@gmail.com> - 2011-12-14 09:05 -0800
        Re: Generate random number in SwiftForth & GForth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-14 11:43 -0600
        Re: Generate random number in SwiftForth & GForth Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-14 23:05 +0100
          Re: Generate random number in SwiftForth & GForth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-15 04:35 -0600
            Re: Generate random number in SwiftForth & GForth Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-15 22:08 +0100
              Re: Generate random number in SwiftForth & GForth Arnold Doray <thinksquared@gmail.com> - 2011-12-18 12:41 +0000
                Re: Generate random number in SwiftForth & GForth Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-18 14:58 +0100
                  Re: Generate random number in SwiftForth & GForth Arnold Doray <thinksquared@gmail.com> - 2011-12-19 00:13 +0000
                    Re: Generate random number in SwiftForth & GForth rickman <gnuarm@gmail.com> - 2011-12-19 18:20 -0800
                      Re: Generate random number in SwiftForth & GForth Arnold Doray <thinksquared@gmail.com> - 2011-12-20 16:31 +0000
                        Re: Generate random number in SwiftForth & GForth Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-20 23:45 +0100
                          Re: Generate random number in SwiftForth & GForth Arnold Doray <invalid@invalid.com> - 2011-12-21 11:19 +0000
                            Re: Generate random number in SwiftForth & GForth Paul Rubin <no.email@nospam.invalid> - 2011-12-21 03:43 -0800
                            Re: Generate random number in SwiftForth & GForth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-21 09:10 -0600
                              Re: Generate random number in SwiftForth & GForth Arnold Doray <invalid@invalid.com> - 2011-12-21 15:30 +0000
                                Re: Generate random number in SwiftForth & GForth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-21 10:45 -0600
                                  Re: Generate random number in SwiftForth & GForth Arnold Doray <invalid@invalid.com> - 2011-12-23 09:56 +0000
                                    Re: Generate random number in SwiftForth & GForth Andrew Haley <andrew29@littlepinkcloud.invalid> - 2011-12-23 04:23 -0600
                            Re: Generate random number in SwiftForth & GForth Bernd Paysan <bernd.paysan@gmx.de> - 2011-12-21 16:31 +0100
                        Re: Generate random number in SwiftForth & GForth rickman <gnuarm@gmail.com> - 2011-12-20 15:34 -0800
    Re: Generate random number in SwiftForth & GForth Roelf Toxopeus <rt4all@notthis.hetnet.nl> - 2011-12-13 23:50 +0100
      Re: Generate random number in SwiftForth & GForth "Elizabeth D. Rather" <erather@forth.com> - 2011-12-13 13:58 -1000
    Re: Generate random number in SwiftForth & GForth Brad <hwfwguy@gmail.com> - 2011-12-14 07:43 -0800

Page 1 of 2  [1] 2  Next page →

#8049 — Generate random number in SwiftForth & GForth

Is there any way to do this? I tried RND RAND & RANDOM but no luck.

Mark

[toc] | [next] | [standalone]

#8050

On 13.12.2011 22:36, Mark Wills wrote:
> Is there any way to do this? I tried RND RAND&  RANDOM but no luck.
>
> Mark

As ususal in Forth "roll your own" eg

( Fast Random Number Generator
   algorithm by George Marsaglia "Xorshift RNGs" )

2463534242 VARIABLE (RND)  \ seed

: RND  ( -- x )
    (rnd) @ dup 13 lshift xor
    dup 17 rshift xor
    dup 5 lshift xor (rnd) ! ;

Andreas

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

#8052

Thanks Andreas

I had to re-jig it slightly to get it to work. VARIABLE doesn't take an initial value (unlike a constant or a value) and an extra DUP was needed:

VARIABLE (RND)  
2463534242 (rnd) ! \ seed

: rnd ( -- n)
    (rnd) @ dup 13 lshift xor
    dup 17 rshift xor
    dup DUP 5 lshift xor (rnd) ! 
;

Happily working in both SwiftForth & GForth now. Thank you.

Mark

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

#8056

Mark Wills wrote:
This is a heavier duty randomizer. It shouldn't be very hard to port:

TIME: returns an integer, POSIX time
MAX-N: returns the largest positive signed integer
SHIFT: LSHIFT, RSHIFT when negative

S" MAX-N" ENVIRONMENT?                 \ query environment
[IF]                                   \ if successful
CONSTANT MAX-N                         \ create constant MAX-N
[ELSE]
.( Warning: MAX-N undefined) CR
[THEN]

[DEFINED] TIME&DATE [IF]
: >JD
  >R 3 - DUP 0< IF 12 + R> 1- >R THEN
  306 * 5 + 10 / + R@ 1461 4 */ + 1721116 +
  DUP 2299169 > IF 3 +  R@ 100 / -  R@ 400 / + THEN R> DROP
;

: >TIME >JD 2440588 - 86400 * >R 3600 * SWAP 60 * + + R> + ;
: TIME TIME&DATE >TIME ;
[THEN]

\ -- KISS generator --
\ http://objectmix.com/fortran/385655-random_number-intrinsic-gfortran.html
\ Algorithm 2007 by George Marsaglia
\ 4tH version 2009, Bill Cook

[UNDEFINED] kiss [IF]
variable x
variable y
variable z
variable w

max-n constant MAX-KISS

: m ( k n ** m ) over swap shift xor ;
: znew z @ dup 65535 and 18000 * swap -16 shift + dup z ! ;
: wnew w @ dup 65535 and 30903 * swap -16 shift + dup w ! ;

: seed4! w ! z ! y ! x ! ;
: seed4@ x @ y @ z @ w @ ;

: cong x @ 69069 * 1327217885 + dup x ! ;
: shr3 y @ 13 m -17 m 5 m dup y ! ;
: mwc znew 16 shift wnew + ;
: kiss mwc cong + shr3 + ;

: randomize time x ! cong y ! shr3 z ! cong w ! ;

[UNDEFINED] random [IF]
aka kiss random
MAX-KISS constant MAX-RAND
[THEN]

[DEFINED] 4th# [IF]
hide m
hide znew
hide wnew
[THEN]
[THEN]

Hans Bezemer

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

#8160

On Tue, 13 Dec 2011 14:14:04 -0800, Mark Wills wrote:

> Thanks Andreas
> 
> I had to re-jig it slightly to get it to work. VARIABLE doesn't take an
> initial value (unlike a constant or a value) and an extra DUP was
> needed:
> 
> VARIABLE (RND)
> 2463534242 (rnd) ! \ seed
> 
> : rnd ( -- n)
>     (rnd) @ dup 13 lshift xor
>     dup 17 rshift xor
>     dup DUP 5 lshift xor (rnd) !
> ;
> 
> Happily working in both SwiftForth & GForth now. Thank you.
> 
> Mark

You might have put the second DUP in the wrong place. Your results may 
still appear "random" but have undesirable/suboptimal properties. 

As Andreas' post says, this is a Xorshift RNG, which might be more 
clearly factored as: 

\ Xorshift (13,17,5)
: xorshift ( n -- n )
  dup 13 lshift xor
  dup 17 rshift xor 
  dup  5 lshift xor ; 

variable (rnd)     \ seed
2463534242 (rnd) ! \ initialize seed

: rnd ( -- n )
   (rnd) @ xorshift dup (rnd) ! ; 

The second DUP should be *after* the xorshift operation, in order to 
update the seed.

Note that zero is obviously a fixed point for any XORSHIFT operation. Ie, 

0 xorshift . 0 ok

so zero should not be used as a seed. 

Also, you might want to investigate the conditions under which a 0 could 
occur after a XORSHIFT, because if you ever hit a zero in the sequence, 
the RNG will be stuck at 0 after that. Not something you want to happen 
midway as your app runs! 

If you need zero in your pseudorandom sequence, you could translate the 
sequence by subtraction: 

: rnd-with-zero ( -- n )
  (rnd) @ xorshift dup (rnd) ! 1- ; 

Cheers,
Arnold

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

#8164

Arnold Doray <thinksquared@gmail.com> wrote:
> On Tue, 13 Dec 2011 14:14:04 -0800, Mark Wills wrote:
>
> Also, you might want to investigate the conditions under which a 0 could 
> occur after a XORSHIFT, because if you ever hit a zero in the sequence, 
> the RNG will be stuck at 0 after that. Not something you want to happen 
> midway as your app runs! 

Zero doesn't appear in the sequence; see the paper.

Andrew.

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

#8168

On Sat, 17 Dec 2011 03:23:47 -0600, Andrew Haley wrote:

> Arnold Doray <thinksquared@gmail.com> wrote:
>> On Tue, 13 Dec 2011 14:14:04 -0800, Mark Wills wrote:
>>
>> Also, you might want to investigate the conditions under which a 0
>> could occur after a XORSHIFT, because if you ever hit a zero in the
>> sequence, the RNG will be stuck at 0 after that. Not something you want
>> to happen midway as your app runs!
> 
> Zero doesn't appear in the sequence; see the paper.
> 
> Andrew.

Yes. 

Another, perhaps simpler way of seeing this is to notice that: 

x y XOR = 0 iff x = y. 

This should be obvious from the definition of the XOR operator. 

The XORSHIFT operator is composed of a sequence of three X Y XORs, each 
taking an X then left/right shifting to get Y then XOR'ing. Eg, 

X (n l/r shift X) XOR == X Y XOR

For the final operation to be zero, X must be the same as Y. Obviously, 
the only number that is the same is its right/left shifted value is zero. 

This reasoning can be applied to the other remaining 2 XORs, so you end 
up with: 

X XORSHIFT = 0 iff X = 0. 

(BTW, iff means "if and only if"). 

Cheers,
Arnold

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

#8070

On Dec 13, 4:49 pm, "A. K." <a...@nospam.org> wrote:
> On 13.12.2011 22:36, Mark Wills wrote:
>
> > Is there any way to do this? I tried RND RAND&  RANDOM but no luck.
>
> > Mark
>
> As ususal in Forth "roll your own" eg
>
> ( Fast Random Number Generator
>    algorithm by George Marsaglia "Xorshift RNGs" )
>
> 2463534242 VARIABLE (RND)  \ seed
>
> : RND  ( -- x )
>     (rnd) @ dup 13 lshift xor
>     dup 17 rshift xor
>     dup 5 lshift xor (rnd) ! ;
>
> Andreas


Are the properties of this generator important?  If so you might check
this implementation.  I don't recognize the design off the top of my
head.  Usually when pseudo random numbers are generated a maximal
length Linear Feedback Shift Register (LFSR) is used.  The above code
may well be a standard LFSR, but I've not seen this before.  If it is
not designed properly, the pattern will repeat well short of the
maximal length.  Does that matter to you?

Rick

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

#8071

rickman <gnuarm@gmail.com> wrote:
> On Dec 13, 4:49?pm, "A. K." <a...@nospam.org> wrote:
>> On 13.12.2011 22:36, Mark Wills wrote:
>>
>> > Is there any way to do this? I tried RND RAND&  RANDOM but no luck.
>>
>> > Mark
>>
>> As ususal in Forth "roll your own" eg
>>
>> ( Fast Random Number Generator
>>    algorithm by George Marsaglia "Xorshift RNGs" )
>>
>> 2463534242 VARIABLE (RND)  \ seed
>>
>> : RND  ( -- x )
>>     (rnd) @ dup 13 lshift xor
>>     dup 17 rshift xor
>>     dup 5 lshift xor (rnd) ! ;
> 
> Are the properties of this generator important?  If so you might
> check this implementation.  I don't recognize the design off the top
> of my head.  Usually when pseudo random numbers are generated a
> maximal length Linear Feedback Shift Register (LFSR) is used.  The
> above code may well be a standard LFSR, but I've not seen this
> before.  If it is not designed properly, the pattern will repeat
> well short of the maximal length.

http://en.wikipedia.org/wiki/George_Marsaglia

It is designed properly, I assure you.

Enjoy: www.jstatsoft.org/v08/i14/paper

Andrew.

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

#8076

rickman wrote:

> On Dec 13, 4:49 pm, "A. K." <a...@nospam.org> wrote:
>> ( Fast Random Number Generator
>> algorithm by George Marsaglia "Xorshift RNGs" )
>>
>> 2463534242 VARIABLE (RND)  \ seed
>>
>> : RND  ( -- x )
>> (rnd) @ dup 13 lshift xor
>> dup 17 rshift xor
>> dup 5 lshift xor (rnd) ! ;
>>
>> Andreas
[...]
> The above code
> may well be a standard LFSR, but I've not seen this before.  If it is
> not designed properly, the pattern will repeat well short of the
> maximal length.  Does that matter to you?

This is an xorshift random number generator, and this is significantly 
better than an LFSR.  It does have the maximum length, and it does not 
have the funny property of LFSRs that many "random" numbers are just 
twice the previous random number.

The source code above misses a ! between "(RND)" and "\ seed"

That's my version, it uses different shift counts, but there are many.  
This is a expicit 32 bit RNG, which is made 32 bit even on 64 bit 
systems:

Variable seed  $3f98c5ac seed !

: xorshift ( n -- n' )
    dup 1 lshift xor $FFFFFFFF and
    dup 3 rshift xor
    dup 10 lshift xor $FFFFFFFF and ;
: rnd  seed @ xorshift dup seed ! ;

What I don't like with xorshift: 0 is not a legal starting point, just 
like LFSR, the algorithm is stuck at 0.  I didn't do any investigation 
into this problem, but maybe inverting the value at the end of the logic 
could solve that problem.

My cryptographic hard Wurstkessel RNG (proven to be "good" with the 
dieharder suite, the actual cryptographic peer review is still pending - 
but when I look at all the problems AES has, I don't really trust that 
sort of peer review, either ;-) with all optimizations on is 6 times 
slower than this xorshift RNG, using gforth-fast (maybe it could be only 
4 or 5 times slower if I generate more than 64 bytes at a time).  But 
for all serious random number stuff, using such a more complex, but 
proven RNG is a good idea - simple algorithms fail pretty soon in this 
test suite, and the artefacts they display there also may show up in 
your program.

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

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

#8085

Bernd Paysan <bernd.paysan@gmx.de> wrote:
> rickman wrote:
> 
>> On Dec 13, 4:49 pm, "A. K." <a...@nospam.org> wrote:
>>> ( Fast Random Number Generator
>>> algorithm by George Marsaglia "Xorshift RNGs" )
>>>
>>> 2463534242 VARIABLE (RND)  \ seed
>>>
>>> : RND  ( -- x )
>>> (rnd) @ dup 13 lshift xor
>>> dup 17 rshift xor
>>> dup 5 lshift xor (rnd) ! ;
>>>
>>> Andreas
> [...]
>> The above code
>> may well be a standard LFSR, but I've not seen this before.  If it is
>> not designed properly, the pattern will repeat well short of the
>> maximal length.  Does that matter to you?
> 
> This is an xorshift random number generator, and this is significantly 
> better than an LFSR.  It does have the maximum length, and it does not 
> have the funny property of LFSRs that many "random" numbers are just 
> twice the previous random number.

https://groups.google.com/group/comp.lang.forth/msg/cc7dec31fa374841?hl=en

Brent proved that for every XOR-shift generator there is an
equivalent LFSR.  However, the XOR-shift form is more efficient in
software than in its LFSR form.

Andrew.

Richard P. Brent, Note on Marsaglia's Xorshift Random Number
Generators, JSS 2004 

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

#8123

Andrew Haley wrote:
> Brent proved that for every XOR-shift generator there is an
> equivalent LFSR.  However, the XOR-shift form is more efficient in
> software than in its LFSR form.

I'm not convinced.  A single LFSR goes from state n to 2n when the MSB 
of n is not set (or, when the shift direction is the other way round, 
from 2n to n, when the LSB of n is not set).  Xorshift RNGs don't, they 
have no such trivial relationship between two results.

LFSRs are easier to implement than xorshift generators, but have this 
additional awkward property.

Brent gives an equvalent to the (1,3,10) xorshift RNG, which is what I 
have used.  This time for 32 bit systems only:

: xorshift ( n -- n' )
    dup 1 lshift xor
    dup 3 rshift xor
    dup 10 lshift xor ;

This should be the equivalent LFSR, if I believe in Brent's paper:

$382d1e61 constant lfsr-eq \ polynom from the Brent paper
: lfsr  dup 0< IF  2* lfsr-eq xor  ELSE  2*   THEN  ;

If the clamed equivalence is true, xorshift and lfsr should perform the 
same function.  I use a Forth approach to math: let's try.  For 
simplicity I use 1 as starting point:

hex 1  ok
xorshift dup u. C03  ok
xorshift dup u. 5A0285  ok
xorshift dup u. CFEE3F7E  ok
xorshift dup u. 8A12C1B2  ok
xorshift dup u. 4B5B9A8C  ok
xorshift dup u. 82B8A266  ok
xorshift dup u. 5459267F  ok
xorshift dup u. 3B6943D1  ok
xorshift dup u. 76FF48FD  ok
drop 1  ok
lfsr dup u. 2  ok
lfsr dup u. 4  ok
lfsr dup u. 8  ok
lfsr dup u. 10  ok
lfsr dup u. 20  ok
lfsr dup u. 40  ok
lfsr dup u. 80  ok
lfsr dup u. 100  ok

I think we can stop here, and we have not even used the polynom Brent 
proposed.  Any LFSR will output this sequence with the starting point 1.

These are not equivalent functions.  Whatever equivalence Brent has 
proven, it's not functional equivalence.  I'm pretty sure I know what an 
LFSR is, so I don't think there is a misunderstanding.  Did Brent test 
his calculations?  I mean, in the way we understand testing a Forth 
program?

LFSRs have somewhat better properties when you use only the MSB.

: lfsr-seq ( seed rnd -- seed' rnd' )
  2dup d+ dup 1 and IF  swap lfsr-eq xor swap  THEN ;
: gen-seq ( seed -- seed' rnd ) 0 $20 0 do lfsr-seq loop ;

If we start with 1, we will get 1 as first result.

1 gen-seq u. 1  ok
gen-seq u. 3DA97C19  ok
gen-seq u. 53BD8241  ok
gen-seq u. 879B88CF  ok
gen-seq u. 37AE719E  ok
gen-seq u. 9E525CC9  ok
gen-seq u. 36E8CFAB  ok
gen-seq u. 1AFFC028  ok
gen-seq u. E86DFC12  ok

These results look better than the xorshift RNG, but they are way more 
costly, and the cycle length is also smaller (only 2^(32-5) values).

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

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

#8190

On Thu, 15 Dec 2011 22:08:12 +0100, Bernd Paysan wrote:

> This should be the equivalent LFSR, if I believe in Brent's paper:
> 
> $382d1e61 constant lfsr-eq \ polynom from the Brent paper 
> : lfsr  dup 0< IF  2* lfsr-eq xor  ELSE  2*   THEN  ;
> 

The heart of Brent's paper ( http://maths.anu.edu.au/~brent/pd/
rpb218.pdf ) is quite simple, if not trivial -- see Section 5. 

He starts with the definition of the minimal polynomial for T, the 
XORSHIFT operator, and with trivial manipulations, obtains a recurrence 
relation that he asserts defines a LFSR. It's airtight. The equivalence 
should be exact. 

Unfortunately, his paper only defines the LFSR for a bitstream, while 
this recurrence relation is for a sequence of bitvectors. 

What's less clear (at least to me) is how to get from this recurrence 
relation of his to your LFSR function. Would you care to elaborate? 

Thanks,
Arnold

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

#8193

Arnold Doray wrote:

> On Thu, 15 Dec 2011 22:08:12 +0100, Bernd Paysan wrote:
> 
>> This should be the equivalent LFSR, if I believe in Brent's paper:
>> 
>> $382d1e61 constant lfsr-eq \ polynom from the Brent paper
>> : lfsr  dup 0< IF  2* lfsr-eq xor  ELSE  2*   THEN  ;
>> 
> 
> The heart of Brent's paper ( http://maths.anu.edu.au/~brent/pd/
> rpb218.pdf ) is quite simple, if not trivial -- see Section 5.
> 
> He starts with the definition of the minimal polynomial for T, the
> XORSHIFT operator, and with trivial manipulations, obtains a
> recurrence relation that he asserts defines a LFSR. It's airtight. The
> equivalence should be exact.
> 
> Unfortunately, his paper only defines the LFSR for a bitstream, while
> this recurrence relation is for a sequence of bitvectors.
> 
> What's less clear (at least to me) is how to get from this recurrence
> relation of his to your LFSR function. Would you care to elaborate?

Hm, I found the clue:

"In hardware implementations of LFSR sequences, the x_j are usually 
single bits (elements of F2), but in software implementations it is easy 
and more efficient to operate on whole words." (Page 3, first sentence)

So what I did is an LFSR as implemented in hardware, with single bits 
x_j.  Where Brent assumes is that "it is easy and more efficient to 
operate on whole words."  No, that's wrong.  It is easy and efficient in 
software to operate on bits (since the appropriate parallelized bit 
vector operations are available), see above definition of a software-
defined bit-wise LFSR.

So he proved the equivalence of xorshift with something that 
mathematically resembles an LFSR, but actually is not a "normal" LFSR, 
because the x_j are bit vectors, not bits.

As I said, I'm not convinced.  LFSRs are sequences of bits, not of bit 
vectors.  Redefining a concept but not changing the name is at least 
misleading.  The term "LFSR" is extremely well defined, and its 
definition is very narrow.

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

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

#8203

On Sun, 18 Dec 2011 14:58:50 +0100, Bernd Paysan wrote:

> Arnold Doray wrote:
> 
>> On Thu, 15 Dec 2011 22:08:12 +0100, Bernd Paysan wrote:
>> 
>>> This should be the equivalent LFSR, if I believe in Brent's paper:
>>> 
>>> $382d1e61 constant lfsr-eq \ polynom from the Brent paper : lfsr  dup
>>> 0< IF  2* lfsr-eq xor  ELSE  2*   THEN  ;
>>> 
>>> 
>> The heart of Brent's paper ( http://maths.anu.edu.au/~brent/pd/
>> rpb218.pdf ) is quite simple, if not trivial -- see Section 5.
>> 
>> He starts with the definition of the minimal polynomial for T, the
>> XORSHIFT operator, and with trivial manipulations, obtains a recurrence
>> relation that he asserts defines a LFSR. It's airtight. The equivalence
>> should be exact.
>> 
>> Unfortunately, his paper only defines the LFSR for a bitstream, while
>> this recurrence relation is for a sequence of bitvectors.
>> 
>> What's less clear (at least to me) is how to get from this recurrence
>> relation of his to your LFSR function. Would you care to elaborate?
> 
> Hm, I found the clue:
> 
> "In hardware implementations of LFSR sequences, the x_j are usually
> single bits (elements of F2), but in software implementations it is easy
> and more efficient to operate on whole words." (Page 3, first sentence)
> 
> So what I did is an LFSR as implemented in hardware, with single bits
> x_j.  Where Brent assumes is that "it is easy and more efficient to
> operate on whole words."  No, that's wrong.  It is easy and efficient in
> software to operate on bits (since the appropriate parallelized bit
> vector operations are available), see above definition of a software-
> defined bit-wise LFSR.
> 
> So he proved the equivalence of xorshift with something that
> mathematically resembles an LFSR, but actually is not a "normal" LFSR,
> because the x_j are bit vectors, not bits.
> 
> As I said, I'm not convinced.  LFSRs are sequences of bits, not of bit
> vectors.  Redefining a concept but not changing the name is at least
> misleading.  The term "LFSR" is extremely well defined, and its
> definition is very narrow.

Brent's results imply that some "word LFSR"s (at the very least those 
corresponding to xorshift operators) do not have the nasty 'doubling' 
subsequences that "bitstream LFSR"s have for positive integers. 

In fact, Brent's result is actually very general -- *any* stateless RNG 
that can be written as the action of a matrix on a bitvector is 
equivalent to some "word LFSR". So, if you have a rule to identify "good" 
word LFSRs, you could then know if your specific stateless RNG is also 
"good". 

Cheers,
Arnold

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

#8235

On Dec 18, 7:13 pm, Arnold Doray <thinksqua...@gmail.com> wrote:
> On Sun, 18 Dec 2011 14:58:50 +0100, Bernd Paysan wrote:
> > Arnold Doray wrote:
>
> >> On Thu, 15 Dec 2011 22:08:12 +0100, Bernd Paysan wrote:
>
> >>> This should be the equivalent LFSR, if I believe in Brent's paper:
>
> >>> $382d1e61 constant lfsr-eq \ polynom from the Brent paper : lfsr  dup
> >>> 0< IF  2* lfsr-eq xor  ELSE  2*   THEN  ;
>
> >> The heart of Brent's paper (http://maths.anu.edu.au/~brent/pd/
> >> rpb218.pdf ) is quite simple, if not trivial -- see Section 5.
>
> >> He starts with the definition of the minimal polynomial for T, the
> >> XORSHIFT operator, and with trivial manipulations, obtains a recurrence
> >> relation that he asserts defines a LFSR. It's airtight. The equivalence
> >> should be exact.
>
> >> Unfortunately, his paper only defines the LFSR for a bitstream, while
> >> this recurrence relation is for a sequence of bitvectors.
>
> >> What's less clear (at least to me) is how to get from this recurrence
> >> relation of his to your LFSR function. Would you care to elaborate?
>
> > Hm, I found the clue:
>
> > "In hardware implementations of LFSR sequences, the x_j are usually
> > single bits (elements of F2), but in software implementations it is easy
> > and more efficient to operate on whole words." (Page 3, first sentence)
>
> > So what I did is an LFSR as implemented in hardware, with single bits
> > x_j.  Where Brent assumes is that "it is easy and more efficient to
> > operate on whole words."  No, that's wrong.  It is easy and efficient in
> > software to operate on bits (since the appropriate parallelized bit
> > vector operations are available), see above definition of a software-
> > defined bit-wise LFSR.
>
> > So he proved the equivalence of xorshift with something that
> > mathematically resembles an LFSR, but actually is not a "normal" LFSR,
> > because the x_j are bit vectors, not bits.
>
> > As I said, I'm not convinced.  LFSRs are sequences of bits, not of bit
> > vectors.  Redefining a concept but not changing the name is at least
> > misleading.  The term "LFSR" is extremely well defined, and its
> > definition is very narrow.
>
> Brent's results imply that some "word LFSR"s (at the very least those
> corresponding to xorshift operators) do not have the nasty 'doubling'
> subsequences that "bitstream LFSR"s have for positive integers.
>
> In fact, Brent's result is actually very general -- *any* stateless RNG
> that can be written as the action of a matrix on a bitvector is
> equivalent to some "word LFSR". So, if you have a rule to identify "good"
> word LFSRs, you could then know if your specific stateless RNG is also
> "good".
>
> Cheers,
> Arnold

I don't feel like digging into all the terminology to understand this
at the level that you all seem to.  But LFSR's, at least the useful
ones, are "maximal length".  If your xor-shift generator is also
maximal length, won't they generate the same pattern?  I haven't given
this a lot of thought so I may be missing something obvious.

Rick

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

#8253

On Mon, 19 Dec 2011 18:20:20 -0800, rickman wrote:

> don't feel like digging into all the terminology to understand this at
> the level that you all seem to.  But LFSR's, at least the useful ones,
> are "maximal length".  If your xor-shift generator is also maximal
> length, won't they generate the same pattern?  I haven't given this a
> lot of thought so I may be missing something obvious.

The Xor-Shift RNG is Marsaglia's invention, not mine. He was a guru on 
RNGs.

To answer your question, just because 2 RNGs are 'maximal length' doesn't 
mean they necessarily produce the same sequence/pattern. 

An "RNG" is just a number generator. 

The "random" part is a largely subjective set of  criteria that you need 
to test for depending on your usage of that sequence. Of course, the 
usual meaning is that each term in the sequence should be i.i.d, but this 
is not an algorithmic prescription. That's why you need tests like 
"Diehard" (also Marsaglia's invention). It is by no means easy to ensure 
i.i.d, unless your source is truly random like thermal noise. But even 
this has correlations, yes? I don't believe any natural source of noise 
is truly "white" (ie, the autocorrelation is a delta function). 

So what you're saying is that two number generators produce the same 
sequence just because they are both 'maximal length'. 

"Maximal length" means that the sequence repeats after N items, where N 
is the size of the space. Eg, for an K bit vector, N = 2^K. 

Put this way, you can see your assertion is obviously false. A simple 
counterexample: in the space {0,1,2}, (whose N = 3) the sequences: 

0 1 2 0 1 2 ... and 0 2 1 0 2 1 ... are both maximal length, but 
obviously not the same. The stateless number generators for these are: 

: 3mod  1+ 3 mod ; \ for the first.
: 3mod+ 1+  3mod ; \ for the second.

BTW, the exact equivalence proved by Brent is between *word* (ie, 
bitvector) LFSRs and xorshift RNGs. These LFSRs are not the same as 
bitstream LFSRs.

You have to prove equivalence on a case-by-case basis. 

Cheers,
Arnold

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

#8267

Arnold Doray wrote:
> To answer your question, just because 2 RNGs are 'maximal length'
> doesn't mean they necessarily produce the same sequence/pattern.

In fact, "maximal length" here is about the maximum achievable length of 
an xorshift or LFSR RNG pattern length - it's actually 2^n-1 for a bit 
width of n (0 is not a member of the output sequence).  For an LFSR, you 
need a primitive polynom to be maximal length, and for an xorshift RNG, 
only a small subset of the three shift numbers give you maximal length, 
so you have to choose carefully.

And about the sequence: For a sequence length of n, there are n! 
possible sequences.  So there really is an abundance of possibilities to 
generate a 2^n-1 length sequence of all numbers between 1 and 2^n-1.

As random number generators, these sequence generators have a number of 
shortcomings.  The first is that their output really is a long sequence, 
which means that the same number will not occur again within the 
sequence length.  Therefore they will fairly quickly fail on a birthday 
paradoxon test.  The birthday paradoxon says that the likelyhood of two 
times the same 32 bit number in a stream of just 64k numbers is 50%.  
Run this test often enough, and you should be fairly close to this 50% 
figure (i.e. if you run 100 times this test, you should have 50 "twins" 
as result).  An xorshift or LFSR RNG will result in 0%.

This is a quick-and-dirty test for a 32 bit RNG, called by the generic 
word rng32 (you can alias your RNG to that):

Create buckets $40000 cells allot
Variable twins

: bucket! ( n addr -- )
    2dup @ = IF  1 twins +!  THEN  ! ;

: push-bucket ( n -- )
    dup $e rshift cells buckets + bucket! ;

: test-rng ( n -- )
    buckets $40000 cells erase
    0 ?DO  rng32 push-bucket  LOOP ;

: tests ( n -- )  twins off
    0 ?DO  $10000 test-rng  LOOP  twins ? ;

This test has some false negatives, as I don't chain my buckets.  
Running this 1000 times with my Wurstkessel rng resulted in a "too good 
to be true" 500 twins result (this is with the static test seed for 
reproduction).

The diehard and dieharder test suites have a lot more such tests.  What 
I'm doing as well (this is not part of these test suites) is an FFT and 
looking at the spectrum.  The frequency distribution should be almost 
flat, almost the same everywhere with a gaussian distribution, and the 
standard deviation of this distribution should be close to the 
theoretically expected one.

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

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

#8273

On Tue, 20 Dec 2011 23:45:45 +0100, Bernd Paysan wrote:

> 
> And about the sequence: For a sequence length of n, there are n!
> possible sequences.  So there really is an abundance of possibilities to
> generate a 2^n-1 length sequence of all numbers between 1 and 2^n-1.
> 
> As random number generators, these sequence generators have a number of
> shortcomings.  The first is that their output really is a long sequence,
> which means that the same number will not occur again within the
> sequence length.  Therefore they will fairly quickly fail on a birthday
> paradoxon test.  The birthday paradoxon says that the likelyhood of two
> times the same 32 bit number in a stream of just 64k numbers is 50%. Run
> this test often enough, and you should be fairly close to this 50%
> figure (i.e. if you run 100 times this test, you should have 50 "twins"
> as result).  An xorshift or LFSR RNG will result in 0%.
> 

Yes, that's a good point. Quite a departure from i.i.d behaviour!

You might be able to partly alleviate this problem by wraping the 
sequence to a shorter length, eg by using a RNG N MOD. The results might 
be better for N << 2^K . 


> This is a quick-and-dirty test for a 32 bit RNG, called by the generic
> word rng32 (you can alias your RNG to that):
> 
> Create buckets $40000 cells allot Variable twins
> 
> : bucket! ( n addr -- )
>     2dup @ = IF  1 twins +!  THEN  ! ;
> 
> : push-bucket ( n -- )
>     dup $e rshift cells buckets + bucket! ;
> 
> : test-rng ( n -- )
>     buckets $40000 cells erase 0 ?DO  rng32 push-bucket  LOOP ;
> 
> : tests ( n -- )  twins off
>     0 ?DO  $10000 test-rng  LOOP  twins ? ;
> 
> This test has some false negatives, as I don't chain my buckets. Running
> this 1000 times with my Wurstkessel rng resulted in a "too good to be
> true" 500 twins result (this is with the static test seed for
> reproduction).

Probably because Wurstkessel is not stateless like Xorshift? :)

> 
> The diehard and dieharder test suites have a lot more such tests.  What
> I'm doing as well (this is not part of these test suites) is an FFT and
> looking at the spectrum.  The frequency distribution should be almost
> flat, 

An interesting test since it may pick up the doubling subsequences in 
your bitstream LFSRs. 

You might use the spectrum's entropy as a measure of flatness.

Cheers,
Arnold

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

#8275

Arnold Doray <invalid@invalid.com> writes:
>> paradoxon test.  The birthday paradoxon says that the likelyhood of two
>> times the same 32 bit number in a stream of just 64k numbers is 50%....
>> An xorshift or LFSR RNG will result in 0%...
>
> You might be able to partly alleviate this problem by wraping the 
> sequence to a shorter length, eg by using a RNG N MOD. The results might 
> be better for N << 2^K . 

In cryptography the standard approach is just make the period big enough
that the discrepancy won't be noticed (e.g. 2**128 in the case of AES).
A result called the PRP-PRF Switching Lemma shows that other than this
O(2**64) birthday test or something else equally slow, there's no way to
distinguish a (pseudo) random permutation from a PRF (i.e. RNG).

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

Page 1 of 2  [1] 2  Next page →

Back to top | Article view | comp.lang.forth

csiph-web