Die Mathe-Redaktion - 22.01.2017 00:45 - Registrieren/Login
Auswahl
Aktion im Forum
Suche
Stichwortsuche in Artikeln und Links von Matheplanet
Suchen im Forum
Suchtipps

Bücher
Englische Bücher
Software
Suchbegriffe:
Mathematik bei amazon
Naturwissenschaft & Technik
In Partnerschaft mit Amazon.de
Kontakt
Mail an Matroid
[Keine Übungsaufgaben!]
Impressum

Bitte beachten Sie unsere Nutzungsbedingungen, die Distanzierung, unsere Datenschutzerklärung und
die Forumregeln.

Sie können Mitglied werden oder den Newsletter bestellen.

Der Newsletter Dez. 2016

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 398 Gäste und 20 Mitglieder online.

Sie können Mitglied werden:
Klick hier.

Über Matheplanet
 
Zum letzten Themenfilter: Themenfilter:
Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Die Collatz-Folge programmieren
Thema eröffnet 2016-10-23 08:10 von gonz
Druckversion
Druckversion
Antworten
Antworten
Seite 7   [1 2 3 4 5 6 7]   7 Seiten
Autor
Kein bestimmter Bereich Die Collatz-Folge programmieren
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2363
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.240, vom Themenstarter, eingetragen 2017-01-21 11:34


Hallo cyrix & al !

Das hört sich doch schon wirklich gut an. Auch 80.000 Kerntage wären ja irgendwie machbar - dann dauert es eben auf 120 Kernen 2 Jahre... Ich denke, wir bleiben einfach dran.

Ich habe festgestellt, dass ich gar nicht danach suchen muss, wie ich der datenbank das hantieren mit grossen integer beibringe, denn wenn die Werte vor dem Eintragen, also zB von einem C Programm, geprüft wurden, dann kann man die verwaltung welcher candidate welche anderen obsolet macht ja auch als Stringvergleich handhaben.

Wenn wir die Definition so wählen, dass ein "candidate" in unserem Projekt eine Startzahl ist von max. 67 Bit ist, deren Collatz Folge einen Wert von 112 Bit erreicht oder überschreitet, dann kommt es auf der Seite des zentralen Servers ja auch nicht auf Geschwindigkeit an, da der Anteil der Kandidaten im Vergleich zur Anzahl der Reste, die den Siebausgang erreichen, sehr gering ist.

Ich stelle schonmal kurz das Protokoll vor, das ich zwischen Client und Server gerade implementiere, damit frühzeitig Kritik einfliessen kann.

Basis ist eine tcp/ip Verbindung, auf der "menschenlesbare" Klartextmeldungen ausgetauscht werden. Damit kann man schon mit einem einfachen telnet Client testen.

Ich verwende am Servern den Port 10108 (wichtig daran ist m.E. nur, dass er über 10.000 liegt, also nicht im Bereich der well known ports mit fester Zuordnung).

Die Identifizierung erfolgt, indem der Client einen Magic-Wert überträgt und damit einem zulässigen User zugeordnet werden kann. Die Magic-Werte kann ich per PN auf dem MP übermitteln, sodass wir ein wenig "schwarze schafe" ausgrenzen können, die uns sonst ggf. die schnittstelle "vollmüllen".

Es können Reste angefordert werden. Der Server vergibt noch nicht abgehakte Reste einfach im Kreis herum, sodass derselbe Rest erst möglichst spät, aber bei ausbleiben einer Antwort doch auch wieder, einem anderen User zugeordnet wird. Es ist nicht notwendig, dass ein Client den Rest, für den er candidates liefern will, vorher angefordert hat, es wird dadurch nur "doppelarbeit" vermieden, candidates können auch ohne das reste-procedere gemeldet werden.

Der Client meldet candidates, die sich aus dem Rest ergeben, und einen Hash Wert, wenn er den Bereich "abgehakt" hat. Der Hash wert könnte zB einfach aus der Schrittzahl aller aus dem Rest zu berechnenden Folgen ermittelt werden und erlaubt einen zumindest teilweisen "peer check". Beide Meldungen werden vom Server bestätigt und sollen vom Client andernfalls wiederholt werden. (Es werden allerdings alle candidates, auch solche, die bereits ggf. schon beim Melden obsolet waren, in der Datenbank gehalten, für Test- und Debug Zwecke)

Man kann über die schnittstelle alle bisher "überlebenden" Candidates abfragen. Dabei wird ausgegeben: Startwert + dessen Bitzahl, Recordwert + dessen Bitzahl, Username und wann eingestellt. Hier bin ich mir noch nicht sicher, ob wir das überhaupt brauchen, denn es könnte alternativ auch einfach eine Website geben, auf der man sich die Ergebnisse ansehen kann.

Ein Dialog Server-Client sähe dann zB so aus:
telnet session
Connected to krottencom.de on port 10108
 
OK! talk to me...
 
magic:xxxxxxxxxxxx
OK! Hello gonz.
 
rest?
OK! rest=121232121221
 
candidate:1211212121212121212
OK! candidate accepted.
 
exit!
OK! have fun.
 
Connection closed by foreign host.

Soweit... Wenn jemand damit herumspielen möchte kann ich gerne die Schnittstelle asap bereitstellen. Für die Datenbank knobele ich noch und werd das db design nochmal vorstellen, bevor wir mit irgendeiner art von offiziellem Betrieb anzustarten. Es wird dann natürlich auch einen passenden Client geben bzw. ein Stück C code das die Kommunikation erledigt.

Einen schönen Start ins WE wünscht

gonz

PS.: Eine Website wäre ggf. auch ganz gut um zentral die notwendige software zu verteilen und anleitungen etc zu posten. ma gucken :)








-----------------
to fight! (Don Quijote de la Mancha)



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 20.04.2013
Mitteilungen: 90
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.241, eingetragen 2017-01-21 20:09


Ich hab' mal noch überprüft, um wieviel sich der Sieberfolgt mit einer Rest 2 mod 3 Prüfung erhöht - es sind tatsächlich nur 0,45%.
Allerdings handelt es sich bei diesen 0,45% eben auch umrecht zickige Folgen, so das der Test letztlich zu einer Beschleunigung führt.
Bei nicht vorgesiebten Startwerten sollte er Sieberfolg entsprechend höher sein.

Ich habe meine Souce  FCM.cpp um eine reine 64bit-Version erweitert, die, in Assembler implementiert, eigentlich jede Nicht-Multistep-Variante schlagen sollte.
Sie wird aktiviert durch Setzen des #define FULL128BIT 0.

Sie kann im interessanten Bereich wenigstens zweimal hintereinander aufgerufen werden, da erst dann ein neuer Pfadrekord in Reichweite kommt. Nach jedem Aufruf mit eine Returnwert 1 müsste eine "Nachiteration" erfolgen, um den Startwert für einen weiteren Aufruf zu ermitteln. Dafür käme entwerder eine Multistep-Variante in Frage, oder aber ein spezielle Variante, der sämtliche Abprüfungen fehlen (die Abprüfungen wurden ja schon mit der 64bit-Variante erledigt).

Falls der AktuellePfadrekord > (Startwert<<24) ist, kann die 64bit-Variante auch für weitere Aufrufe verwendet werden.

Leider ist die 64bit-Varante nicht für GPUs geeignet, denn denen fehlt, soweit ich das gesehen habe, ein CountTrailingZeros-Befehl.

Die Routine besteht aus 40 Stufen, in denen eine 3x+1-Operation, eine CountTrailingZeros-Operation, ein Aufsummieren der gezählten Nullen, eine (z.B. stage17) oder zwei (z.B. stage18) Abprüfungen und eine Schiebeoperation enthalten ist.
C++
  :
  :
  :
#define M3XP1(x) (x=(x<<1)+x+1)
  :
  :
  :
  //[ stage17
  M3XP1(low);                         // 3x + 1
  ctz = __builtin_ctzll(low);
  sum += ctz; 
  if ((low == 0) || (sum >= 27)) {    // x < startval?
    return 0;
  }
# if XEQU2MOD3_TEST
  //if ((ctz  & 1) && (sum >= 27)) {    // x == 2 mod 3?
  //  return 0;
  //}
# endif
  low >>= ctz;
  //]
  //[ stage18
  M3XP1(low);                         // 3x + 1
  ctz = __builtin_ctzll(low);
  sum += ctz; 
  if ((low == 0) || (sum >= 29)) {    // x < startval?
    return 0;
  }
# if XEQU2MOD3_TEST
  if ((ctz  & 1) && (sum >= 28)) {    // x == 2 mod 3?
    return 0;
  }
# endif
  low >>= ctz;
  //]
  :
  :
  :
 




  Profil  Quote  Link auf diesen Beitrag Link
gonz hat die Antworten auf ihre/seine Frage gesehen.
Seite 7Gehe zur Seite: 1 | 2 | 3 | 4 | 5 | 6 | 7  
Neues Thema [Neues Thema] Antworten [Antworten]    Druckversion [Druckversion]

 


Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2017 by Matroids Matheplanet
This web site was made with PHP-Nuke, a web portal system written in PHP. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]