Implementierung von rand()

Ich schreibe eingebetteten Code in C und muss die Funktion rand() verwenden. Leider wird rand() in der Bibliothek für den Controller nicht unterstützt. Ich brauche eine einfache Implementierung, die schnell ist, aber vor allem wenig Speicherplatz benötigt und relativ hochwertige Zufallszahlen erzeugt. Kennt jemand den zu verwendenden Algorithmus oder Beispielcode?

EDIT: Es ist für die Bildverarbeitung, also bedeutet “relativ hohe Qualität” eine anständige Zykluslänge und gute gleichmäßige Eigenschaften.

Schau dir das an Sammlung von Zufallszahlengeneratoren von George Marsaglia. Er ist ein führender Experte für die Generierung von Zufallszahlen, daher würde ich zuversichtlich sein, alles zu verwenden, was er empfiehlt. Die Generatoren in dieser Liste sind winzig, einige benötigen nur ein paar unsignierte Longs als Zustand.

Die Generatoren von Marsaglia sind nach Ihren Maßstäben für lange Lebensdauer und gute gleichmäßige Verteilung definitiv “hochwertig”. Sie bestehen strenge statistische Tests, obwohl sie für die Kryptografie nicht geeignet wären.

Verwenden der C-Code zum LFSR113 von L’écuyer:

unsigned int lfsr113_Bits (void)
{
   static unsigned int z1 = 12345, z2 = 12345, z3 = 12345, z4 = 12345;
   unsigned int b;
   b  = ((z1 << 6) ^ z1) >> 13;
   z1 = ((z1 & 4294967294U) << 18) ^ b;
   b  = ((z2 << 2) ^ z2) >> 27; 
   z2 = ((z2 & 4294967288U) << 2) ^ b;
   b  = ((z3 << 13) ^ z3) >> 21;
   z3 = ((z3 & 4294967280U) << 7) ^ b;
   b  = ((z4 << 3) ^ z4) >> 12;
   z4 = ((z4 & 4294967168U) << 13) ^ b;
   return (z1 ^ z2 ^ z3 ^ z4);
}

Sehr hochwertig und schnell. Verwenden Sie rand() NICHT für irgendetwas. Es ist schlimmer als nutzlos.

Hier ist ein Link zu einem ANSI C Implementierung einiger Zufallszahlengeneratoren.

Ich habe eine Sammlung von Zufallszahlengeneratoren erstellt, “einfachzufällig“, die kompakt und für eingebettete Systeme geeignet sind. Die Sammlung ist verfügbar in C und Python.

Ich habe mich nach ein paar einfachen und anständigen umgesehen, die ich finden konnte, und sie in einem kleinen Paket zusammengestellt. Dazu gehören mehrere Marsaglia-Generatoren (KISS, MWC, SHR3) und einige L’Ecuyer LFSR-Generatoren.

Alle Generatoren geben eine 32-Bit-Ganzzahl ohne Vorzeichen zurück und haben typischerweise einen Status, der aus 1 bis 4 32-Bit-Ganzzahlen ohne Vorzeichen besteht.

Interessanterweise habe ich ein paar Probleme mit den Marsaglia-Generatoren gefunden und versucht, all diese Probleme zu beheben/verbessern. Diese Probleme waren:

• Der SHR3-Generator (Bestandteil von Marsaglias KISS-Generator von 1999) war kaputt.
• MWC Low 16 Bits haben nur ca. 2^29.1 Zeitraum. Also habe ich einen leicht verbesserten MWC gemacht, der den niedrigen 16 Bit eine 2 gibt^59.3 Periode, die die Gesamtperiode dieses Generators ist.

Ich habe ein paar Probleme mit dem Seeding aufgedeckt und versucht, robuste Seeding- (Initialisierungs-) Verfahren zu entwickeln, damit sie nicht kaputt gehen, wenn Sie ihnen einen “schlechten” Seed-Wert geben.

Ich empfehle die wissenschaftliche Arbeit Zwei schnelle Implementierungen des minimalen Standard-Zufallszahlengenerators von David Carta. Sie können kostenlose PDF-Dateien über Google finden. Lesenswert ist auch die Originalarbeit zum Minimal Standard Random Number Generator.

Der Code von Carta liefert schnelle, qualitativ hochwertige Zufallszahlen auf 32-Bit-Rechnern. Für eine gründlichere Bewertung siehe das Papier.

Mersenne-Twister

Etwas aus Wikipedia:

• Es wurde für eine Periode von 2 entwickelt¹⁹⁹³⁷ − 1 (die Ersteller des Algorithmus haben diese Eigenschaft bewiesen). In der Praxis gibt es wenig Grund, einen größeren Zeitraum zu verwenden, da die meisten Anwendungen 2 nicht benötigen¹⁹⁹³⁷ einzigartige Kombinationen (2¹⁹⁹³⁷ ist ungefähr 4,3 × 10⁶⁰⁰¹; Dies ist viele Größenordnungen größer als die geschätzte Anzahl von Teilchen im beobachtbaren Universum, die 10 beträgt⁸⁰).
• Es hat eine sehr hohe Ordnung der dimensionalen Gleichverteilung (siehe linearer Kongruenzgenerator). Dies impliziert, dass es eine vernachlässigbare serielle Korrelation zwischen aufeinanderfolgenden Werten in der Ausgangssequenz gibt.

• Es besteht zahlreiche Tests auf statistische Zufälligkeit, einschließlich der Diehard-Tests. Es besteht die meisten, aber nicht alle der noch strengeren TestU01 Crush Randomness Tests.

• Quellcode für viele Sprachen unter dem Link verfügbar.

Ich würde eine aus der GNU C-Bibliothek nehmen, die Quelle kann online durchsucht werden.

http://qa.coreboot.org/docs/libpayload/rand_8c-source.html

Aber wenn Sie irgendwelche Bedenken hinsichtlich der Qualität der Zufallszahlen haben, sollten Sie sich wahrscheinlich sorgfältiger geschriebene mathematische Bibliotheken ansehen. Es ist ein großes Thema und der Standard rand Implementierungen werden von Experten nicht sehr geschätzt.

Hier noch eine Möglichkeit: http://www.boost.org/doc/libs/1_39_0/libs/random/index.html

(Wenn Sie feststellen, dass Sie zu viele Optionen haben, können Sie jederzeit eine zufällig auswählen.)