Mid-Square-Methode

Mid-Square-Methode

Die Mittquadratmethode (auch Mid-Square-Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid-square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst später wurde diese Funktion auch als Hash-Funktion benutzt.

Es ist eine einfache Methode, bei der von einer Ausgangszahl das Quadrat gebildet wird. Die mittleren Ziffern des Quadrats werden als erste Zufallszahl genommen. In der nächsten Iteration wird die vorherige Zufallszahl quadriert, und die mittleren Ziffern ergeben die nächste Zufallszahl usw., bis die Ausgabe dieser Zufallszahlenreihe beendet wird.

Die Ausgangszahl kann z. B. die Uhrzeit sein oder die Anzahl an Millisekunden, die seit dem Start des Computers vergangen sind. Knuth (Lit.) zeigte, dass sich nach dieser Methode die Zufallszahlen nach 142 Zahlen wiederholen.

Beim Hashing ist die Ausgangzahl der Schlüsselwert, und es ist nur eine Iteration notwendig.

Ein Vorteil ist die einfache Implementierung des Verfahrens. Die Nachteile sind der sehr hohe Rechenaufwand, die sehr kurze Periodenlänge und das häufige Abstürzen auf die Zahl Null. Für die Verwendung als Hash-Funktion ist das Verfahren nicht geeignet, da die Kollisionshäufigkeit bei bestimmten üblichen Schlüsselwertverteilungen größer ist als bei anderen, einfacheren Hashing-Verfahren (siehe z. B. Multiplikative Methode).

Diese Methode besitzt nur noch historische Bedeutung.

Beispiel

Nach jeder Iteration werden jeweils die 2 mittleren Ziffern ausgewählt:

62 · 62 = 3844
84 · 84 = 7056
5 · 5 = 0025
2 · 2 = 0004
0 · 0 = 0000
...

Literatur


Wikimedia Foundation.

Игры ⚽ Поможем написать реферат

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Mid-square methode — Die Mittquadratmethode (auch Mid Square Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst… …   Deutsch Wikipedia

  • Mid square methode — Die Mittquadratmethode (auch Mid Square Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst… …   Deutsch Wikipedia

  • Mid-square-method — Die Mittquadratmethode (auch Mid Square Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst… …   Deutsch Wikipedia

  • Mid-square method — Die Mittquadratmethode (auch Mid Square Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst… …   Deutsch Wikipedia

  • Mid square method — Die Mittquadratmethode (auch Mid Square Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst… …   Deutsch Wikipedia

  • Mittquadratmethode — Die Mittquadratmethode (auch Mid Square Methode oder mittlere Quadratmethode genannt; aus dem englischen middle square method oder mid square method) wurde 1946 von John von Neumann als einer der ersten Zufallszahlengeneratoren vorgestellt. Erst… …   Deutsch Wikipedia

  • Fraction Continue — Exemple de développement infini en fraction continue En mathématiques, une fraction continue ou fraction continue simple ou encore fraction continuée[1] est une expression de la forme  …   Wikipédia en Français

  • Fraction continuée — Fraction continue Exemple de développement infini en fraction continue En mathématiques, une fraction continue ou fraction continue simple ou encore fraction continuée[1] est une expression de la forme  …   Wikipédia en Français

  • Fractions continues — Fraction continue Exemple de développement infini en fraction continue En mathématiques, une fraction continue ou fraction continue simple ou encore fraction continuée[1] est une expression de la forme  …   Wikipédia en Français

  • Fractions continuées — Fraction continue Exemple de développement infini en fraction continue En mathématiques, une fraction continue ou fraction continue simple ou encore fraction continuée[1] est une expression de la forme  …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”