Projektidee gesucht

Grid-Computing, technische Entwicklung von Distributed Computing...
Nachricht
Autor
Dj Ninja
Task-Killer
Task-Killer
Beiträge: 721
Registriert: 21.04.2008 10:37

Projektidee gesucht

#1 Ungelesener Beitrag von Dj Ninja » 02.04.2015 14:41

Ich würde gerne ein Boinc-Projekt aufbauen, um meine eigenen Programmierfähigkeiten zu testen bzw. zu verbessern und um im Zuge der Diskussion über das Creditsystem was zum Probieren zu haben.

Wonach ich suche ist ein Problem, was sich in endlicher Zeit mit DC lösen lässt oder wo sich Teilprobleme in endlicher Zeit lösen lassen (z.B. die Primzahlsuche ist nie abgeschlossen, aber eine einzelne Zahl auf Primalität testen geht vergleichsweise schnell) und was ich nicht jahrelang studiert haben muß um es zu verstehen und einen Computer-lösbaren Ansatz programmieren zu können.

Also gerne mathematische Ideen. Mir ist bislang nichts vernünftiges eingefallen.

Wer hat eine Idee?

mibere

Re: Projektidee gesucht

#2 Ungelesener Beitrag von mibere » 02.04.2015 18:08

Eine spannende Idee habe ich grad auch nicht parat, aber dein Vorhaben finde ich gut, lehrreich und mutig - was bitte positiv zu verstehen ist.
Wenn man sich mal auf Wikipedia umsieht, da scheint es einiges zu geben, bspw. Taxicab-Zahl.

Benutzeravatar
Myrmidon
Brain-Bug
Brain-Bug
Beiträge: 542
Registriert: 04.10.2007 17:55

Re: Projektidee gesucht

#3 Ungelesener Beitrag von Myrmidon » 02.04.2015 18:25

Wie wäre es mit dem finden aller glücklicher Primzahlen http://de.wikipedia.org/wiki/Gl%C3%BCckliche_Zahl oder fröhlicher Zahlen http://de.wikipedia.org/wiki/Fr%C3%B6hliche_Zahl bis zu irgend eniem Zahlenwert.
Bild

Bild

Dj Ninja
Task-Killer
Task-Killer
Beiträge: 721
Registriert: 21.04.2008 10:37

Re: Projektidee gesucht

#4 Ungelesener Beitrag von Dj Ninja » 02.04.2015 23:15

Yep, genau... irgendwie sowas.

Ich hatte vor einigen Jahren auch schon einen eigenen 3x+1 Client geschrieben, nur das Projekt nicht fertiggestellt weil ein anderes schneller war und ich zwei gleiche Projekte unnötig fand. Damals hab ich überlegt, diesen Client auf 5x+1 oder so umzustellen.

Eine zweite Möglichkeit wäre Rectilinear Crossing Numbers wiederzubeleben. Allerdings fällt mir dazu nur der Bruteforce-Ansatz ein und der ist bei einer großen Anzahl Punkte nur auf sehr kleinen Feldern praktikabel. Ich bin mir nicht sicher ob das bessere Ergebnisse liefert, als bereits bekannt sind. Da bräuchte man einen anderen Ansatz, um die Anzahl Kreuzungen zu reduzieren... sowas hab ich nicht studiert.

Aber das mit den "fröhlichen Zahlen" schaue ich mir an. Da scheint es ja eine Menge Zahlen mit irgendwelchen speziellen Eigenschaften zu geben. Interessant wird das wohl bei wirklich großen Zahlen, ähnlich wie bei der Primzahlsuche. Da muß ich mal schauen wie lange der Test einer größeren Zahl dauert. Danke für den Tip!

mibere

Re: Projektidee gesucht

#5 Ungelesener Beitrag von mibere » 03.04.2015 17:50

Lösung des Zauberwürfels (Rubik's Cube) aus jeder möglichen Ausgangsstellung

- in der kürzestmöglichen Anzahl an Zugfolgen oder
- beliebige Anzahl an Zugfolgen, hauptsache die Lösung wurde gefunden

Dj Ninja
Task-Killer
Task-Killer
Beiträge: 721
Registriert: 21.04.2008 10:37

Re: Projektidee gesucht

#6 Ungelesener Beitrag von Dj Ninja » 03.04.2015 18:19

Gute Idee, aber dafür brauch ich kein DC Projekt, das schafft eine einzelne Kiste alleine. Es gibt auch bereits Robotor, die das Ding einscannen und anschließend auf optimalem Wege lösen.

Grund dafür ist, daß es feste Abläufe gibt, um ein bestimmtes Feld oder eine Fläche an eine bestimmte Position zu bringen und der unbewegliche Mittenstein die Sollfarbe der Fläche vorgibt. Dadurch ist das Ding für eine Maschine (oder ausreichend trainierte Menschen) keine größere Herausforderung.

Das Ding ist für DC nicht komplex genug. *g*

Aber ähnliche Ideen bzw. geometrische Projekte find ich super.

mibere

Re: Projektidee gesucht

#7 Ungelesener Beitrag von mibere » 03.04.2015 18:28

...notfalls würde es auch die 8x8-Variante geben :wink:

Dennis Kautz
Vereinsmitglied
Vereinsmitglied
Beiträge: 4742
Registriert: 22.02.2003 02:12
Kontaktdaten:

Re: Projektidee gesucht

#8 Ungelesener Beitrag von Dennis Kautz » 05.04.2015 08:25

Wie wäre es mit was in Richtung zelluläre Automaten / Game of Life? Vielleicht mal nicht klassisch zweidimensional, sondern in nem drei- oder höherdimensionalen Raum? Und dann die komplexesten Ergebnisse in ner DB sammeln?

Dj Ninja
Task-Killer
Task-Killer
Beiträge: 721
Registriert: 21.04.2008 10:37

Re: Projektidee gesucht

#9 Ungelesener Beitrag von Dj Ninja » 09.04.2015 06:28

Sooo, das mit den "fröhlichen Zahlen" habe ich mir mal angeschaut.

Ich vermute, daß es extrem (unendlich) viele in großer Dichte davon gibt, da auch eine sehr große Zahl nach der ersten Iteration nur noch sehr klein ist. Alle zu suchen ist also wie Sandkörner sammeln in der Wüste. Dadurch bliebe eine Suche nach Extremwerten, ähnlich wie 3x+1 - welche Zahl erzeugt die längste Folge.

Bei der Berechnung gibt es das Problem, daß es im Prozessor keine wirklich effiziente Möglichkeit gibt, eine Riesenzahl in ihre einzelnen Ziffern aufzuspalten. Dazu müßte man sie immer wieder durch 10 teilen (wodurch man die jeweils letzte Ziffer als Rest erhält), bedeutet bei Riesenzahlen einen Ablauf, der der schriftlichen Division sehr ähnlich ist. Der Vorteil dabei ist wie gesagt, daß eine denkbare Riesenzahl nach dem ersten Rechenschritt keine mehr ist. Alles was weniger als 53 Millionen (2^32/9^2) Ziffern hat, passt nach der ersten Iteration in ein 32 Bit Register und sowas wird problemlos von jedem 386er durch 10 geteilt. Ich glaub so weit ginge die Suche in endlicher Zeit nicht. Der erste Rechenschritt ist also der einzige, der wirklich lange dauert. Man könnte ihn vereinfachen, wenn man davor ausgeht, daß es immer nur einen ersten Riesen-Rechenschritt gibt (würde das Programm auf Zahlen bis 10^53.000.000 limitieren), indem man die Zahl als Klartext behandelt und direkt alle Ziffern abarbeitet.

Das bedeutet aber auch, daß sich die Länge der Folge sehr schnell gegen ihren praktikablen Maximalwert festläuft. Wenn man also nach solchen Rekorden sucht, werden die sehr schnell sehr selten. Der erste Rechenschritt reduziert unvorstellbare 10^53.000.000 Zahlen auf weniger als 2^32 Möglichkeiten. Keine gute Motivation...

Besteht denn echtes Interesse an einem solchen Projekt? Den Client dafür schreiben wäre kein Problem, der Kern sind ein paar Zeilen Assembler-Code. Das wäre vor allem auf älteren Prozessoren verdammt schnell, es braucht so gut wie keinen Speicher.

Benutzeravatar
Myrmidon
Brain-Bug
Brain-Bug
Beiträge: 542
Registriert: 04.10.2007 17:55

Re: Projektidee gesucht

#10 Ungelesener Beitrag von Myrmidon » 09.04.2015 10:54

Dj Ninja hat geschrieben: Besteht denn echtes Interesse an einem solchen Projekt? Den Client dafür schreiben wäre kein Problem, der Kern sind ein paar Zeilen Assembler-Code. Das wäre vor allem auf älteren Prozessoren verdammt schnell, es braucht so gut wie keinen Speicher.
Ohne die Antwort zu kennen...besteht denn echtes Interesse an Collatz Conjecture? Eines der Projekte mit der meisten Rechenleistung.
Bild

Bild

Dj Ninja
Task-Killer
Task-Killer
Beiträge: 721
Registriert: 21.04.2008 10:37

Re: Projektidee gesucht

#11 Ungelesener Beitrag von Dj Ninja » 10.04.2015 15:29

Ich schätze aber die Möglichkeit, bei Collatz irgendeine längere Folge zu finden, größer ein, als bei fröhlichen Zahlen. Die ersten Rechenschritte machen die Zahl so winzig, daß nur sehr kleine Zahlen (ich schätze unter 300) eine Chance haben, nochmal größer zu werden. Das gibt es in dieser Form bei Collatz nicht.


Antworten

Zurück zu „Hintergrundinfos zu Verteiltem Rechnen“