Zufallszahlengeneration optimiert: Neuer Algorithmus wirft effizient gezinkte Würfel
Klimaforschung, Epidemiologie, Finanzen: Ansatz erleichtert Simulationen komplexer SystemeWürfel: Virtuelles Zinken macht durchaus Sinn (Foto: Jose-Luis Olivares/mit.edu)
Gewichteter Zufall
Das schnelle, effiziente Generieren von Zufallszahlen ist eine der grundlegendsten Herausforderungen in der Informatik und für Computersimulationen. Oft wäre dabei eine Gewichtung sinnvoll, dass also verschiedene Zahlen mit unterschiedlicher Wahrscheinlichkeit auftreten. Wenn zum Beispiel zwei Sportteams aufeinandertreffen, gibt es nur drei mögliche Ergebnisse - aber dass das stärkere Team gewinnt, ist wahrscheinlicher als ein Überraschungssieg oder Unentschieden. Hier könnte also ein passend gezinkter Würfel am schnellsten geeignete Zufallszahlen liefern - und genau das ist die Aufgabe des FLDR.
Der Algorithmus, der kommende Woche bei der 23rd International Conference on Artificial Intelligence and Statistics http://aistats.org näher vorgestellt wird, verspricht nämlich exakt gewichtete Ergebnisse. Das heißt: Jede einer Reihe von Zufallszahlen tritt mit genau der gewünschten Wahrscheinlichkeit auf. Das allerdings ist gar nicht das Entscheidende am neuen Algorithmus; der eigentliche Durchbruch liegt darin, wie wenig Speicherbedarf dieser hat. Eben das sollte ihn den MIT-Forschern zufolge für Simulationsanwendungen sehr interessant machen.
Kompakt und schnell
Die Informatiker Donald Knuth und Andrew Yao haben bereits 1976 einen Algorithmus vorgestellt, der gezinkte Würfel mit der größtmöglichen zeitlichen Effizienz wirft. Allerdings ist ihr Ansatz ein unglaublicher Speicherfrssser. "Wir sind fast so zeiteffizient, aber wesentlich speicherffizienter", betont MIT-Doktorand Feras Saad; einer der Entwickler des FLDR. Dieser erfordert bis zu 10.000 Mal weniger Speicher, braucht aber höchstens 1,5 Mal so lange für eine Operation. Im Vergleich zum derzeit für gewichtete Zufallszahlen gängigen Ansatz "Alias" sei FLDR etwas effizienter und bisweilen auch schneller.
Das macht den neuen Algorithmus für immer größere, komplexere Computersimulationen interessant. Denn hier gibt es oft nur eine begrenzte Zahl möglicher Ergebnisse, die nicht gleich wahrscheinlich sind. Als Beispiel verweist das MIT besonders auf Inferenz-Verfahren, wo mehrere Simulationen reale Daten erklären sollen. Das ist klarerweise rechenaufwendiger als eine einfache Simulation, kommt aber beispielsweise bei den UN zum Einsatz, um seismische Daten zu interpretieren. Zu anderen Feldern, die profitieren könnten, zählt die dank COVID-19 ins Rampenlicht geratene Epidemiologie.
Aussender: pressetext.redaktion
Ansprechpartner: Thomas Pichler
E-Mail: Diese E-Mail-Adresse ist vor Spambots geschützt! Zur Anzeige muss JavaScript eingeschaltet sein!
Tel.: +43-1-81140-314
Website: www.pressetext.com
© pressetext.deutschland +++ pressetext.austria +++ pressetext.schweiz +++ termindienst +++ fotodienst +++ newsfox.com und der jeweilige Aussender
http://www.pressetext.com/news/20200529019pte20200529019
Forschung/Entwicklung, Technologie/Digitalisierung
Medieninhaber und Herausgeber:
pressetext Nachrichtenagentur GmbH, Josefstädter Straße 44, A-1080 Wien
pressetext ist reichweitenstärkster Nachrichtenverbreiter für Entscheider und Journalisten in der DACH-Region. Die inhaltliche Verantwortung für redaktionelle Meldungen (pte) liegt bei pressetext, für Pressemitteilungen (pts) und Kapitalmarktmitteilungen börsennotierter Unternehmen (pta) beim jeweiligen Aussender. Die Nachrichten werden auf den pressetext-Länderplattformen publiziert und je nach Abonnement-Profil und gewählter Zustellart einzeln oder täglich als Newsletter an die Abonnenten verschickt. Weitere Informationen erhalten Sie bei unserem Redaktionsservice unter Tel. +43-1-81140-300.