Hilfe für Erstellung eines neuen Projekts?!

[test123]

Hallo Rechenkraftler!

Ich würde gern ein neues Projekt initiieren. Inhalt folgt gleich. Jedoch kenne ich mich bei der Programmierung nur im mathematischen Teil gut aus. Über eine Server-Client-Arbeitsverteilung, das Hosten des Projekts usw., habe ich mir noch keine Gedanken gemacht bzw. bin ich, was die technische Anwendung angeht, ahnungslos.

Es wäre schön, wenn man den Spaß etwa in yoyo als Subprojekt einklinken könnte. Oder aber es wäre schön, wenn ich hier Hilfe erhalten könnte, wie man den Spaß in ein Boinc-Projekt umsetzt. Ich denke doch, dass es da hier Experten für gibt.


Nun aber zum Inhalt:

Im Rahmen meiner Diplom-Arbeit hatte ich mich mit dem Problem des Perfekten Quaders (ein Quader, dessen Kantenlängen, Längen der Flächen- und Raumdiagonalen sämtlich ganze Zahlen sind) beschäftigt. Dieses Problem ist bisher noch ungelöst. (In meiner DA schwächte ich das Problem derart ab, dass ich eine der Bedingunen fallen ließ und so eine neue, untere Schranke für die Anzahl solcher "Teillösungen" mit gegebener Maximallänge der Raumdiagonale konstruieren konnte.)

Jetzt würde ich gern dieses Problem wieder aufgreifen und ihm numerisch etwas zu Leibe rücken. M.W. ist dies - bis auf ein paar Hobby-Programmierer - noch nie etwas koordinierter getan worden.

(Eben verlinkte Person konnte zeigen, dass es keinen perfekten Quader gibt, dessen "ungerade Kantenlänge" (ein perfekter Quader mit teilerfremden Kantenlängen hat genau eine Kantenlänge, die ungerade ist) <10^12 ist. Die Raumdiagonale der betrachteten Quader sollte dabei "im Mittel" nicht deutlich größer gewesen sein.

Ich selbst habe bisher nur ein - wenig optimiertes - C-Programm mit einem anderen Ansatz laufen. Innerhalb von ein paar Tagen konnte ich ähnliche Größenordnungen erreichen.)

Ein koordinierter Angriff auf größere Bereiche wäre m.E. durchaus möglich! (Der Algo, den ich im Hinterkopf habe, läuft etwa in O(n log n), wobei n die maximale Diagonalenlänge ist;wahrsch. kann man an dem log-Parameter noch etwas rumschrauben.) Deshalb hier dieser Thread.

Nur um auch fair zu sein: Es ist bisher noch kein perfekter Quader gefundenworden, und eine "krude" Heuristik sagt auch die Existenz keines weiteren voraus. Jedoch: Die gleiche Heuristik hätte auch der abgespeckten Version keine Lösung zugebilligt, wobei dort bewiesener Maßen[!] unendlich viele existieren! Jedoch bleibt der Suchraum- auch bei verbessertem Algorithmus - weiterhin unendlich, sodass auf diese Weise eine mögliche Nichtexistenz eines perfekten Quaders nicht gezeigt werden kann.

Unabhängig davon liefert das Projekt aber Daten für die abgeschwächten Problemstellungen. Dort sind bisher nur wohl nicht "scharfe" untere Schranken über das asymptotische Wachstum der Anzahl der Lösungen mit beschränkter Kanten- oder (was das gleiche ist) Diagonalenlänge bekannt. Eine Erweiterung der Datenbasis könnte hier zu neuen Vermutungen darüber führen.


Also, was meint ihr?

Grüße

[yoyo]

Mich würde zunächstmal die Meinung der anderen hier interessieren.

Du willst also einen bestimmten Bereich, bis zu einer Obergrenze zunächstmal über Boinc abgrasen wollen?
Hast Du schon Vorstellungen zu:
- WU-Laufzeiten
- Checkpoints
- Fortschrittsanzeige?

yoyo

[test123]

Hallo yoyo!

Die einzelnen Rehnungen sind, jeweils für sich genommen, nicht groß oder lang. Kernpunkt ist jeweils das Prüfen, ob eine Zahl der Größenordnung des Quadrats unserer oberen Grenze Quadratzahl ist. (Sagen wir, wir wollen bis 10^15 absuchen, müssen wir Zahlen der Größenordnung 10^30 prüfen.) Das dauert auf nem normalen Proessor halbwegs intelligent umgesetzt im Schnitt nur ein paar Millisekunden... Insofern lassen sich Checkpoints und Work-Unit-Laufzeiten relativ beliebig festlegen. (Sinnvoll wäre eine Zusammenfassung von Ergebnissen zu einem Checkpoint / einer Work-Unit von ca. 10^10 solcher Berechnungen. Zum Vergleich: Mein Rechner benötigt derzeit dafür etwa ne Viertel-Stunde. Ich durchlaufe aber gerade erst kleinere Zahlen, sodass beim Laufzeitende etwa die doppelte Rechenzeit benötigt werden wird.) eine Fortschrittsanzeige ließe sich dann auch sehr leicht implementieren...

Warum gerade Suchraum <=10^15? Weil es mir machbar erscheint. Mein PC ist derzeit selbst am Rechnen. Dies etwas nach oben exploriert (etwas mehr als die Hälfte hab ich schon) sagt, dass ich in insgesamt ca. 10 CPU-Tagen bis 10^13 komme. Da der Algorithmus in etwa mit O(n log n) skaliert, wäre man - vorsichtig geschätzt - nach < 2000 CPU-Tagen fertig und hätte diederzeit höcste, bekannte Schranke um Faktor 1000 erhöht.


Grüße

[Norman]

hört sich interessant an für ein 'ziel', dass es höchstwahrscheinlich niemals geben wird (sollte man der beschreibung der allgemeinen problematik gedanken schenken).
mal was anderes als primzahldoktorei oder nicht ?! wer weiss für man das noch alles evtl. brauchen könnte, gerade weil es noch nie weiter berechnet wurde.

[Txt.file]

eine anwendung des ganzen würde mich mal interessieren. weil ansonsten ists für mich erstmal nicht besser als die ganzen primzahlprojekte.

[test123]

Nun, wie üblich bei Diplomarbeiten handelt es sich um eine kleine Problemstellung aus einem größeren Rahmen, der mit aktueller Forschung zu tun hat. Hier ist dies die Untersuchung so genannter K3-Flächen bzw. genauer der Arithmetik der rationalen Punkte auf diesen. (Geht man eine Dimension runter, so landet man z.B. bei elliptischen Kurven. Das Verständnis der Arithmetik ihrer rationalen Punkte (z.B. Satz von Mordell) war schon für sich genommen nen math. Durchbruch. Anwendungen, die daraus entstanden, waren z.B. das Faktorisierungsverfahren mithilfe elliptischer Kurven ECM, ein schneller Primzahltest ECPP oder ein neues Krptographie-Verfahren.)

Von einer allgemeinen Theorie der rationalen Punkte auf K3-Flächen ist man zur Zeit noch ein gutes Stück entfernt, obwohl es aktueller Forschungsgegenstand ist. Eine Vermutung von Manin besagt z.B., dass man die rationalen Punkte einer solchen K3-Fläche auf Scharen rationaler Kurven auf dieser suchen soll.

Ein mögliches Vorgehen, was häufig ersteinmal angewendet wird, wenn man so gar keine Ahnung vom allgemeinen Verhalten hat, ist, sich ersteinmal ein par Beispiele genauer anzuschauen. Dies ist eines. Noch dazu ein halbwegs historisches: Die Problemstellung ist seit der griechischen Antike bekannt und auch z.B. Euler hat sich mit ihm beschäftigt. Insofern ist es von gewissem Interesse.


Grüße

[Txt.file]

klingt gut. versteh zwar kaum was, aber wenn andere mathematische probleme darauf basieren, ists schonmal von interesse (für mich).

[nico]

Das Problem hört sich so an, als sei es Perfekt für Grafikkarten geeignet: Hauptsächlich Integer Berechungen und keine Datenabhängigkeiten... Wo sind ist unsere Grafikkartenprogrammierertaskforce?

[Michael H.W. Weber]

eine anwendung des ganzen würde mich mal interessieren. weil ansonsten ists für mich erstmal nicht besser als die ganzen primzahlprojekte.

...den Zahn, daß Primzahlen keine Anwendung hätten, muß ich Dir allerdings hiermit ziehen.

Michael.

[respawner]

sagen wir so, die großen Primzahlen wie die merserne (schreibt man die so) haben keine Anwendung. Bei Verschlüsselungen, braucht man ja Primzahlen oder Pseudoprimzahlen die unbekannt sind. Wenn also z.B. das Produkt zweier Primzahlen verwendet werden.

[Thommy3]

Nunja, mit größeren Mersenneprimzahlen, kann man immer bessere Zufallszahlengeneratoren erstellen. Wobei es da aber auch andere gute Algorithmen gibt.

[mxplm]

Das Problem hört sich so an, als sei es Perfekt für Grafikkarten geeignet: Hauptsächlich Integer Berechungen und keine Datenabhängigkeiten...

Als GPU Projekt könnte man 10^16 bis 10^17 anvisieren ;)