Zitat von
jojansen
Mich interessiert nun, wie diese Zahlen zustande kommen, und wie ich diesen Effekt austricksen kann.
Bleibt es mir womöglich nicht erspart, ein Rauschen als Zufallsquelle zu benutzen?
Rauschen ist natütlich die beste Zufallsquelle, aber da brauchs leider extra Hardware. Und Pseudozufall hat auch seine Vorteile, etwa beim Debugging, weil Prog immer die gleichen Entscheidungen trifft.
Wie dein RND arbeitet kann ich nicht sagen, dazu müsste man in die Doku schauen -- falls überhaupt dokumentiert -- oder in die Quelle, falls vorhanden.
Für rnd nehme ich gerne die Arithmetik über dem endlichen Körper F_{2^n} mit 2^n Elementen. Was das ist, erklär ich jetzt mal nicht, entscheidend ist, daß das guten Pseudozufall liefert und nur eine ganz simple Arithmetik braucht, die sogar in Assembler schnell hingeschrieben ist.
Was man dazu braucht, ist erst mal ein Polynom, daß diesen Körper erzeugt, also ein Polynom p vom Grad n, das über F_2 irreduzibel. Damit hat man
F_{2^n} ~ F_2[x] / p*F_2[x]
Wie das Polynom p weiter aussieht ist egal. Wichtig ist nur, daß es irreduzibel ist und Grad n hat. Für n=15 geht etwa
p(x) = 1 + x^2 + x^5 + x^8 + x^13 + x^14 + x^15
Koeffizienten von p sind immer 0 oder 1, so daß p besonders gut binär dargestellt werden kann. Gleiches gilt für alle Elemente von F_{2^n}, da genügen n Bits zur Darstellung und n+1 für p.
In F_{2^n} lässt sich Arithmetik betreiben. Was man für nen Pseude-Rand braucht ist Multiplikation zweier Elemente a und b und Potenzieren mit einer natürlichen Zahl m. Für ein geeignetes a ist dann die Folge
a, a^2, a^3, a^4, ... eine Pseudozufallsfolge, deren Periode 2^n - 1 ist und die an allen Bits ne gute Zuvallsverteilung aufweist. Für unser n=15 widerholt sich die Folge also alle 32767 Glieder.
Ich poste hier mal nen C Code, wenn weitere Fragen sind und überhaupt Interesse an dem Thema ist, kann ich gerne noch was dazu sagen. Ich welcher Sprache das formuliert wird ist ja erst mal egal. Es geht zunächst mal darum zu zeigen, wie einfach das in Quelle aussieht und wie wenig Aufwand es ist.
Code:
#include <stdio.h>
#define POLY 0xe125 /* 1 + x^2 + x^5 + x^8 + x^13 + x^14 + x^15 */
#define DEGREE 15
#define ROOT 0x2200 /* x^9 + x^13 */
typedef unsigned short poly;
poly prod (poly, poly);
poly ppow (poly, poly);
void out (char*, poly);
#define MASK(b) \
(((poly) 1) << (b))
/**
* Berechnet a*b mod p
*/
poly pprod (poly a, poly b)
{
const poly mask = MASK (DEGREE);
poly c = 0;
while (b)
{
// Ist bit i in b gesetzt?
if (b & 1)
c ^= a; // dann c = c + a * x^i
a <<= 1; // a = a*x
if (a & mask) // a = a mod p
a ^= POLY;
b >>= 1;
}
return c;
}
/**
* Berechnet a^n mod p
*/
poly ppow (poly a, poly n)
{
poly c = 1;
poly a2; // a^(2^i)
// a2 = pmod (p, a);
a2 = a;
if (a2 == 0)
return 0;
while (n)
{
// Falls bit i von n gesetzt ist,
// multipliziere c mit a^(2^i)
if (n & 1)
c = pprod (c, a2);
n >>= 1;
a2 = pprod (a2, a2);
}
return c;
}
void out (char *str, poly p)
{
int i;
if (str)
printf ("%s", str);
if (p == 0)
{
printf ("0\n");
return;
}
for (i=0; p; i++)
{
if (p & 1)
{
if (i==0) printf ("1");
else printf ("x");
if (i > 1) printf ("^%0d", i);
if (p > 1) printf (" + ");
}
p >>= 1;
}
printf ("\n");
}
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
//////////////////////////////////////////////////////////////////////////
int main()
{
poly a = ROOT;
int i, j=0;
for (i=1; i<300; i++)
{
printf ("% 4d: ", i);
out ("", a);
a = pprod (a, ROOT);
}
}
Johannes
Berechtigungen
Zitieren
Lesezeichen