Fragen zu RND()

[jojansen]

Moin,
ich spiele hier etwas mit der RND Funktion herum und habe es auch 'gefressen', daß, wenn ich nichts mit Rseed mache, die Abfolge der 'zufälligen' Zahlen immer gleich ist.
Ich habe nun eine kleine Spielerei, bei der ich mir drei mal eine Zahl geben lasse, die ich für die Ansteuerung für eine rote grüne und blaue LED verwende. Die Farbkanäle bekommen dabei nicht zur (fast) selben Zeit ihre Zufallszahl, sondern mit unterschiedlichen zeitlichen Abständen. Unbefriedigend und schon etwas auffällig finde ich dabei, daß, trotz zeitlicher Abstände, die Zahlenkorridore nahe beieinander liegen.
So weit so gut. 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?

:-) Johannes

[sep]

nein, du kannst auch einen eigenen Pseudo-Zufalls-Algorithmus ausgraben.
Leider kenne ich mich da nicht gut aus, aber es wird sich schon noch eine kundige Webseite finden.

Vielleicht tust du die eingebaute Zufalls-Funktion einfach etwas aufbohren.

Bist du sicher, dass die Zufallszahlen "schlecht" sind? Ich will dich ja nicht beschuldigen Murks programmiert zu haben... Aber vielelicht ist es halt auch einfach "Zufall" gewesen...

[SprinterSB]

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.


#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);
}

}

[jojansen]

Hilf Himmel, Mathe. Trotzdem Danke. Ich werde mal schauen, ob ich mich da etwas einfuchsen kann. Mathe war nie meine Stärke. Ich werde mich mal in einer ruhigen Stunde mit meinem Firmeninformatiker zusammensetzen und mir das erklären lassen. Es scheint doch (zumindest für mich) interessant zu sein.
:-) johannes

[SprinterSB]

Jo, intesessant ist es allemal. Ausserdem ist man damit ganz dich bei Kryptographie, da wird so was auch gerne verwendet. Also Obacht, wenn du in Frankreich arbeitest. Da werden krypotgraphische Algorithmen genauso behandelt wie Waffenbesitz.

Die Multiplikation ist super simpel und funktioniert nach dam selben Prinzip, wie Grundschüler lernen 2 ganze Zahlen mit Papier und Bleistift zu multiplizieren.

Zum Ergebnis addiert man immer die Zahl a um m Stellen nach links geschoben und mit b_m multipliziert, wenn b_m die m-te Stelle von b ist.

Beide Zahlen hat man binär vorliegen, kennt also ihre Bits. Jedes Mal, wenn Bit m von b gesetzt ist, addiert man zum Ergebnis a * 2^m hinzu. That's it!

Oben in pprod() wird b mit >>=1 immer um 1 nach rechts geschoben. Daher hat man im k. Schritt an Bit 0 das (k-1)-te Bit von b. Alternativ könnte man eine Maske nach links shiften. a wird immer nach links geschoben, was einer Multiplikation mit der formalen Variablen x entspricht. Die Addition zweier Werte ist in unserem Falle aber nicht +, sondern exklusiv-oder (^ in C-Notation). Wenn man statt dem xor ein + nimmt, hat man die Multiplikation ganzer Zahlen! Bis auf einen Unterschied: in unserem Fall wird a noch mod p reduziert. Dadurch bleibt immer grad(a) < grad(p). Erst durch diese Reduktion mod p kommt es zu dem durcheinanderwürfeln der Werte. Zugleich hat man algebraisch voll den Überblick, was abgeht.

Ähnlich gute Zufallszahlen erhält man, wenn man über Z mod p*Z arbeitet. Dabei meint Z die ganzen Zahlen und p eine Primzahl (prim entspricht der Eigenschaft irreduzibel von oben).

Hast du eine ganze Zufallszahl r und ein a, dann berechnest du die nächste Zufallszahl einfach durch
r := r*a mod p
Dabei ist a eine feste Zahl, die man so wählt, daß ggT(a,p) = 1 ist und
a^((p-1)/q) ungleich 1 modulo p für alle Primteiler q von p-1.
Modulo ist der Rest, der bei Divison bleibt, zB
103 mod 10 = 3
100 mod 4 = 0
n mod (n-1) = 1
n mod (n+1) = n = -1
(n*m) mod n = 0 = (n*m) mod m