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

Groups > comp.lang.forth > #8076

Re: Generate random number in SwiftForth & GForth

Show all headers | View raw

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/

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