Array rundum mit modulo unsigned

Ich versuche, die Implementierung eines lagged Fibonacci pseudo-Zufallszahlengenerator für ganze zahlen bis zu einem gewissen maximum. Es unterhält ein array von Werten

int values[SIZE] = { /* 55 seed values */ };

und verwendet die folgenden Funktion geben Sie den nächsten Wert

unsigned lagfib()
{
    static unsigned idx = 0;
    int r = values[idx];

    /* The following does not work: */
    values[idx] = (values[(idx-24) % SIZE] + values[(idx-55) % SIZE])
                 % MAX_VALUE;
    idx = (idx+1) % SIZE;
    return r;
}

In der Wirkung values sollte eine einfache ring-buffer, der ist immer voll. Die Subtraktion und modulo-Umbruch der index um an das Ende des Arrays. SIZE sollte immer mindestens 55, aber ich möchte die Runde bis zu 64 beschleunigt die modulo -.

Aber anscheinend habe ich die modulo-Berechnungen falsch und ich weiß nicht, wie Sie zu beheben. Ändern der index-Typ int nicht die Dinge verbessern.

(PS.: Ja, static Daten ist schlechter Stil, aber ich wollen, dass es lesbar für C-und C++ - Programmierer, da es sich auf beide Sprachen.)

  • Warum ist static Daten schlechter Stil (in C, oder meinst du nur C++)?
  • In C ist es auch schlechter Stil, denn es führt zu einer nicht-reentrant-code.
  • Warum ist das schlecht?
  • denn es macht den code nicht threadsicher.
  • Warum ist das schlecht? Oder vielmehr, Wann ist es schlecht? Die Sprache konstruieren, die nicht existieren würde, wenn es waren immer schlecht, oder?
  • Ich Neige dazu, zu schreiben, meinen code in eine thread-sichere Weise, es sei denn, ich mache Experimente, wie in diesem Fall. Also ja, static hat einen Sinn und das war es, aber nur dieses war ein one-off-Programm.
  • Sie können immer um Ihre static Daten-problem (und der Reentranz-Problematik) durch die übergabe der Staat (in diesem Fall idx) wie ein Zeiger, und die Arbeit mit, dass: unsigned lagfib(unsigned* idx). Benutzer dann nur initialisiert es manuell auf 0 (oder verwendet lagfib_init(&state)) vor dem ersten Aufruf. Wenn Sie nicht sicher sind, ob idx ist immer wieder eine unsigned können Sie verstecken Ihre Art hinter einem typedef, oder verstecken es in einer (nicht-Opak für die Umsetzung Gründen, Opak-API-Weise) struct lagfib_stat.

InformationsquelleAutor Fred Foo | 2010-10-18
  1. 2

    Wenn z.B. idx weniger als 24, erhalten Sie rundum-zum anderen Ende der Reihe Reihe von unsigned int. 55 ist kein Teiler von z.B. 2^32, so wird dies nicht geben Ihnen die richtigen Ergebnisse.

    Können, sehe ich zwei Optionen:

    • Erhalten drei separate idx Variablen offset von 24 und 55 beziehungsweise.
    • Z.B. (idx - 24 + SIZE) % SIZE.

    Eigentlich, ich würde die erste option wählen, und vermeiden Sie die modulo vollständig durch umschreiben der Schrittweite als:

    idx = ((SIZE-1) == idx) ? 0 : (idx+1);

    wird wohl Weg sein, schneller als die Berechnung von modulo.

    • +1 und akzeptiert, aber ich gehe davon modulo 64 ist, werden erstellt, um eine Bitmaske op. Ich sollte wirklich aktualisieren meine modulare Arithmetik.
    • Ach so, Sie haben tatsächlich SIZE == 64 im code?
    • Übrigens, haben Sie berücksichtigt, dass Ihre seed-Werte müssen in "umgekehrter" Reihenfolge?
    • Zurück zu SIZE=55, und bemerkt, dass idx + 55 - SIZE ist jetzt idx also brauche ich nur zwei Indizes. Vielen Dank!
    InformationsquelleAutor Oliver Charlesworth
  2. 3

    Lässt idx = 0 und SIZE = 64.

    (idx-24) % SIZE wird ein sehr großer Wert (4294967272 für ein 32-bit int )als idx ist nicht signiert, so dass es ein Ungültiger index.

    Um die kreisförmigen Effekt, den Sie hinzufügen SIZE vor unter Modul:

    (idx-24+SIZE) % SIZE wird (0-24+64)%64 die Auswertung zu 40.

    • idx ist nicht signiert.
    InformationsquelleAutor codaddict
  3. 0

    Greifen Sie auf Werte mit einem negativen index. Zum Beispiel:

    -24 % 55 == -24

    So müssen Sie einige Logik-wrap-around-das Ende des Arrays. C/C++ nicht, dies für Sie tun.

    • idx ist nicht signiert.
    InformationsquelleAutor chrisaycock
Schreibe einen Kommentar