Extended Meissel-Lehmer |
| 28.02.2023, 16:08 | Telefonmann1 | Auf diesen Beitrag antworten » | ||
| Extended Meissel-Lehmer Es geht also darum den Meissel-Lehmer-Algorithmus möglichst effektiv zu programmieren. Die erste Umsetzung von D. Lehmer im Jahr 1958 auf einer IBM701 würde ich heute mal ganz frech als Schulmathematik bezeichnen und damit als verstanden voraussetzen. Will man es etwas ausgeklügelter haben, bietet sich die ganz oben verlinkte Arbeit von J.C. Lagarias et al. an. Es gibt dazu auch den folgenden Open-Source-C-Code mit der folgenden Datei für einen guten Einstieg in das Thema. Dort findet man eine einfache aber noch recht übersichtliche Programmierung des im paper vorgestellten Algorithmus. Ich habe diesen Code zu Testzwecken so angepasst, dass er mit MS-VisualStudio 2010 läuft und auch korrekte Resultate liefert. Kann mir nun jemand erklären, warum die Funktion S2(....) tatsächlich den Algorithmus des Lagarias-papers implementiert? zB wird im Paper für die Berechnung von S2 eine Binärdarstellung der betreffenden Zahlen verwendet, die in der Funktion dann aber nicht zu finden ist. Der Autor des Codes hat sich hier offensichtlich gut passende Gedanken zur Umsetzung bzw. Berechnung von S2 gemacht. PS: Als Anfänger darf ich hier scheinbar keine urls einstellen. Diese liefere ich gerne nach, wenn ihr mir sagt wie. Ich habe diesen Beitrag lokal bei mir inklusive urls abgespeichert. Es handelt sich also nur um die Einleitung zum eigentlichen Thema. |
||||
| 28.02.2023, 23:01 | Telefonmann1 | Auf diesen Beitrag antworten » | ||
RE: Extended Meissel-Lehmer
Hat sich eigentlich schon wieder erledigt. Schreibt man den Binärbaum mal für einen relativ einfachen Fall wie zB unter Berücksichtigung der Regel T auf, wird es klar 
|
||||
| 01.03.2023, 10:29 | HAL 9000 | Auf diesen Beitrag antworten » | ||
Vermutlich genießt der "Meissel-Lehmer-Algorithmus" unter den Foren-Mitgliedern keine allzu große Bekanntheit, ich bin nach kurzem Wikipedieren auch nur auf das oben vermutlich gemeinte Paper gestoßen - es geht also um eine Methode zur Berechnung der Primzahlfunktion , Ich wollte das an der Stelle nur anmerken, damit der Thread nicht zu einem reinen Selbstgespräch mutiert, wo sich alle wundern: Worüber redet Telefonmann1 überhaupt? |
||||
| 01.03.2023, 14:20 | Telefonmann1 | Auf diesen Beitrag antworten » | ||
Genau so ist es und vielen Dank für die Beteiligung am Thema. Es ist die Referenz [2] des englischsprachigen WP-Artikels zum Meissel-Lehmer algorithm. Das pdf auf ams.org verwendet einen etwas schöneren Schriftsatz. Eine interessante Programmierung des beschriebenen Algorithmus findet man auch auf github com und es lohnt sich wirklich diese Umsetzung nachzuvollziehen, vorausgesetzt man hat sich schon etwas mit den Prinzipien der verwendeten Sieb- bzw. Zählfunktionen vertraut gemacht. Ich finde es immer wieder faszinierend, wie man durch mathematische Optimierungen solche technischen Algorithmen immer schneller und effizienter machen kann. Ich wünschte ich könnte Links mitangeben, aber dazu habe ich scheinbar noch nicht oft genug geschrieben. Freundliche Grüße, Bernhard |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
| Die Größten » |
| Die Neuesten » |