Hi zusammen...
Cybernd wrote:
[Soweit ACK]
Post by CyberndIn den ersten PCs steckte ein Zufallsalgo. Dieser funktionierte
wunderbar über Monate (Jahre?) hinweg.
Sorry, das stimmt so nicht. Es wurden immer lineare Kongruenzmethoden
verwendet, was schon schlimm war...diese waren aber
teilweise noch extrem schlecht aufgesetzt, so dass Knuth selbst
scharfe Kritik an den damals vorkommenden PRNG (Zufallsgenerator)
geübt hat.
Dieses "wunderbar" funktionieren stimmt schon deshalb nicht,
weil sich selbst im Optimalfalle nach 16 Millionen Iterationen
die Zahlen wiederholten. Das war schon seit dem 80386 keine
Monate, geschweige denn Jahre mehr.
Post by CyberndAlles paletti bis da jemand auf die Idee kam derartige
Zufallszahlen für 3D-Simmulationen zu verwenden.
1. Dimension, 2. Dimension, 3. Dimension, 1. Dimension ...
123,123,123,123,123,123
Und sieheda diese Zufallszahlen in einem 3D-Diagramm aufgezeichnet lagen
exakt in einer Ebene, also alles andere als Zufällig.
Marsaglia Effekt: Hier schön zu beobachten (von oben draufschauen).
http://www.physics.carleton.ca/courses/75.502/slides/java/RandomApplet/
RandomApplet.html
Post by CyberndDerartige auf leichte Beweise zur Widerlegung der Zufälligkeit sind mit
den momentan gängigen Random Algos nicht möglich. Wenn du etwas präziser
zufälliges haben willst mußt du entsprechend aufgebohrte Libs verwenden.
Die brauchen dann aber erhebliche Rechenlast pro Zufallszahl.
Nope. Ich stelle mal den Mersenne Twister hier zur Verfügung; dieser
verwendet nur Bitoperationen und ist deshalb extrem schnell; die
Länge der Iteration bis zur Wiederholung ist 2^19937 und weist
bis zur 623. Dimension Gleichverteilung auf.
public class MersenneTwister {
private int mti;
private int[] mt = new int[N]; // set initial seeds: N = 624 words
private byte[] seed=null; // initial seed
private boolean sucInit=false; // report if SecRandom was successful
private long iNumber=0; // number of current iteration
/* Period parameters */
private static final int N=624;
private static final int M=397;
private static final int MATRIX_A=0x9908b0df; // constant vector a
private static final int UPPER_MASK=0x80000000; // most significant
w-r bits */
private static final int LOWER_MASK=0x7fffffff; /* least significant r
bits */
/* for tempering */
private static final int TEMPERING_MASK_B=0x9d2c5680;
private static final int TEMPERING_MASK_C=0xefc60000;
private static final int mag0 = 0x0;
private static final int mag1 = MATRIX_A;
//private static final int[] mag01=new int[] {0x0, MATRIX_A};
/* mag01[x] = x * MATRIX_A for x=0,1 */
public static final int DEFAULT_SEED = 4357;
/**
* Constructs and returns a random number generator with a default seed,
which is a <b>constant</b>.
* Thus using this constructor will yield generators that always produce
exactly the same sequence.
* This method is mainly intended to ease testing and debugging.
*/
public MersenneTwister()
{
try
{
seed=new byte[4*N];
SecureRandom random=SecureRandom.getInstance("SHA1PRNG");
seed=random.generateSeed(4*N);
sucInit=fillTwister(seed);
if (!sucInit)
setSeed(DEFAULT_SEED);
}//try
catch (NoSuchAlgorithmException e)
{}
}
/**
* Constructs and returns a random number generator with a chosen
arbitrary seed,
* which is a <b>constant</b>.
* Thus using this constructor will yield generators that always produce
exactly
* the same sequence for a known seed, but with extreme variability.
* This method is mainly intended to perform strong statistical tests
@param newseed long seed stored in a byte array; the length of the
byte array must be 2496
*/
public MersenneTwister(byte[] newseed) throws IllegalArgumentException
{
if (newseed.length != (N*4))
throw new IllegalArgumentException("Wrong seed dimension:
"+Integer.toString(newseed.length));
sucInit=fillTwister(newseed);
if (!sucInit)
setSeed(DEFAULT_SEED);
}
/**
* Constructs and returns a random number generator with the given seed.
*/
public MersenneTwister(int seed) {
setSeed(seed);
}
/**
* Constructs and returns a random number generator seeded with the
given date.
*
* @param d typically <tt>new java.util.Date()</tt>
*/
public MersenneTwister(Date d) {
this((int) (d.getTime() & 0x00000000FFFFFFFF));
}
/**
* Returns a copy of the receiver; the copy will produce identical
sequences.
* After this call has returned, the copy and the receiver have equal
but separate state.
*
* @return a copy of the receiver.
*/
public Object clone() throws CloneNotSupportedException
{
MersenneTwister clone = (MersenneTwister) super.clone();
clone.mt = (int[]) this.mt.clone();
return clone;
}
public static void main(String[] args)
{
final int randtry=1000;
long walk=0;
int shortwalk=0;
int cum=0;
double border=0.0;
int number=0;
MersenneTwister twister = new MersenneTwister();
byte[] test=twister.getSeed();
for (int anz=0; anz < 1000; anz++)
{
walk=0;
cum=0;
for (int i=0; i<randtry; i++)
{
/*
shortwalk=0;
for (int j=0; j<200; j++)
{
if (twister.nextInt() < 0)
shortwalk++;
}//for
border=Math.sqrt(50*(i+1));
walk+=shortwalk-100;
*/
border=Math.sqrt((i+1)*0.25);
if (twister.nextInt() < 0)
walk++;
else
walk--;
if (((double)Math.abs(walk)) > border)
cum++;
}//for
double Percent=(new Integer(cum)).doubleValue()/randtry;
//System.out.println(walk+" "+Percent);
if (Percent > 0.317)
number++;
}//for
System.out.println((new Integer(number)).doubleValue()/1000);
}//main
/**
* Fill Mersenne Twister with arbitrary seed
*/
private boolean fillTwister(byte[] newseed)
{
if (newseed.length == (4*N))
{
for (int i=0; i<N; i++)
{
mt[i]=((int) seed[4*i] << 24) |
((int) seed[4*i+1] << 16) |
((int) seed[4*i+2] << 8)|
(int) seed[4*i+3];
}//for
return true;
}//if
else
return false;
}
/**
* Generates N words at one time.
*/
protected void nextBlock() {
/*
// ******************** OPTIMIZED **********************
// only 5-10% faster ?
int y;
int kk;
int[] cache = mt; // cached for speed
int kkM;
int limit = N-M;
for (kk=0,kkM=kk+M; kk<limit; kk++,kkM++) {
y = (cache[kk]&UPPER_MASK)|(cache[kk+1]&LOWER_MASK);
cache[kk] = cache[kkM] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
}
limit = N-1;
for (kkM=kk+(M-N); kk<limit; kk++,kkM++) {
y = (cache[kk]&UPPER_MASK)|(cache[kk+1]&LOWER_MASK);
cache[kk] = cache[kkM] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
}
y = (cache[N-1]&UPPER_MASK)|(cache[0]&LOWER_MASK);
cache[N-1] = cache[M-1] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
this.mt = cache;
this.mti = 0;
*/
// ******************** UNOPTIMIZED **********************
int y;
int kk;
for (kk=0;kk<N-M;kk++) {
y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
mt[kk] = mt[kk+M] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
}
for (;kk<N-1;kk++) {
y = (mt[kk]&UPPER_MASK)|(mt[kk+1]&LOWER_MASK);
mt[kk] = mt[kk+(M-N)] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
}
y = (mt[N-1]&UPPER_MASK)|(mt[0]&LOWER_MASK);
mt[N-1] = mt[M-1] ^ (y >>> 1) ^ ((y & 0x1) == 0 ? mag0 : mag1);
mti = 0;
}
/**
* Returns a 32 bit uniformly distributed random number in the closed
interval <tt>[Integer.MIN_VALUE,Integer.MAX_VALUE]</tt> (including
<tt>Integer.MIN_VALUE</tt> and <tt>Integer.MAX_VALUE</tt>).
*/
public int nextInt() {
/* Each single bit including the sign bit will be random */
if (mti == N) nextBlock(); // generate N ints at one time
int y = mt[mti++];
y ^= y >>> 11; // y ^= TEMPERING_SHIFT_U(y );
y ^= (y << 7) & TEMPERING_MASK_B; // y ^= TEMPERING_SHIFT_S(y) &
TEMPERING_MASK_B;
y ^= (y << 15) & TEMPERING_MASK_C; // y ^= TEMPERING_SHIFT_T(y) &
TEMPERING_MASK_C;
// y &= 0xffffffff; //you may delete this line if word size = 32
y ^= y >>> 18; // y ^= TEMPERING_SHIFT_L(y);
iNumber++;
return y;
}
/**
* Sets the receiver's seed.
* This method resets the receiver's entire internal state.
*/
protected void setSeed(int seed) {
mt[0] = seed & 0xffffffff;
for (int i = 1; i < N; i++) {
mt[i] = (1812433253 * (mt[i-1] ^ (mt[i-1] >> 30)) + i);
/* See Knuth TAOCP Vol2. 3rd Ed. P.106 for multiplier. */
/* In the previous versions, MSBs of the seed affect */
/* only MSBs of the array mt[]. */
/* 2002/01/09 modified by Makoto Matsumoto */
mt[i] &= 0xffffffff;
/* for >32 bit machines */
this.seed[4*i] =(byte) ((mt[i] >> 24) & 255);
this.seed[4*(i+1)] =(byte) ((mt[i] >> 16) & 255);
this.seed[4*(i+2)] =(byte) ((mt[i] >> 8) & 255);
this.seed[4*(i+3)] =(byte) (mt[i] & 255);
}
iNumber=0;
//System.out.println("init done");
mti = N;
/*
old version was:
for (int i = 0; i < N; i++) {
mt[i] = seed & 0xffff0000;
seed = 69069 * seed + 1;
mt[i] |= (seed & 0xffff0000) >>> 16;
seed = 69069 * seed + 1;
}
//System.out.println("init done");
mti = N;
*/
}
/**
* Get the seed
*/
public byte[] getSeed()
{ return seed; }
}
Grüße
Thorsten
--
Bitte Reply-To: unverändert verwenden; die Adresse ist gültig.