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

Groups > comp.lang.forth > #8123

Re: Generate random number in SwiftForth & GForth

Show all headers | View raw

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/

Back to comp.lang.forth | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web