3. zahl 31 schnell zu berechnen?

zahl 31 schnell zu berechnen?

  • ?

    Hallo,

    ich habe mal irgendwo im Zusammenhang mit hash tables
    gehört (ich weiß nicht mehr genau wo) dass die Zahl 31 eine für den compiler
    schnell berechenbare zahl darstellt da sie über 32-1 dargestellt werden kann.

    Ist das so? Wenn ja warum? Mich interessiert der genau Hintergrund? Bit shift mit 2 << 5 -1 oder so?

    danke euch

    0
  • C

    Dieser Thread wurde von Moderator/in SeppJ aus dem Forum C++ (auch C++0x und C++11) in das Forum Rund um die Programmierung verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.

    0
  • S

    Warum solltest Du die 31 überhaupt berechnen wollen, wenn Du schon weißt, dass die 31 gesucht ist?

    0
  • ?

    die zahl 31 wird irgendwie zum durchmischen von bit-werten hergenommen (in der schlüsselberechnung die ja eindeutig sein soll). ich frage mich halt warum 31 und nicht 11 oder so...deswegen die frage

    0
  • B

    Du hast wahrscheinlich gehört, dass man modulo 32 schnell berechnen kann, indem man mit 31 bitweise Und-verknüpft (analog für alle anderen Zweierpotenzen.)

    0
  • ?

    soll heißen dass ich mich verhöhrt habe?
    also wäre es unsinn zu behaupten dass 31*zahl schneller geht als 11*zahl ?
    das mit modulo versteh ihc aber auch nicht ganz. modulo macht ansonsten alles über differenzen?

    0
  • C

    frakccc schrieb:

    soll heißen dass ich mich verhöhrt habe?

    Ja

    frakccc schrieb:

    also wäre es unsinn zu behaupten dass 31*zahl schneller geht als 11*zahl ?

    Ja

    frakccc schrieb:

    das mit modulo versteh ihc aber auch nicht ganz. modulo macht ansonsten alles über differenzen?

    Modulo dividiert normalerweise.

    0
  • ?

    cooky451 schrieb:

    frakccc schrieb:

    soll heißen dass ich mich verhöhrt habe?

    Ja

    frakccc schrieb:

    also wäre es unsinn zu behaupten dass 31*zahl schneller geht als 11*zahl ?

    Ja

    Falsch, 31 * zahl ist äquivalent zu (zahl << 5) - zahl und damit schneller als eine reguläre Multiplikation, darum wird oft 31 statt andere primzahlen zum berechnen von hash codes benutzt.

    0
  • B

    gastantwort schrieb:

    Falsch, 31 * zahl ist äquivalent zu (zahl << 5) - zahl und damit schneller als eine reguläre Multiplikation, darum wird oft 31 statt andere primzahlen zum berechnen von hash codes benutzt.

    Klingt gut 👍

    0
  • C

    Bashar schrieb:

    Klingt gut 👍

    Relativ. Zugegeben, daran hatte ich nicht gedacht. Allerdings schien es mir auch gleich komisch, dass auf einer heutigen Architektur die Multiplikation so langsam ist. Und na ja was soll ich sagen. Ja, VS11 macht diese Optimierung. Nein, sie hilft nicht. Bei mir ist die Shift Variante wesentlich langsamer (0.037 zu 0.05) als die Multiplikation. Was schon irgendwie lustig ist, wenn man bedenkt, dass VS das Programm somit effektiv "negativ" optimiert. Es verunsichert mich auch etwas, aber einen Fehler in dem Test kann ich nicht finden. IDEONE gibt für beide Varianten in etwa die gleiche Geschwindigkeit an. http://ideone.com/Ro59c

    0
  • ?

    cooky451 schrieb:

    Bashar schrieb:

    Klingt gut 👍

    Relativ. Zugegeben, daran hatte ich nicht gedacht. Allerdings schien es mir auch gleich komisch, dass auf einer heutigen Architektur die Multiplikation so langsam ist. Und na ja was soll ich sagen. Ja, VS11 macht diese Optimierung. Nein, sie hilft nicht. Bei mir ist die Shift Variante wesentlich langsamer (0.037 zu 0.05) als die Multiplikation. Was schon irgendwie lustig ist, wenn man bedenkt, dass VS das Programm somit effektiv "negativ" optimiert. Es verunsichert mich auch etwas, aber einen Fehler in dem Test kann ich nicht finden. IDEONE gibt für beide Varianten in etwa die gleiche Geschwindigkeit an. http://ideone.com/Ro59c

    Mach mal was ohne Iterator Dereferenzierung und messe etwas was länger braucht.

    0
  • K

    frakccc schrieb:

    [...]die zahl 31 wird irgendwie zum durchmischen von bit-werten hergenommen[...]

    Wenn ich raten müsste, was du gehört/gelesen hast: Bei einer Prüfsummenberechnung der Art

    unsigned check_sum(int numBytes, const unsigned char data[])
{
  unsigned result = 0;
  for (int i=0; i<numBytes; ++i) {
    result = (result * (UCHAR_MAX+1) + data[i]) % 31;
  }
  return result;
}

    (also Die Binärdaten als riesige Zahl betrachtet, deren Divisionsrest ich hier berechne) eine schlaue Sache ist, da

    • 31 eine zu 2 teilerfremde Zahl ist und
    • die Zahlen 0...30 die 5 Bit relativ effektiv ausnutzen

    wenn man eine 5-bittige-Prüfsumme von Binärdaten haben will.

    Geht das in die Richtung dessen, was du gehört/gelesen hast?

    0
Anmelden zum Antworten