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 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. Donald Knuth zeigte, dass sich nach dieser Methode die Zufallszahlen nach 142 Zahlen wiederholen (bei Verwendung von 20-Bit-Zahlen).

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 beiden mittleren Ziffern ausgewählt:

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

Literatur

Content Disclaimer

Informasi ini disarikan dari Wikipedia dan disajikan kembali untuk tujuan edukasi. Konten tersedia di bawah lisensi CC BY-SA 3.0. Kami tidak bertanggung jawab atas ketidakakuratan data yang bersumber dari kontribusi publik tersebut.

  1. The information displayed on this website is sourced in part or in whole from Wikipedia and has been adapted for the purpose of restating it. We strive to provide accurate and relevant information, however:
  2. There is no guarantee of absolute accuracy. Wikipedia is an open, collaborative project that can be edited by anyone, so information is subject to change.
  3. It is not intended to constitute professional advice. The content displayed is for informational and educational purposes only. For important decisions (e.g., medical, legal, or financial), please consult a professional.
  4. Content copyright. Wikipedia is licensed under the Creative Commons Attribution-ShareAlike License (CC BY-SA). This means that content may be reused with appropriate attribution and shared under a similar license.
  5. Responsible use. Any risk arising from the use of information from this website is entirely the responsibility of the user.