"{ Package: 'stx:libbasic2' }"
Object subclass:#RandomTT800
instanceVariableNames:'k x mag01'
classVariableNames:'M N'
poolDictionaries:''
category:'Magnitude-Numbers'
!
RandomTT800 comment:'A pseudo-random number generator; see below for references.
This generator is much slower than Squeak''s Random class.
It automatically seeds itself based on the millisecond clock.
Using the generator:
randy := RandomTT800 new.
randy seed: anInteger. "optional; never use zero"
aRandom := randy next.
Example (InspectIt):
| r |
r := RandomTT800 new.
(1 to: 50) collect: [ :n | r next ].
===================================================================
Originally a C-program for TT800 : July 8th 1996 Version
by M. Matsumoto, email: matumoto@math.keio.ac.jp
Generates one pseudorandom number with double precision which is uniformly distributed on [0,1]-interval for each call. One may choose any initial 25 seeds except all zeros.
See: ACM Transactions on Modelling and Computer Simulation,
Vol. 4, No. 3, 1994, pages 254-266.
ABSTRACT
The twisted GFSR generators proposed in a previous article have a defect in k-distribution for k larger than the order of recurrence. In this follow up article, we introduce and analyze a new TGFSR variant having better k-distribution property. We provide an efficient algorithm to obtain the order of equidistribution, together with a tight upper bound on the order. We discuss a method to search for generators attaining this bound, and we list some of these such generators. The upper bound turns out to be (sometimes far) less than the maximum order of equidistribution for a generator of that period length, but far more than that for a GFSR with a working are of the same size.
Previous paper:
ACM Transactions on Modeling and Computer Simulation
Volume 2 , Issue 3 (1992) Pages 179-194
Twisted GFSR generators
Makoto Matsumoto, and Yoshiharu Kurita
ABSTRACT
The generalized feed back shift register (GFSR) algorithm suggested by Lewis and Payne is a widely used pseudorandom number generator, but has the following serious drawbacks: (1) an initialization scheme to assure higher order equidistribution is involved and is time consuming; (2) each bit of the
generated words constitutes an m-sequence based on a primitive trinomials, which shows poor randomness with respect to weight distribution; (3) a large working area is necessary; (4) the period of sequence is far shorter than the theoretical upper bound. This paper presents the twisted GFSR (TGFSR) algorithm, a slightly but essentially modified version of the GFSR, which solves all the above problems without loss of merit. Some practical TGFSR generators were implemented and passed strict empirical tests. These new generators are most suitable for simulation of a large distributive system, which requires a number of mutually independent pseudorandom number generators with compact size.
'
!
!RandomTT800 class methodsFor:'documentation'!
LICENSE
"
PLEASE READ THE FOLLOWING NOTICE AND DISCLAIMER CAREFULLY
BEFORE DOWNLOADING THIS SOFTWARE. BY DOWNLOADING THIS SOFTWARE
YOU ARE AGREEING TO BE BOUND BY THESE TERMS. IF YOU DO NOT AGREE
TO THE TERMS, DO NOT DOWNLOAD.
This software (Software), provided by IBM Corporation, may
contain, or be derived from, code provided by Apple Computer,
Inc., and is provided subject to the provisions of the Apple
Computer, Inc. Software License for the SQUEAK Smalltalk System
which can be viewed at http://www.squeak.org/license.html.
This Software is provided AS IS, and IBM Corporation
DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING, WITHOUT
LIMITATION, ANY WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
PARTICULAR PURPOSE, AND NONINFRINGEMENT OF THIRD PARTY RIGHTS.
IBM DOES NOT WARRANT THAT THE FUNCTIONS CONTAINED IN THE SOFTWARE
WILL MEET THE USERS' REQUIREMENTS, THAT THE OPERATION OF THE
SOFTWARE WILL BE UNINTERRUPTED OR ERROR-FREE, OR THAT DEFECTS
IN THE SOFTWARE WILL BE CORRECTED. UNDER NO CIRCUMSTANCES SHALL
IBM CORPORATION BE LIABLE FOR INCIDENTAL, INDIRECT OR CONSEQUENTIAL
DAMAGES ARISING FROM OR RELATING TO USE OF THIS SOFTWARE. The
user of this Software agrees to indemnify and hold IBM Corporation
harmless from any and all damages, liabilities, costs and expenses
(including attorney's fees) incurred by IBM Corporation as a
result of any claim, proceeding or judgment to the extent it
arises out of or is connected in any manner with the operation,
use, distribution or modification of the Software, or the combination
of the Software or modified Software with other programs.
"
!
TT800OriginalCVersion
" From: http://random.mat.sbg.ac.at/ftp/pub/data/tt800.c
/* A C-program for TT800 : July 8th 1996 Version */
/* by M. Matsumoto, email: matumoto@math.keio.ac.jp */
/* genrand() generate one pseudorandom number with double precision */
/* which is uniformly distributed on [0,1]-interval */
/* for each call. One may choose any initial 25 seeds */
/* except all zeros. */
/* See: ACM Transactions on Modelling and Computer Simulation, */
/* Vol. 4, No. 3, 1994, pages 254-266. */
/* ABSTRACT
The twisted GFSR generators proposed in a previous article have a defect in k-distribution for k larger than the order of recurrence. In this follow up article, we introduce and analyze a new TGFSR variant having better k-distribution property. We provide an efficient algorithm to obtain the order of equidistribution, together with a tight upper bound on the order. We discuss a method to search for generators attaining this bound, and we list some of these such generators. The upper bound turns out to be (sometimes far) less than the maximum order of equidistribution for a generator of that period length, but far more than that for a GFSR with a working are of the same size.
*/
#include <stdio.h>
#define N 25
#define M 7
double
genrand()
{
unsigned long y;
static int k = 0;
static unsigned long x[N]={ /* initial 25 seeds, change as you wish */
0x95f24dab, 0x0b685215, 0xe76ccae7, 0xaf3ec239, 0x715fad23,
0x24a590ad, 0x69e4b5ef, 0xbf456141, 0x96bc1b7b, 0xa7bdf825,
0xc1de75b7, 0x8858a9c9, 0x2da87693, 0xb657f9dd, 0xffdc8a9f,
0x8121da71, 0x8b823ecb, 0x885d05f5, 0x4e20cd47, 0x5a9ad5d9,
0x512c0c03, 0xea857ccd, 0x4cc1d30f, 0x8891a8a1, 0xa6b7aadb
};
static unsigned long mag01[2]={
0x0, 0x8ebfd028 /* this is magic vector `a', don't change */
};
if (k==N) { /* generate N words at one time */
int kk;
for (kk=0;kk<N-M;kk++) {
x[kk] = x[kk+M] ^ (x[kk] >> 1) ^ mag01[x[kk] % 2];
}
for (; kk<N;kk++) {
x[kk] = x[kk+(M-N)] ^ (x[kk] >> 1) ^ mag01[x[kk] % 2];
}
k=0;
}
y = x[k];
y ^= (y << 7) & 0x2b5b2500; /* s and b, magic vectors */
y ^= (y << 15) & 0xdb8b0000; /* t and c, magic vectors */
y &= 0xffffffff; /* you may delete this line if word size = 32 */
/*
the following line was added by Makoto Matsumoto in the 1996 version
to improve lower bit's corellation.
Delete this line to o use the code published in 1994.
*/
y ^= (y >> 16); /* added to the 1994 version */
k++;
return( (double) y / (unsigned long) 0xffffffff);
}
"
!
documentation
"
Warning: this generator should not be used for cryptographic work.
NO WARRANTY
Slightly adapted Squeak code for fileIn into ST/X.
The original comment was:
A pseudo-random number generator; see below for references.
This generator is much slower than Squeak's Random class.
It automatically seeds itself based on the millisecond clock.
Using the generator:
randy := RandomTT800 new.
randy seed: anInteger. 'optional; never use zero'
aRandom := randy next.
Example (InspectIt):
| r |
r := RandomTT800 new.
(1 to: 50) collect: [ :n | r next ].
===================================================================
Originally a C-program for TT800 : July 8th 1996 Version
by M. Matsumoto, email: matumoto@math.keio.ac.jp
Generates one pseudorandom number with double precision which is uniformly distributed
on [0,1]-interval for each call. One may choose any initial 25 seeds except all zeros.
See: ACM Transactions on Modelling and Computer Simulation,
Vol. 4, No. 3, 1994, pages 254-266.
ABSTRACT
The twisted GFSR generators proposed in a previous article have a defect in k-distribution for k larger
than the order of recurrence.
In this follow up article, we introduce and analyze a new TGFSR variant having better k-distribution property.
We provide an efficient algorithm to obtain the order of equidistribution, together with a tight upper bound
on the order.
We discuss a method to search for generators attaining this bound, and we list some of these such generators.
The upper bound turns out to be (sometimes far) less than the maximum order of equidistribution for a generator
of that period length, but far more than that for a GFSR with a working are of the same size.
Previous paper:
ACM Transactions on Modeling and Computer Simulation
Volume 2 , Issue 3 (1992) Pages 179-194
Twisted GFSR generators
Makoto Matsumoto, and Yoshiharu Kurita
ABSTRACT
The generalized feed back shift register (GFSR) algorithm suggested by Lewis and Payne is a widely used pseudorandom number generator, but has the following serious drawbacks: (1) an initialization scheme to assure higher order equidistribution is involved and is time consuming; (2) each bit of the
generated words constitutes an m-sequence based on a primitive trinomials, which shows poor randomness with respect to weight distribution; (3) a large working area is necessary; (4) the period of sequence is far shorter than the theoretical upper bound. This paper presents the twisted GFSR (TGFSR) algorithm, a slightly but essentially modified version of the GFSR, which solves all the above problems without loss of merit. Some practical TGFSR generators were implemented and passed strict empirical tests. These new generators are most suitable for simulation of a large distributive system, which requires a number of mutually independent pseudorandom number generators with compact size.
[see also:]
http://www0.cs.ucl.ac.uk/staff/d.jones/GoodPracticeRNG.pdf
RandomGenerator - the default; uses the machine's /dev/random if available
Random - fast, but generates less quality random numbers
RandomParkMiller - a good one (according to literature)
RandomMT19973 - a better one (according to literature)
RandomKISS - a fast, reasonably good one (according to literature)
"
!
examples
"
[exBegin]
| r |
r := RandomTT800 new.
(1 to: 50) collect: [ :n | r next ].
[exEnd]
"
! !
!RandomTT800 class methodsFor:'initialization'!
initialSeeds
" initial 25 seeds, change as you wish. (there must be N seeds) "
^ self originalSeeds
!
originalSeeds
" original initial 25 seeds. DO NOT CHANGE "
^ #( 16r95F24DAB 16r0B685215 16rE76CCAE7 16rAF3EC239 16r715FAD23
16r24A590AD 16r69E4B5EF 16rBF456141 16r96BC1B7B 16rA7BDF825
16rC1DE75B7 16r8858A9C9 16r2DA87693 16rB657F9DD 16rFFDC8A9F
16r8121DA71 16r8B823ECB 16r885D05F5 16r4E20CD47 16r5A9AD5D9
16r512C0C03 16rEA857CCD 16r4CC1D30F 16r8891A8A1 16rA6B7AADB ) copy
! !
!RandomTT800 class methodsFor:'instantiation'!
new
^ super new
initialize
! !
!RandomTT800 class methodsFor:'testing'!
bucketTest1
" Answers an array with 50 elements each of which should hold an integer near the value 1000,
the closer the better. "
" RandomTT800 bucketTest1 inspect "
| a r s k |
s := 50.
a := Array new: s.
a atAllPut: 0.
r := RandomTT800 new.
1 to: 50000 do: [ :n |
k := (r next * s) truncated + 1.
a at: k put: (a at: k) + 1 ].
^ a
!
firstInteger: s
" Answers an array with the first 's' raw integer elements generated by the RNG using the original seeds.
Intended for testing only. "
" RandomTT800 firstInteger: 50 "
| a r |
a := Array new: s.
a atAllPut: 0.
r := RandomTT800 new.
" set the original initial 25 seeds. "
r setSeeds: self originalSeeds.
1 to: s do: [ :n |
a at: n put: r nextInteger ].
^ a
!
theItsCompletelyBrokenTest
" Test to see if generator is answering what it should.
Assumes that the initial seeds are what is given in the original version.
If this fails something is badly wrong; do not use this generator."
" RandomTT800 theItsCompletelyBrokenTest "
| okResult |
okResult := #(
16rBCF1F45A 16rA26BF07E 16r14AEFF49 16r6777A14E 16r880C242F
16rECEF7842 16r3BD9352 16r1DD55C94 16r7BC39C7 16r75E78DC2
16rF0CF8478 16rE2886F41 16rB63AC1A9 16r57858A58 16r16169989
16rD8602211 16r31818D3 16r30D51520 16r1C61F026 16rB58FA81
16r51AF5CAC 16r609D3850 16r278BF184 16r50C1F860 16rEE6F61B4
16r33C2A07E 16r55EE93B7 16r40BD28C3 16r713DB4BE 16rDD9352E3
16r9254D8B9 16r9C02EE00 16r5F1BB40C 16rF741D0A5 16r6EE25C13
16r375DD95B 16rFB24339 16rF3E2C95A 16r8CAA8C6F 16r63858F2F
16r70369B29 16r617E2292 16r357EC977 16rC0B7E080 16r16474ADA
16rAFDF1588 16rA1502F9D 16rC4577788 16rE3A9893C 16r71662621 ).
(self firstInteger: 50) = okResult ifFalse: [
PopUpMenu notify: 'First 50 results do not match the expected results.' ].
(self firstInteger: 1001) last = 16rD7B4E10B ifFalse: [
PopUpMenu notify: 'Element 1001 does not match the expected result.' ].
PopUpMenu notify: 'The expected results were obtained.'
! !
!RandomTT800 methodsFor:'initialization'!
initialize
N := 25.
M := 7.
k := 0.
"x := self class initialSeeds. (Done in #seed:) "
self seed: (Random randomSeed bitAnd:16rFFFFFFFF).
" this is magic vector `a', don't change "
mag01 := #( 16r0 16r8EBFD028 ).
!
seed: anInteger
x := self class initialSeeds.
1 to: x size do: [ :n |
x at: n put: ((x at: n) bitXor: anInteger) ].
k := 0.
!
setSeeds: anArray
" Used only by class methods for testing. "
anArray size = x size ifTrue: [
x := anArray ]
! !
!RandomTT800 methodsFor:'random numbers'!
next
" Answer the next random number as a float in the range [0.0,1.0) "
^ self nextInteger asFloat / 4.29496729500000e9 "16rFFFFFFFF asFloat"
" Note that: 4.29496729500000e9 asTrueFraction hex
is: '16rFFFFFFFF' "
!
nextBoolean
" Answer the next boolean"
^ self nextInteger > 16r7FFFFFFF
!
nextInteger
" Answer the next random number in its raw integer form "
| y kk jLast |
" generate N words at one time "
k = N ifTrue: [
"for (kk=0;kk<N-M;kk++) {"
0 to: N-M-1 by: 1 do: [ :j |
jLast := j.
kk := j+1.
"x[kk] = x[kk+M] ^ (x[kk] >> 1) ^ mag01[x[kk] % 2];"
x at: kk put:
( ((x at: kk+M) bitXor: (x at: kk) >> 1)
bitXor: (mag01 at: (x at: kk) \\ 2 + 1) )
].
"for (; kk<N;kk++) { "
jLast+1 to: N-1 by: 1 do: [ :j |
kk := j+1.
"x[kk] = x[kk+(M-N)] ^ (x[kk] >> 1) ^ mag01[x[kk] % 2];"
x at: kk put:
( ((x at: kk+M-N) bitXor: (x at: kk) >> 1)
bitXor: (mag01 at: (x at: kk) \\ 2 + 1) )
].
k := 0.
].
y := x at: k+1.
"y ^= (y << 7) & 0x2b5b2500; /* s and b, magic vectors */"
y := y bitXor: ((y << 7) bitAnd: 16r2B5B2500). " s and b, magic vectors "
y := y bitAnd: 16rFFFFFFFF.
"y ^= (y << 15) & 0xdb8b0000; /* t and c, magic vectors */"
y := y bitXor: ((y << 15) bitAnd: 16rDB8B0000). " t and c, magic vectors "
y := y bitAnd: 16rFFFFFFFF. " you may delete this line if word size = 32 "
"The following line was added by Makoto Matsumoto in the 1996 version
to improve lower bit's corellation.
Delete this line to o use the code published in 1994. "
y := y bitXor: y >> 16. "added to the 1994 version"
k := k + 1.
^ y
! !
!RandomTT800 class methodsFor:'documentation'!
version
^ '$Header: /cvs/stx/stx/libbasic2/RandomTT800.st,v 1.10 2014-10-02 16:22:58 cg Exp $'
!
version_CVS
^ '$Header: /cvs/stx/stx/libbasic2/RandomTT800.st,v 1.10 2014-10-02 16:22:58 cg Exp $'
! !