Der Versuch, eine Zahl von 0..4096 mit 0,3 zu multiplizieren, indem nur ganzzahlige Mathematik verwendet wird

Lesezeit: 6 Minuten

Benutzer-Avatar
Donald Hawken

Ich versuche mir vorzustellen, wie ich eine Zahl von 0..4096 mit 0,3 multiplizieren würde, indem ich nur ganze Zahlen mit Verschiebungsoperationen und Skalierung verwende. ohne zu teilenin C. Ich bin neu in diesem Zeug und alle Eingaben oder Schritt-für-Schritt-Vorschläge wären äußerst hilfreich.

  • Ich denke, er meint eine beliebige Zahl aus dem Bereich [0, 4096] multipliziert mit 0,3

    – Ferdinand Beyer

    23. März 2015 um 22:03 Uhr

  • Multipliziere mit 3 und dividiere dann durch 10.

    – Daniel Kamil Kozar

    23. März 2015 um 22:05 Uhr

  • Dies kann helfen: stackoverflow.com/questions/11694546/…

    – Ninja im Ruhestand

    23. März 2015 um 22:05 Uhr

  • (a*9830 + 16384)>>15

    – Benutzer3528438

    23. März 2015 um 22:08 Uhr

  • @DanielKamilKozar Ich habe deinen Kommentar positiv bewertet und dann bemerkt ‘ohne Division in C’.

    – Licht

    23. März 2015 um 22:20 Uhr


Benutzer-Avatar
ableuchten

Multiplizieren mit 0,3 ist dasselbe wie Multiplizieren mit (0.3*2^n)dann dividieren durch 2^n. Die zweite Stufe entspricht einer Rechtsverschiebung von n.

Aber was ist das Beste Wert von n?

Um dies zu finden, nehmen Sie Ihre größte ganze Zahl und finden Sie den größten Wert von n damit du multiplizieren kannst (0.3*2^n) ohne Überlauf. Mit 64-Bit-Ganzzahlen ohne Vorzeichen und 4096 als Maximalwert benötigen Sie

0.3*2^n <= 2^(64-12)

oder

0.3 <= 2^(64-12-n)

Diese Ungleichheit hat ein Maximum n wenn die RHS gleich 0,5 ist, also

2^-1 = 2^(64-12-n)

Also -1 = 64-12-n, n = 64-12+1 = 53.

Also ist die Antwort multiplizieren mit 2^53*0.3 dann um 53 nach rechts verschieben, dh

/* designed to work with input values 0 .. 4096 only */
uint64_t
multiplyby0_3 (uint64_t x)
{
    return (x * 2702159776422297ULL) >> 53;
}

Um zu überprüfen, dass es nicht überläuft, und wir haben das Beste naus bc:

2702159776422297*4096 = 11068046444225728512
2^64                  = 18446744073709551616

IE wird es nicht überlaufen, aber wenn wir es wieder mit 2 multiplizieren würden, würde es.

Für 32-Bit-Ganzzahlen wird die Antwort multipliziert mit 2^21*0.3 dann um 21 nach rechts verschieben, dh

/* designed to work with input values 0 .. 4096 only */
uint32_t
multiplyby0_3 (uint32_t x)
{
    return (x * 629146U) >> 21;
}

Und schließlich können Sie jede Multiplikation in eine Reihe von Additionen zerlegen, indem Sie sich die Binärzahl ansehen 1ist im Multiplikator. Also erlaubst du ‘Skalierung’ und ich nahm an, das bedeutete multiplizieren. Wenn nicht, hier ist die 32-Bit-Version (64-Bit-Version als Übung für den Leser übrig), die die Tatsache ausnutzt 629146 ist 10011001100110011010 (ein ordentliches Muster aufgrund des wiederkehrenden Binärbruchs). Wir werden in die andere Richtung runden und verwenden 10011001100110011001 stattdessen.

/* designed to work with input values 0 .. 4096 only */
uint32_t
multiplyby0_3 (uint32_t x)
{
    uint32_t y;
    x += x<<3;    /* * 1001 */
    y = x<<4 + x; /* * 10011001 */
    y += y<<8;    /* * 1001100110011001 */
    y += x<<16;   /* * 10011001100110011001 */
    return y >> 21;
}

  • Die Verwendung so vieler Bits ist übertrieben – da der Eingabebereich nur ~ 12 Bit beträgt, sollten Sie dies mit voller Genauigkeit innerhalb eines 32-Bit-Zwischenwerts tun können.

    – PaulR

    23. März 2015 um 22:19 Uhr

  • @duskwuff Ich glaube nicht, dass das richtig ist. Der höchstmögliche Wert (sofern der Eingang auf 0 .. 4096 begrenzt ist) ist 4096, also ist das Bit in den Klammern höchstens “2702159776422297 * 4096 = 11068046444225728512`, was bequem (gerade) in 64 Bit passt. Ich werde einen Kommentar zu den Codebeispielen kleben.

    – Licht

    23. März 2015 um 22:23 Uhr


  • @PaulR ist das nicht das, was das 32-Bit-Beispiel tut? Ja, mir ist klar, dass es übertrieben ist, aber ich wollte OP beibringen, wie man es im allgemeinen Fall ausarbeitet. Zu beweisen, dass eine geringere Anzahl von Bits niemals eine andere Antwort gibt, ist auf jeden Fall mehr Arbeit!

    – Licht

    23. März 2015 um 22:28 Uhr

  • Sicher – wenn Sie sich ändern 629146ULL zu 629146U so dass Sie nur 32-Bit-Arithmetik verwenden, dann ist es in Ordnung.

    – PaulR

    23. März 2015 um 22:36 Uhr

  • @ablight erhält den Pfeil nach oben. Die Anzahl der Bits, die auf 0,3 festgelegt werden sollen, ist die Anzahl der Bits in Ihrem vorzeichenlosen Wort (64 oder 32) minus 12 (da 2 ^ 12 = 4096). Sie möchten also, dass 0,3 als 0,3 * 2 ^ 52 oder 0,3 * 2 ^ 20 dargestellt wird, multiplizieren Sie Ihren Wert und (zum Runden auf den nächsten) addieren Sie entweder 2 ^ 51 und verschieben Sie 52 Bits nach rechts oder addieren Sie 2 ^ 19 und verschieben Sie nach rechts um 20 Bit.

    – Robert Bristol-Johnson

    24. März 2015 um 2:36 Uhr

Wenn Sie eine schnelle ganzzahlige Multiplikation, aber keine ganzzahlige Division haben, können Sie eine vernünftige Annäherung erhalten, indem Sie mit 1229 multiplizieren und dann um 12 Bit nach rechts verschieben. Zum Beispiel:

>> 100 * 1229
122900
>> 122900 >> 12
30

Das funktioniert, weil 1229 ungefähr ist 0.3 * 1 << 12. Der “reale” Wert ist 1228,8, daher wird die Schätzung in einigen Fällen um 1 hoch sein (68 von 4097 Werten). Es wird jedoch nie um mehr als 1 abweichen.

  • Ich würde +2048 vor >>12 machen, um eine einfache Rundung durchzuführen.

    – Benutzer3528438

    23. März 2015 um 22:10 Uhr

  • Was ist, wenn die Multiplikation überläuft?

    – EÖF

    23. März 2015 um 22:10 Uhr

  • @EOF: 122900 sind nur 17 Bit, also sollte dies mit 32-Bit-Ganzzahlen und einem 12-Bit-Eingabebereich in Ordnung sein.

    – PaulR

    23. März 2015 um 22:12 Uhr

  • @EOF Das maximale Zwischenergebnis in Anbetracht des in der Frage angegebenen Bereichs ist 1229 * 4096 = 5033984. Das liegt gut im Bereich einer 32-Bit-Ganzzahl; Wenn Sie innerhalb von 16 Bit bleiben müssen, ist das etwas schwieriger.

    Benutzer149341

    23. März 2015 um 22:12 Uhr

  • Richtig, aber das scheint nicht für alle Eingabewerte genau zu sein. Ich nahm an, dass OP versuchte, einen Weg zu finden, um dasselbe zu produzieren wie eine Ganzzahl mit 0,3 zu multiplizieren (das Ergebnis zu runden), und dies schien gelegentlich falsch zu sein. Sie brauchen ein paar Bits mehr (möglicherweise nicht so viele wie in meiner Antwort!)

    – Licht

    23. März 2015 um 22:32 Uhr

Mit einem klassischen Hack für divu10() unter. Ich bevorzuge den *n- und Shift-Ansatz, dachte aber, ich biete einen anderen POV an.

unsigned mult3tenths(unsigned x) {
  return divu10(x*3);
}

unsigned divu10(unsigned n) {
  unsigned q, rem;
  q = (n >> 1) + (n >> 2);
  q = q + (q >> 4);
  q = q + (q >> 8);
  q = q + (q >> 16);
  q = q >> 3;
  rem = n - q*10;
  return q + ((rem + 6) >> 4);  
}

  • ordentlich, obwohl ich traurig bin, dass die zweite Zeile nicht gelesen wurde div10(x+(x<<1)) und später rem=n-(q<<3)-(q<<1) nur um auch alle Multiplikationen zu eliminieren 🙂

    – Licht

    23. März 2015 um 22:34 Uhr

  • @ablight Vermute, dass ein guter Compiler dauern wird x*3 oder x+(x<<1) und machen Sie den gleichen Code.

    – chux – Wiedereinsetzung von Monica

    23. März 2015 um 22:43 Uhr

  • ja das wird es in der Tat. Aber zum Spaß habe ich einen noch kürzeren Weg ohne explizite Multiplikation gefunden und meiner Antwort hinzugefügt 🙂

    – Licht

    23. März 2015 um 23:21 Uhr

Ich weiß, dass dies kein Codierungsbeispiel ist, tut mir leid, aber wenn das Set so klein ist (range [0;4096]), warum nicht einen Ergebnisblock erstellen und einen Zeiger zum Extrahieren von Werten verwenden? Es wird die GPU-Zyklen stark reduzieren, da es keine Speicherbeschränkungen gibt.

Benutzer-Avatar
Chux – Wiedereinsetzung von Monica

Einfach viele Kombinationen der Form ausprobiert (A*x + B) >> n mit dem folgenden Testcode und kam auf:

// Scale by 4915, then shift 14.
int Mult3Tenths(int x) {
  return (x*4915 + 0) >> 14;  // Use 4915L if `int` is 16 bit.
}

Code testen

#define N3 (4096)
int main(void) {
  int target[N3 + 1];
  unsigned i;
  for (i = 0; i <= N3; i++) {
    target[i] = 0.3 * i;
  }

  // form (A*x + B) >> n
  int A, B, n;
  int besti = 0;
  for (n = 0; n < 31; n++) {
    int Amin = ((N3 * 0.3 - 1) * (1 << n) - (1 << n)) / N3 - 1;
    int Amax = ((N3 * 0.3 + 1) * (1 << n) + (1 << n)) / N3 + 1;
    for (A = Amin; A <= Amax; A++) {
      int Bmax = 1 << n;
      for (B = -Bmax; B <= Bmax; B++) {
        for (i = 0; i <= N3; i++) {
          int y = (A * i + B) >> n;
          if (y != target[i])
            break;
          if (i > besti) {
            besti = i;
            if (i == N3) {
              printf("i:%i A:%d B:%d n:%d\n", i, A, B, n);
              printf("!!!\n");
              exit(0);
            }
          }
        }
      }
    }
  }
  printf("???\n");
  return 0;
}

1180150cookie-checkDer Versuch, eine Zahl von 0..4096 mit 0,3 zu multiplizieren, indem nur ganzzahlige Mathematik verwendet wird

This website is using cookies to improve the user-friendliness. You agree by using the website further.

Privacy policy