Pseudo Random Number Generator test results
Howerd
I ran the following code past Diehard :
variable MyRandom
\ Marsaglia, "Xorshift RNGs". http://www.jstatsoft.org/v08/i14/paper
: NewRandom ( -- u )
MyRandom @
dup 13 lshift xor invert
dup 17 rshift xor
dup 5 lshift xor invert
dup MyRandom ! ;
The text file of the results are here : http://www.inventio.co.uk/myrandxor.txt
My own summary is that it looks very good :-)
Andrew : Thanks for posting the link...
Best regards,
Howerd
Howerd
Human error strikes again - the inverts are not required. Being a pair
the result is identical the code without them...
I ran the following code past Diehard :
variable MyRandom
\ Marsaglia, "Xorshift RNGs". http://www.jstatsoft.org/v08/i14/paper
: NewRandom ( -- u )
MyRandom @
dup 13 lshift xor
dup 17 rshift xor
dup 5 lshift xor
dup MyRandom ! ;
The text file of the results are here : http://www.inventio.co.uk/myrandxor.txt
My own summary is that it looks very good :-)
Andrew : Thanks for posting the link...
Best regards,
Howerd
Brad
> : NewRandom ( -- u )
> MyRandom @
> dup 13 lshift xor invert
> dup 17 rshift xor
> dup 5 lshift xor invert
> dup MyRandom ! ;
It looks a lot like what hardware guys call a LFSR. The frequency
spectrum of a LFSR isn't flat, but in many apps, who cares? Thanks for
the code.
-Brad
Hugh Aguilar
> I ran the following code past Diehard :
>
> variable MyRandom
>
> \ Marsaglia, "Xorshift RNGs". http://www.jstatsoft.org/v08/i14/paper
> : NewRandom ( -- u )
> MyRandom @
> dup 13 lshift xor
> dup 17 rshift xor
> dup 5 lshift xor
> dup MyRandom ! ;
>
> The text file of the results are here :http://www.inventio.co.uk/myrandxor.txt
I haven't heard of Diehard --- is that a test suite for prngs? I would
be interested in seeing how my LC53 tests out. It is a linear-
congruential that takes advantage of Forth's mixed-precision
arithmetic. Is your prng 32-bit or 16-bit?
Andreas
> On Mar 9, 11:52 am, Howerd<howe...@yahoo.co.uk> wrote:
>> : NewRandom ( -- u )
>> MyRandom @
>> dup 13 lshift xor invert
>> dup 17 rshift xor
>> dup 5 lshift xor invert
>> dup MyRandom ! ;
>
> It looks a lot like what hardware guys call a LFSR.
That's exactly not the case here. Pseudo random number generators with
LFSRs process individual bits from selected positions (based on prime
numbers represented by binary polynomials, to simplify it) and feed them
back into the shifted seed, ad "infinitum" = 2^n-1 times.
The XOR-shifter is very much simpler to build.
Andreas
Brad
> That's exactly not the case here. Pseudo random number generators with
> LFSRs process individual bits from selected positions (based on prime
> numbers represented by binary polynomials, to simplify it) and feed them
> back into the shifted seed, ad "infinitum" = 2^n-1 times.
>
> The XOR-shifter is very much simpler to build.
Well, that is very cool. I'll be hanging on to this.
-Brad
Stephen Pelc
wrote:
>: NewRandom ( -- u )
> MyRandom @
> dup 13 lshift xor
> dup 17 rshift xor
> dup 5 lshift xor
> dup MyRandom ! ;
Now set
0 MyRandom !
and try again.
Stephen
--
Stephen Pelc, steph...@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads
The Beez'
Sorry to spoil the fun, but according to George himself, there are
still pattern in this shifter. As a matter of fact his "ordinary" KISS
(AFAIK there are at least two successors) contains this randomizer as
a COMPONENT. Here is the code, it shouldn't be too hard too port IMHO:
\ -- 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
Andrew Haley
> On Mar 9, 7:52?pm, Howerd <howe...@yahoo.co.uk> wrote:
> Sorry to spoil the fun, but according to George himself, there are
> still pattern in this shifter.
Well, of course: it's simple and small. But, for a low-cost RNG it's
excellent, and it might even be optimum in some cases.
I just heard that George Marsaglia died in Tallahassee on February 15.
He kept up posting about randomness and statistics until the end of
his life. I think this is his last posting:
http://groups.google.com/group/sci.math/msg/eb5b7c32517b8820?hl=ene47e0d8327548aa
Andrew.
Howerd
I feel like I am battling against an unknown enemy here - maybe its
tiredness, or a series of senior moments...
It seems that the inverts are important, even though I put them in
because I mis-read the C code.
I think when I re-created the random file using the code without the
inverts I got the filename or location wrong, and incorrectly said
that the files were identical.
I also incorrectly assumed that the two inverts would cancel out -
clearly they do not with an initial value of 0.
I have posted all of the improved code that I used below - as you can
see I initialise MyRandom to 0 , as it is a special case and most
likely to be pathological, since the shifts do not set any bits high,
just low.
There is now only one invert - it seems to be just as good as the code
with two, and is slightly faster than Andrew's original 0= test.
Diehard is a randomness test suite by George Marsaglia and is
available here : http://www.stat.fsu.edu/pub/diehard/
I ran the following code past Diehard :
\ Testing PRNG 2011 Mar 10
variable MyRandom
decimal
\ Marsaglia, "Xorshift RNGs". http://www.jstatsoft.org/v08/i14/paper
: NewRandom ( -- u )
MyRandom @
dup 13 lshift xor
dup 17 rshift xor
invert
dup 5 lshift xor
dup MyRandom ! ;
1024 Buffer: RandomBlock
: FillRandomBlock ( -- ) RandomBlock 1024 0 do NewRandom over i
+ ! cell +loop drop ;
\ create a random number file for Diehard tests
: TTRandomFile
s" MyRandXor.rnd" R/W CREATE-FILE abort" Cannot create the file!"
0 MyRandom !
11 1024 * ( 11 Mbyte ) 0 do
FillRandomBlock
RandomBlock over 1024 swap WRITE-FILE abort" Cannot write to
file!"
loop
CLOSE-FILE abort" Cannot close the file!"
;
The text file of the results are here : http://www.inventio.co.uk/myrandxor.txt
and the Forth file is here : http://www.inventio.co.uk/prngxor.f
My own summary is that it looks very good :-)
Andrew : Thanks for posting the original link...
If anyone can interpret the C code and text of the paper into
*working* code it would be good, but the correction of the apparent
typo in the paper, combined with an invert to handle the 0 case seems
to create a good PRNG.
I will leave it as an exercise for the reader(s) to run translate the
KISS code into Forth, and pass Hugh's LC53 code to Diehard ...
Thanks to everyone for their comments and corrections :-)
Best regards,
Howerd
On Mar 10, 7:21 am, "The Beez'" <hans...@bigfoot.com> wrote:
> On Mar 9, 7:52 pm, Howerd <howe...@yahoo.co.uk> wrote:
> Sorry to spoil the fun, but according to George himself, there are
> still pattern in this shifter. As a matter of fact his "ordinary" KISS
> (AFAIK there are at least two successors) contains this randomizer as
> a COMPONENT. Here is the code, it shouldn't be too hard too port IMHO:
>
> \ -- KISS generator --
> \http://objectmix.com/fortran/385655-random_number-intrinsic-gfortran....
Howerd
Thanks for the comments.
I think what I am looking for here is a simple PRNG for general
purpose applications.
I suspect that George Marsaglia is setting his sights much higher.
When I ran the PRNG that I was using through Diehard it is clearly not
very good :
: NewRandom ( - u )
MyRandom @
69069 * 1+
dup MyRandom !
;
This also uses a multiplication rather than shifts, xors and inverts.
And yes - I just noticed that the KISS code is already in Forth :-(
Randomness is an interesting subject - there does not seem to be an
absolute way of judging randomness, by definition...
Best regards,
Howerd
On Mar 10, 7:21 am, "The Beez'" <hans...@bigfoot.com> wrote:
> On Mar 9, 7:52 pm, Howerd <howe...@yahoo.co.uk> wrote:
> Sorry to spoil the fun, but according to George himself, there are
> still pattern in this shifter. As a matter of fact his "ordinary" KISS
> (AFAIK there are at least two successors) contains this randomizer as
> a COMPONENT. Here is the code, it shouldn't be too hard too port IMHO:
>
> \ -- KISS generator --
> \http://objectmix.com/fortran/385655-random_number-intrinsic-gfortran....
Howerd
The code is 32 bit, there is also a 64 bit version in the original
paper.
I look forward to seeing the LC53 results from Diehard :-)
Best regards,
Howerd
Andrew Haley
> If anyone can interpret the C code and text of the paper into
> *working* code
Damn it all to hell and back, I already did! In the first message you
replied to. WTF?
> it would be good, but the correction of the apparent typo in the
> paper, combined with an invert to handle the 0 case seems to create
> a good PRNG.
The INVERT is wrong.
unsigned long xor(){
static unsigned long y=2463534242;
y^=(y<<13); y^=(y>>17); return (y^=(y<<5)); }
becomes
variable y 2463534242 y !
: xor ( - u)
y @
dup 13 lshift xor
dup 17 rshift xor
dup 5 lshift xor
dup y ! ;
The 0 case doesn't need handling because it's not part of the cycle.
Your INVERT, however, will produce a 0 where one did not appear in the
original generator. I would leave it as it is if I were you.
Andrew.
Howerd
I can see why you are annoyed - you corrected the typo in your code,
then I go and break it all... Sorry...
> The 0 case doesn't need handling because it's not part of the cycle.
This means that if the value ever gets to 0 the PRNG sticks at 0.
It also means that the PRNG can never give a 0 ( well I suppose it
could give one, then die).
How do you know that 0 is not part of the cycle? No doubt this is
covered in the paper.
> The INVERT is wrong.
Adding the invert handles the 0 case, and seems not to give bad p-
values in the Diehard tests.
In what way is that wrong?
> Your INVERT, however, will produce a 0 where one did not appear in the
> original generator.
Yes - 0 is a valid number within the range of the PRNG.
>I would leave it as it is if I were you.
Well maybe, but I would have to understand why the sequence would
never hit 0, and for ever be aware that the seed value has a
pathological special case...
Normally I use the system clock or other asynchronous value as the
seed - I don't want to have to test it for zero in case it breaks the
PRNG.
Anyway, fascinating stuff - I must get back to work now :-)
Best regards,
Howerd
On Mar 10, 10:48 am, Andrew Haley <andre...@littlepinkcloud.invalid>
wrote:
Andrew Haley
>
> I can see why you are annoyed - you corrected the typo in your code,
> then I go and break it all... Sorry...
>
>> The 0 case doesn't need handling because it's not part of the cycle.
> This means that if the value ever gets to 0 the PRNG sticks at 0.
> It also means that the PRNG can never give a 0 ( well I suppose it
> could give one, then die).
> How do you know that 0 is not part of the cycle? No doubt this is
> covered in the paper.
That's right: the period of the generator is 2^32-1, and therefore
includes all numbers from 1 to 0ffffffff inclusive.
>> The INVERT is wrong.
> Adding the invert handles the 0 case, and seems not to give bad p-
> values in the Diehard tests.
> In what way is that wrong?
Well, it's different, and it creates a different generator. Will this
generator get stuck in a short cycle, or even a fixed point? Off the
top of my head, I can't tell.
>> Your INVERT, however, will produce a 0 where one did not appear in the
>> original generator.
> Yes - 0 is a valid number within the range of the PRNG.
And does your generator then have a full period? If not, what period
does it have?
>>I would leave it as it is if I were you.
> Well maybe, but I would have to understand why the sequence would
> never hit 0, and for ever be aware that the seed value has a
> pathological special case...
So why not use the version I provided? It has all of the nice
properties of the Marsaglia generator and works with any initial
seed.
Andrew.
Andrew Haley
> On Mar 9, 11:52?am, Howerd <howe...@yahoo.co.uk> wrote:
>> : NewRandom ( -- u )
>> MyRandom @
>> dup 13 lshift xor invert
>> dup 17 rshift xor
>> dup 5 lshift xor invert
>> dup MyRandom ! ;
>
> It looks a lot like what hardware guys call a LFSR.
It is. 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
Alex McDonald
> Hi The Beez,
>
> Thanks for the comments.
> I think what I am looking for here is a simple PRNG for general
> purpose applications.
> I suspect that George Marsaglia is setting his sights much higher.
> When I ran the PRNG that I was using through Diehard it is clearly not
> very good :
>
> : NewRandom ( - u )
> MyRandom @
> 69069 * 1+
> dup MyRandom !
> ;
>
> This also uses a multiplication rather than shifts, xors and inverts.
>
> And yes - I just noticed that the KISS code is already in Forth :-(
>
> Randomness is an interesting subject - there does not seem to be an
> absolute way of judging randomness, by definition...
>
There are means to judge. http://en.wikipedia.org/wiki/Algorithmically_random_sequence
Howerd
Yes - you are right.
I have amended my code and the test results, which still look good :
http://www.inventio.co.uk/prngxor.f
and
http://www.inventio.co.uk/prngxor.txt
Thanks!
Best regards,
Howerd
On Mar 10, 11:34 am, Andrew Haley <andre...@littlepinkcloud.invalid>
wrote:
Howerd
Well, I spent 2 minutes looking at the Wikipedia article - either I
use Andrew's algorithm or devote the rest of my life to understanding
Randomness ;)
I choose the former...
BTW here is the conclusion so USE THIS ONE and not all of the others
that look so similar :
\ Marsaglia, "Xorshift RNGs". http://www.jstatsoft.org/v08/i14/paper
: NewRandom ( -- u )
MyRandom @
dup 0= or
dup 13 lshift xor
dup 17 rshift xor
dup 5 lshift xor
dup MyRandom ! ;
This seems to be a good general purpose PRNG, even though it probably
only exhibits stronger than Martin-Löf randomness occasionally ;-)
Now I have a PIC chip to program in C - sympathy please :-)
Best regards,
Howerd
Albert van der Horst
Andrew Haley <andr...@littlepinkcloud.invalid> wrote:
>Howerd <how...@yahoo.co.uk> wrote:
>>
>> I can see why you are annoyed - you corrected the typo in your code,
>> then I go and break it all... Sorry...
>>
>>> The 0 case doesn't need handling because it's not part of the cycle.
>> This means that if the value ever gets to 0 the PRNG sticks at 0.
>> It also means that the PRNG can never give a 0 ( well I suppose it
>> could give one, then die).
>> How do you know that 0 is not part of the cycle? No doubt this is
>> covered in the paper.
>
>That's right: the period of the generator is 2^32-1, and therefore
>includes all numbers from 1 to 0ffffffff inclusive.
>
>>> The INVERT is wrong.
>> Adding the invert handles the 0 case, and seems not to give bad p-
>> values in the Diehard tests.
>> In what way is that wrong?
>
>Well, it's different, and it creates a different generator. Will this
>generator get stuck in a short cycle, or even a fixed point? Off the
>top of my head, I can't tell.
I will put it more bluntly. The original random generator is
sophisticated and has a large motivation and test behind it.
Now comes a rank amateur, throws in an INVERT and says:
: "It looks like it still works!".
>
>>> Your INVERT, however, will produce a 0 where one did not appear in the
>>> original generator.
>> Yes - 0 is a valid number within the range of the PRNG.
>
>And does your generator then have a full period? If not, what period
>does it have?
>
>>>I would leave it as it is if I were you.
>> Well maybe, but I would have to understand why the sequence would
>> never hit 0, and for ever be aware that the seed value has a
>> pathological special case...
>
>So why not use the version I provided? It has all of the nice
>properties of the Marsaglia generator and works with any initial
>seed.
Indeed, If you're presented with a solid piece of work, just use
it.
>
>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
Albert van der Horst
Howerd <how...@yahoo.co.uk> wrote:
>Hi The Beez,
>
>Thanks for the comments.
>I think what I am looking for here is a simple PRNG for general
>purpose applications.
>I suspect that George Marsaglia is setting his sights much higher.
>When I ran the PRNG that I was using through Diehard it is clearly not
>very good :
>
>: NewRandom ( - u )
> MyRandom @
> 69069 * 1+
> dup MyRandom !
>;
These type of random generators can be acceptable.
Knuth (TAO) has a lot to say about them, including proposals
for the multipliers 69069 * and the addition (1+).
For tForth Marcel Hendrix came up with a reference
IDN 1991 jan 21 , page 151.
This is used to this day in tforth ciforth and probably iforth.
(107465 * 234567 )
Why reinvent the wheel?
>> Hans Bezemer
Paul Rubin
>> Randomness is an interesting subject - there does not seem to be an
>> absolute way of judging randomness, by definition...
>>
> There are means to judge. http://en.wikipedia.org/wiki/Algorithmically_random_sequence
That is a little bit bogus--the wiki article gives a mathematical
definition of algorithmic randomness, but the point is that there is no
ALGORITHM to determine whether something is algorithmically random.
That would be equivalent to solving the halting problem, i.e. it is
impossible. Slightly more technically: the Kolmogorov complexity K(x)
is not a computable function of x.
A more useful criterion for a software PRNG is that there is no
computationally feasible way to distinguish its output from a true
random sequence. That can be done in a weak way with (say) LFSR-type
generators, which have good enough statistical properties for many
purposes but can be identified by someone who knows what to look for, or
it can be done in a stronger way, designing PRNG's to thwart adversaries
who are willing to expend huge resources trying to find correlations in
the output. The design of adversary-resistant PRNG's a main topic in in
cryptography, and such PRNG's are sometimes called CPRNG's or CSPRNG's
(cryptographic PRNG or cryptographically secure PRNG) to distinguish
them from non-adversarial PRNG's.
I'm pretty sure that Forth implementations exist of standard
cryptographic primitives like the AES block cipher and the SHA family of
hash functions and the HMAC combining function. These will be slower
than an LFSR but still fast enough for most purposes not needing huge
quantities of random numbers. They are fast and convenient enough that
I'd say to use one if you are in any significant doubt about whether
some particular weaker PRNG is sufficiently random for your application.
The simplest way to use AES as a random number generator is to pick a
random secret key K, then encrypt the 128-bit numbers 0, 1, 2... This
is called CTR (short for counter) mode. A standard way to encrypt a
message is just XOR it with the CTR output, but you can also use the CTR
output directly as random numbers. If K is random and kept secret, then
there are no known attacks that distinguish this CTR output from random
with a feasible amount of work.
You can also get strong (but kind of slow) pseudorandom numbers on Linux
by reading the /dev/urandom file, or on Windows from the CryptGenRandom
function. You can use those numbers to seed AES-CTR, for example.
The Beez'
wrote:
> I just heard that George Marsaglia died in Tallahassee on February 15.
> He kept up posting about randomness and statistics until the end of
> his life. I think this is his last posting:
appreciate his work. The 4tH community has ported several of his well
documented randomizers, so I'm quite familiar with his good work. I
especially like how he always converted his work into working programs
and his close link to the Internet community.
Hans Bezemer
The Beez'
> And yes - I just noticed that the KISS code is already in Forth :-(
---8<---
\ -- super KISS generator --
\ Algorithm 2009 by George Marsaglia
\ Forth version by Marcel Hendrix, 2009
\ 4tH version by Hans Bezemer, 2009
[UNDEFINED] kiss [IF]
[UNDEFINED] um* [IF] include lib/mixed.4th [THEN]
41790 constant ixmax
ixmax array q
variable indx
variable carry
variable xcng
variable xxs
: reset ( -- u )
ixmax 0 ?do
q i th @ 7010176 um* carry @ u>d d+ carry ! invert q i th !
loop 1 indx ! q @
;
: cng xcng @ 69609 * 123 + dup xcng ! ;
: xs xxs @ dup 13 lshift xor dup 17 rshift xor dup 5 rshift xor dup
xxs ! ;
: supr indx @ ixmax < if q indx @ th @ 1 indx +! else reset then ;
: kiss ( -- u ) supr cng + xs + ;
: initialize ixmax indx ! ixmax 0 ?do cng xs + q i th ! loop ;
: seed3! ( -- ) xxs ! xcng ! carry ! initialize ;
: randomize time xcng ! cng xxs ! xs carry ! initialize ;
[DEFINED] 4th# [IF]
hide q
hide ixmax
hide indx
hide carry
hide xcng
hide xxs
hide reset
hide initialize
[THEN]
[THEN]
\ 362436 1236789 521288629 seed3!
\ 0 1000000 over ?do drop kiss loop ." x = " . cr
\ 1 x= B754D5CD x=-1219177011
\ 10 x= 8DB4048B x=-1917582197
\ 100 x= 20FEE35D x= 553575261
\ 1000 x= C5BA67A7 x= -977639513
\ 10000 x= 2229E08A x= 573169802
\ 100000 x= C2856C21 x=-1031443423
\ 1000000 x= 16DA5756 x= 383407958
\ 10000000 x= 1C3F1FB8 x= 473898936
\ 100000000 x= 7C2EF719 x= 2083452697
\ 1000000000 x= CC000AE2 x= -872412446
---8<---
Hans Bezemer
Howerd
> I will put it more bluntly. The original random generator is
> sophisticated and has a large motivation and test behind it.
> Now comes a rank amateur, throws in an INVERT and says:
> : "It looks like it still works!".
Yes, I agree, I was wrong to do this.
> Indeed, If you're presented with a solid piece of work, just use
> it.
In my defence, the original paper has a typo ( missing ^ ) and
Andrew's original post had a typo (mixing up parameters from the 64
and 32 bit versions),
so I wanted to test it.
In terms of the Diehard tests, any combination of "invert"s or the
"dup 0= or" phrase gives good results.
I was testing the 'if' in the above statement - how solid was the
code?
The flip side of the coin is that using any piece of code without
testing it is unwise.
I suspect that the original paper is mathematically correct, and that
the C code (when corrected) reflects the theory.
But I will never believe that it "works" without some kind of test.
There is then also the issue of whether the test that I choose is
valid...
So I can see both sides of the issue - the best approach seems to be
to take code that reflects well documented theory AND test it too :-)
BTW I intend to use this PRNG to replace the '69069 * 1+' code from
Knuth which 'fails' the Diehard tests...
Best regards,
Howerd
On Mar 10, 11:56 pm, Albert van der Horst <alb...@spenarnc.xs4all.nl>
wrote:
> In article <yJidnSyQz4WuKuXQnZ2dnUVZ_tCdn...@supernews.com>,
> Andrew Haley <andre...@littlepinkcloud.invalid> wrote:
Howerd
I was thinking about adding TEAN to the PRNG to make it
cryptographically secure.
Clearly the issues here are choosing a random K and keeping it secret.
I was thinking of using a random seed to the PRNG then using the next
6 32 bit values for the input and key for TEAN (2 for the input, 4 for
the key which are 64 and 128 bit respectively).
There may be a way of using the PRNG sequence to crack this more
efficiently than brute force, but I cannot see how...
I suspect that any encryption algorithm used in CTR mode would be
susceptible to differential analysis attacks - the use of the PRNG
would make this much more difficult and probably infeasible.
The result would be determined by the original seed, which is 32 bits,
but this can be scaled up as required to give as much strength as
required.
Best regards,
Howerd
On Mar 10, 11:24 pm, Paul Rubin <no.em...@nospam.invalid> wrote:
> Alex McDonald <b...@rivadpm.com> writes:
> >> Randomness is an interesting subject - there does not seem to be an
> >> absolute way of judging randomness, by definition...
>
> > There are means to judge.http://en.wikipedia.org/wiki/Algorithmically_random_sequence
Howerd
Thanks for this - I will test it with Diehard when I get time...
Best regards,
Howerd
Andrew Haley
> In my defence, the original paper has a typo ( missing ^ ) and
> Andrew's original post had a typo (mixing up parameters from the 64
> and 32 bit versions),
Eh? One of us must be going crazy. ;-)
My origial post had:
: random ( - n)
rng @
dup 0= or
dup 6 lshift xor
dup 21 rshift xor
dup 7 lshift xor
dup rng ! ;
Where's the typo? This is the 32-bit version.
Andrew.
Paul Rubin
> I was thinking about adding TEAN to the PRNG to make it
> cryptographically secure.
TEA is very easy to implement but rather slow, and its security isn't so
great. It's probably fine for numerical simulations but using it for
cryptography is questionable. There's a perfectly good standard (AES)
so I'd just use that. Also, TEA is a 64-bit block cipher so in CTR mode
there is a likely distinguisher after around 2**32 blocks, not a huge
number these days, due to birthday collisions.
RC5 is almost as easy as TEA to implement and may have better security,
but it may still have active patents, I haven't been keeping track.
I'd like to hope someone has already written AES and SHA* in Forth, so
I'd just use an existing implementation. There are certainly C and
assembler versions around for most cpu's, so maybe they could be linked
to Forth somehow as an alternative.
> I suspect that any encryption algorithm used in CTR mode would be
> susceptible to differential analysis attacks - the use of the PRNG
> would make this much more difficult and probably infeasible.
If you mean the random input, I doubt it helps much. The way to thwart
differential and other attacks is use a good cipher. The practice these
days is to use modes whose security is easy to prove, and rely on the
strength of the underlying primitive for security.
Howerd
> Where's the typo? This is the 32-bit version.
OK - suspected typo - the C code example in the paper uses different
coefficients, but I see that ( 6,21,7 ) is in the table of good values
so this is *a* 32-bit version...
> Eh? One of us must be going crazy. ;-)
There is always the possibility that both of us are going crazy ;-
Anyway, thanks for the post - this looks like a very useful
algorithm :-)
Must get back to the PIC now :-(
Best regards,
Howerd
On Mar 11, 9:28 am, Andrew Haley <andre...@littlepinkcloud.invalid>
wrote:
Albert van der Horst
>Howerd <how...@yahoo.co.uk> wrote:
>>Hi The Beez,
>>
>>Thanks for the comments.
>>I think what I am looking for here is a simple PRNG for general
>>purpose applications.
>>I suspect that George Marsaglia is setting his sights much higher.
>>When I ran the PRNG that I was using through Diehard it is clearly not
>>very good :
>>
>>: NewRandom ( - u )
>> MyRandom @
>> 69069 * 1+
>> dup MyRandom !
>>;
>
>These type of random generators can be acceptable.
>Knuth (TAO) has a lot to say about them, including proposals
>for the multipliers 69069 * and the addition (1+).
>For tForth Marcel Hendrix came up with a reference
>IDN 1991 jan 21 , page 151.
Sorry that is
EDN journal.
Andrew Haley
>> Where's the typo? This is the 32-bit version.
> OK - suspected typo - the C code example in the paper uses different
> coefficients, but I see that ( 6,21,7 ) is in the table of good values
> so this is *a* 32-bit version...
That's right: any of the triples in the paper is suitable for a
generator. No typo, I assure you.
Andrew.
Hugh Aguilar
wrote:
> Brad <hwfw...@gmail.com> wrote:
> > On Mar 9, 11:52?am, Howerd <howe...@yahoo.co.uk> wrote:
> >> : NewRandom ( -- u )
> >> MyRandom @
> >> dup 13 lshift xor invert
> >> dup 17 rshift xor
> >> dup 5 lshift xor invert
> >> dup MyRandom ! ;
>
> > It looks a lot like what hardware guys call a LFSR.
>
> It is. 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.
Your prng *ISN'T* an LFSR. Also, LFSRs were invented by mathematicians
--- not "hardware guys" --- hence there is a *definition* for what an
LFSR is, and you don't have to wonder what it "looks like."
For *any* prng (generated by any algorithm), there is an equivalent
LFSR (not just XOR-shift generators). This is found with the Berlekamp-
Massey algorithm. Converting into an LFSR is useful for cryptanalysis
because there are techniques for cracking LFSRs, or at least analyzing
them. Also, a binary LFSR can be built in hardware to be much faster
than the original algorithm written in software. I don't actually know
how the Berlekamp-Massey works, but if I can figure it out I will
include it in the next novice package upgrade. Right now, my linear-
congruential encryption-cracking software is the weakest program in
the novice package, so I would really like to improve it.
In my book slide-rule.pdf, I present a stream cipher that I invented,
called Templar Encryption, which is based on playing cards. I hope to
find an LFSR that is equivalent, as this would give me a measure of
how strong my cipher is. When all I have is a complicated algorithm
involving decks of cards, there is no way to analyze it --- I suppose
I could use a statistical test suite such as Diehard, but that
wouldn't really tell me anything about encryption strength.
Hugh Aguilar
> BTW I intend to use this PRNG to replace the '69069 * 1+' code from
> Knuth which 'fails' the Diehard tests...
That 69069 multiplier is very small for a 32-bit number --- the
purpose of using such a small multiplier is to avoid overflow (that
was Knuth's clever trick). But overflow is not a problem if you have
mixed-precision arithmetic! Forth is the *only* language that has
mixed-precision arithmetic, and we are all supposedly Forth
programmers --- so why are we trying to avoid overflow by using a tiny
multiplier???
LC53 uses a gigantic multiplier, and it is written in the Forth
language. Coincidence? I don't think so!
If you were to write LC53 in C, you would have to convert *everything*
to long ints, which would kill the speed as compared to the Forth
version. There is actually a lot of code in my novice package which
would be pretty difficult to implement in C. By comparison, I'm not
aware of any C code that would be difficult to implement in Forth, and
wouldn't even be improved in terms of readability or efficiency or
both.
Howerd
> That 69069 multiplier is very small for a 32-bit number
Its certainly too big for 16 bits.
> the
> purpose of using such a small multiplier is to avoid overflow
If you multiply 69069 by a sixteen bit number it can still overflow,
so I don't think that is why Knuth chose it.
Actually its not that hard to create */ in C :
/* returns Value * Multiplier / Divisor , using a 64 bit intermediate
value */
u32 StarSlash( u32 Value, u32 Multiplier, u32 Divisor )
{
return( ( (unsigned long long)Value * Multiplier) / Divisor );
}
I find it just as useful in C as in Forth...
Best regards,
Howerd
Stephen Pelc
wrote:
>Actually its not that hard to create */ in C :
>
>/* returns Value * Multiplier / Divisor , using a 64 bit intermediate
>value */
>u32 StarSlash( u32 Value, u32 Multiplier, u32 Divisor )
>{
> return( ( (unsigned long long)Value * Multiplier) / Divisor );
>}
It is not immediately clear to me what precision is used for the
multiply and divide. Would it not be safer and clearer to use:
u32 StarSlash( u32 Value, u32 Multiplier, u32 Divisor )
{
u64 temp1, temp2;
temp1 = (u64)Value * (u64)Multiplier;
temp2 = temp1 / (u64)Divisor;
return( (u32) (temp / Divisor) );
}
It may be bad C style to "overcast", but it avoids a lot of problems,
and helps people like me who don't know the C corner cases.
-Wall is your friend. Paranoia is useful.
Stephen
--
Stephen Pelc, steph...@mpeforth.com
MicroProcessor Engineering Ltd - More Real, Less Time
133 Hill Lane, Southampton SO15 5AF, England
tel: +44 (0)23 8063 1441, fax: +44 (0)23 8033 9691
web: http://www.mpeforth.com - free VFX Forth downloads
Andrew Haley
> Hi Hugh,
>
>> That 69069 multiplier is very small for a 32-bit number
> Its certainly too big for 16 bits.
>
>> the purpose of using such a small multiplier is to avoid overflow
>
> If you multiply 69069 by a sixteen bit number it can still overflow,
> so I don't think that is why Knuth chose it.
I'm sure it isn't. The multiplier 69069 is George Marsaglia's choice
for a 32-bit linear congruential generator; it gives good results on
the spectral test and it's easy to remember. He used c=1234567, but I
doubt that this will affect the result by very much. This generator
is about as good as it gets for a LCG mod 2^32, AFAIK.
Here's his famous collection of RNGs:
http://www.math.niu.edu/~rusin/known-math/99/RNG
Andrew.