Die Mathe-Redaktion - 23.06.2017 19:08 - Registrieren/Login
Auswahl
Schwarzes Brett
Wartet auf Antwort2017-06-22 12:40 bb ?
Alte Mathematikbücher
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 Apr. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 499 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 3   [1 2 3 4 5 6 7 8]   8 Seiten
Autor
Kein bestimmter Bereich Die Collatz-Folge programmieren
trunx
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 16.08.2003
Mitteilungen: 2637
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.80, eingetragen 2016-11-11 10:46


2016-11-11 10:28 - cyrix in Beitrag No. 79 schreibt:
@trunx: Gar nicht. ;)
schade :)

Wenn es einen nicht-trivialen Zyklus geben sollte (und nur dafür spielt der Wert als Verhältnis der Halbierungs- zu den Verdreifachungsschritten ja eine Rolle), dann läuft oben angegebenes Programm einfach - wie bei einer divergierenden Collatz-Folge auch - in eine Endlosschleife und macht sich dadurch bemerkbar. Da aber ein solcher nichtrivialer Zyklus extrem unwahrscheinlich ist (muss > 10^10 Folgenglieder enthalten), und für Startwerte < 2^61 auch von TOlivera e Silva nicht gefunden wurden, wird der Fall gar nicht weiter betrachtet.
ja, diese grössenordnung ist mir bekannt, aber eben weil es sich um derart grosse zahlen handelt, muss ln3/ln2 auch so genau bestimmt werden (auch wenn man vermutlich nichts auf seinem heim-pc finden wird :p)

Wenn man ihn beliebig genau berechnen würde müssen, dann wäre wohl die GNU Multi Precission - Bibliothek  GMP das Mittel der Wahl.
auch für diesen link mein dank; ich selbst hab mich durch rückwärts addition für die erzeugung von ln3 und ln2 gekämpft, um damit peu a peu immer ein weiteres glied in der kettenbruchentwicklung (also jeweils optimale rationale approximationen) zu erzeugen.

bye trunx


-----------------
das problem des menschen ist nicht, dass er fleisch von tieren isst, sondern dass er für sein wachstum KRIEG gegen alle anderen lebensformen führt. dieser krieg nennt sich (land)wirtschaft, seine ideologische legitimation kultur.



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2004
Mitteilungen: 2388
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.81, eingetragen 2016-11-12 20:45


2016-11-11 03:31 - cyrix in Beitrag No. 77 schreibt:

Und eine letzte Bemerkung: Derzeit ist startdepth mit dem Wert 25 definiert. Eigentlich sollte auch eine weitere Erhöhung möglich sein (bis einem irgendwann der dafür notwendige Speicherplatz ausgeht, den man auch entsprechend zur Verfügung stellen muss). Jedoch passieren für startdepth = 26 gerade komische Dinge, wobei ich vermuten würde, dass dies damit zusammenhängt, dass dann Zahlen um 31 Bits o.ä. geschoben werden, was dem Compiler irgendwie nicht zu gefallen scheint...

"Fehler" gefunden! :) Es war tatsächlich das Problem, dass hier was aus dem vorgesehenen Speicherplatz rausgeschoen wurde: Bisher (Zeile #32 im ersten Code-Teil in Beitrag #77) wurde der Wert startdepthpow definiert als (1 << startdepth). Das wird offensichtlich vom Compiler als vom Typ int (= __int32) angesehen, also insbesondere vorzeichenbehaftet. Natürlich geht das schief, wenn man die führende 1 dann in Zeile #98 des zweiten Code-Teils auf das vorderste (=32.ste) Bit schiebt...

Dies kann man umgehen, indem man in die Definition gleich reinschreibt, dass es ein unsigned __int64 sein soll, d.h. Zeile #32 im ersten Code-Teil geht über in
#define startdepthpow ((unsigned __int64) 1 << startdepth)

Jedoch stellt sich auf meinem Rechner heraus, dass das erst einmal zu einer kleinen Verlangsamung führt, die sich aber leicht beheben lässt, wenn man Zeile #173 des zweiten Code-Teils die Aktualisierung des Dreierrests (Variable rest_3) schon vorher berechnet, d.h. anstatt
rest_3 = (rest_3 + (startdepthpow % modbase_3)) % modbase_3;

jetzt
rest_3 = (rest_3 + rest_3_add) % modbase_3;

wobei vor Beginn der Schleife die Variable rest_3_add einführt und natürlich zu
const unsigned int rest_3_add = startdepthpow % modbase_3;

berechnet. (Auch dem checkit_3-Array und dem range-Wert kann man das Schlüsselwort const gönnen. Vielleicht kann der Compiler ja nun damit was anfangen... Tatsächlich habe ich aber keine Laufzeit-Veränderungen gemessen.)


Jedenfalls kann man nun den Wert startdepth, der die Tiefe angibt, wie viele Startiterationen der relevanten Restklassen ausgeführt werden sollen, bevor es in die Main-Schleife geht, auf größere Werte als 25 setzen. (Gegebenenfalls muss man mehr Speicherplatz für die Arrays, in denen die Ergebnisse dieser ersten Iterationen abgelegt werden, entsprechend anpassen. Dies geht durch den in Zeile #33 des ersten Codeteils angegebenen Wert
#define nr_start_classes (1 << 20) // reicht aus für startdepth <= 26

, den man dann natürlich so weit erhöhen muss, dass die Anzahl aller nach den startdepth ersten Iterationen noch überlebenden Restklassen <= diesem Wert ist.Für startdepth = 32 reicht für nr_start_classes der Wert 33515912, der knapp kleiner ist als 2^25. (Das dürfte auch der limitierende Faktor sein. Jedenfalls kann ich gerade auf meinem Rechner nicht mehr Speicher reservieren. Wahrscheinlich reize ich das RAM damit gerade ganz gut aus, da ja vier 64-Bit-Arrays dieser Länge reserviert werden, was allein also schon 2^30 Bytes braucht.)

Wählt man startdepth >= 31, so muss man noch die Zeile #133 im ersten Code-Teil anpassen, dass der dort im Rekursionsaufruf vorkommende Parameter rest + (1 << nr_it) korrekt berechnet wird, also rest + ((unsigned __int64) 1 << nr_it).

Tatsächlich ist das (startdepth = 32) auch der Wert, der auf meinem Rechner die optimalen Werte liefert:

Roosendaal #60, single threaded (3,2GHz, 4 GB RAM)
Beitrag #77 in 5.38 min
Beitrag #91 in 3.00 min;

Rosendaal #61, analoge
Beitrag #77 in 17.21 min
Beitrag #91 in 09.43 min,


also noch mal knapp nen Faktor 2. :)


Viele Grüße
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
Amateur
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.10.2012
Mitteilungen: 771
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.82, eingetragen 2016-11-13 03:22


Hallo,

mit dem neuen Programm habe ich mal ein wenig gespielt, aktuell mit nur einem Thread und ohne Änderung von startdepth. Getestet habe ich bis Roosendal #65, im Bereich von Roosendaal #88 und im Bereich von 1<<62. Die Geschwindigkeit des Programms erwies sich dabei als unabhängig von der Größe der zu untersuchenden Zahlen. Das hat mich positiv überrascht.  
Zu Beginn der while(1)-Schleife in main() wird startnr+=range; ausgeführt, also noch vor der eigentlichen Berechnung. Der tatsächlich untersuchte Bereich startet also später, als ich erwartet hatte. Die Berechnungen waren aber vollständig und richtig.
Dankeschön, Cyrix!

Viele Grüße A.



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2004
Mitteilungen: 2388
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.83, eingetragen 2016-11-13 04:22


2016-11-13 03:22 - Amateur in Beitrag No. 82 schreibt:
Die Geschwindigkeit des Programms erwies sich dabei als unabhängig von der Größe der zu untersuchenden Zahlen. Das hat mich positiv überrascht.  

Das gilt natürlich nur, solang wir auch mit unserer 128-Bit-Arithmetik hinkommen. Wenn wir über den ereich hinaus langen, und auf allgemeine Big-Int-Implementierungen gehen müssen, wird natürlich die Geschwindigkeit darunter leiden...

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
Amateur
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.10.2012
Mitteilungen: 771
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.84, eingetragen 2016-11-13 11:27


Auch bei Eingabedaten größer 64 Bit erreicht die Folge nur sehr selten die 128-Bit-Grenze. Sollte dieser Fall eintreten, wird ersatzweise ein triviales Verfahren mit höherer Bitzahl verwendet. Der eigentliche Algorithmus wäre nicht betroffen. Daß diese zweistufige Methode recht weit trägt, zeigen die Beiträge #56 und #61 für die Kombination 64Bit/128Bit.

Viele Grüße A.



  Profil  Quote  Link auf diesen Beitrag Link
astrid-clz
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.10.2016
Mitteilungen: 21
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.85, eingetragen 2016-11-13 12:51


Einen angenehmen Sonntag :)

Es macht Sinn denke ich - erstmal bei 64bit Startwert / 128bit Pathrecord bleiben und alle Werte auswerfen, die grösser als 128 Bit gehen, diese dann einzeln mit einem Programm nachbearbeiten, das sich Zeit lassen kann.

Oder: erst einmal die Startwerte bis dahin abgrasen, es gibt ja diesen komischen Wert #88, den Roosendaal selber nicht verifiziert hat, und ich habe nirgendwo eine Info gefunden, ob der nächste Wert jenseits der #88 mit 64 / 128 Bit auskommt.

Wir könnten mal zusammenwerfen, wer an einer Parallelisierung auf mehrere Linux-Rechner mitmachen würde, ich hätte aktuell einen Rechner mit 6 Kernen dafür frei privat (mein Arbeitgeber spielt leider nicht mit). Solange das nicht zu viele Leute sind, könnten wir die Reste händisch aufteilen, die jeweils bearbeitet werden sollen.

Das ganze gespannt beobachtend

Astrid



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2004
Mitteilungen: 2388
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.86, eingetragen 2016-11-13 13:17


Hallo Astrid,

was die Parallelisierung auf mehrere Rechner angeht, so kann man ja einfach verschiedene Suchbereiche verteilen, indem man eben Pakete (in Vielfachen der range-Variable) packt und dann entsprechend zuweist. Z.B.: Rechner A betrachtet den Bereich k*2^50 -- (k+1)*2^50, Rechner B den von (k+1)*2^50 -- (k+2)*2^50 usw.


Allerdings überlege ich noch, da der Speicherplatz bei dem "Vorsieben" ja derzeit der Flaschenhals ist, ob man die Daten wirklich rausschreiben muss. Eventuell könnte man auch die "äußere Schleife" (bzw. deren Inhalt), die gerade in der main-Methode steht, direkt in den Rekursionsabbruch der Methode startiteration packen, sodass man dort die Daten, die man dafür braucht, direkt zur Verfügung hat und nicht zwischenspeichern muss. (So geht Olivera e Silva vor und siebtin seinem 2008er Durchlauf bis zur Tiefe startdepth = 48; zum Vergleich in Beitrag #81 gehe ich bis zur Tiefe startdepth = 32. Dies dürfte noch einmal etwa ein Faktor 4 in der Laufzeit ausmachen.)

Es ergeben sich zwei Probleme bei diesem Vorgehen:

*) Die Bereiche, die die nun deutlich mehr einzeln betrachteten Restklassen unabhängig voneinander durchsuchen, werden deutlich größer, sodass man haufenweise Rekod-Kandidaten einzelner Restklassen bekommt, von denen man erst am Ende, wenn alle Restklassen betrachtet wurden, weiß, ob sie denn echte Rekordhalter sind. Bisher ging die "Verwaltung" dieser Kandidaten von Hand. Dann muss man sich wohl programatisch um sie kümmern.

*) Die Parallelisierung auf mehrere Threads gestaltet sich schwieriger, da man nicht wie bisher einfach die verschiedenen (nun viel zu vielen) Restklassen durchlaufen und von jedem Thread nacheinander eine der Restklassen bearbeiten lassen kann. (Man will ja auch den Baum nicht regelmäßig wieder erzeugen müssen.) Wahrscheinlich kann man das Problem lösen, indem man einen Mittelweg geht:

Erzeuge den Baum bis zu einer vorgegebenen, sinnvollen Tiefe (z.B. 20 oder auch 30 Iterationen) und speichere hier die Informationen raus. Dann verteile dies auf die einzelnen Threads, die nun ihrerseits erst einmal analog in ihrer betrachteten Restklasse noch ein paar Iterationen in ihrer Restklasse weiter verzweigen, und dort dann in jedem Blatt erst mit der "äußeren Schleife" ansetzen...


Dies noch als algorithmische Verbesserungs-Idee.

Viele Grüße
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
matph
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 20.11.2006
Mitteilungen: 5291
Aus: A
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.87, eingetragen 2016-11-13 14:19


Hallo,

Ohne den Code im Detail angesehen zu haben, würde ich vermuten, dass sich noch die eine oder andere Moduloperation oder/und Division einsparen lässt, was einen deutlichen unterschied machen sollte, da diese extrem langsam sind.

Des weiteren lassen sich die Schleifen via OpenMP parallelisieren smile

Auch klingt es fast so, als seien nicht alle Optimierungsflags wie -march=native, -funsafe-math-optimizations, -finite-math-only, -fno-trapping-math... gesetzt.
--
mfg
matph


-----------------
Wir müssen wissen, wir werden wissen. Hilbert
Das Buch der Natur ist in der Sprache der Mathematik geschrieben. Galilei



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2004
Mitteilungen: 2388
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.88, eingetragen 2016-11-13 19:03


So, zwischendurch konnte ich einen kleinen "Satz" beweisen:

Satz: Mündet keine Startzahl kleiner 110 * 2^60 (was < 1,27 * 10^20 ist) in einen nicht-trivialen Collatz-Zyklus, so besitzt ein solcher mindestens 114.208.327.604 ungerade Folgenglieder.

Bemerkung: Bisher klar war die Aussage nur, wenn alle Startzahlen kleiner ca.  2,17 * 10^20 (was > 188 * 2^60 ist) überprüft worden wären. Die dafür notwendige Schranke wurde also um den Faktor <0,5844, also fast ein Bit, reduziert. (Zur Größenordnung: Olivera e Silva hat bei seinem 2008er Durchlauf dies bis zur Schranke 5 * 20^60 verifiziert. Mit den heutigen Rechnern sollte der Aufwand bis zur im "Satz" genannten Schranke in etwa vergleichbar sein mit dem, was Olivera e Silva vor acht Jahren geleistet hat. [Faktor 22 größerer Bereich, ca. Faktor 16 schnellere Rechentechnik])

Beweis-Skizze:
Zuerst kurz zum allgemeinen (und bekannten) Vorgehen, dann zur hier vorgenommenen Verschärfung.

Man sieht recht schnell ein, dass in einem nicht-trivialen (d.h. von 1 --> 4 --> 2 --> 1 ... verschiedenen) Collatz-Zyklus sich die x/2 und die (3x+1)-Schritte in etwa wie log(3) : log(2) verhalten müssen: Die ersten dividieren immer durch 2, die zweiten multiplizieren mit (nur leicht mehr als) 3. Wenn insgesamt nach einem Zyklus wieder die Startzahl herauskommen soll, müssen also die Zweierpotenz, durch die dividiert wird, und die "Dreierpotenz", mit der multipliziert wird, gleich sein. Logarithmieren liefert dann das oben genannte Verhältnis von deren Anzahlen.

Leicht rigoroser: In den (3x+1)-Schritten wird die Zahl x mit (3+1/x) multipliziert. Ist x groß, so ist dieser Faktor nur wenig größer als 3. Dies rechtfertigt, für genügend große x dann die entsprechende Näherung zu machen, dass der Faktor "ungefähr" 3 sei.

Rechnet man es exakt durch, dann erhält man, dass

<math>\frac{\log(3)}{log(2)} < \frac{g}{u} < \frac{\log\left(3 + \frac{1}{u}\sum_{x\in Z, 2\nmid x} \frac{1}{x}\right)}{log(2)}</math>

gelten muss, wobei g und u die Anzahl der geraden und ungeraden Collatz-Folgenglieder im Zyklus Z sind und die Summe im Logarithmus des hinteren Terms über alle ungerade Folgenglieder x dieses Zykluses läuft.

Nun hat man eine rationale Zahl g/u, die eine irrationale log(3)/log(2) gut annähern soll (da ja auch die obere Schranke für große x nicht allzuviel größer ist als die untere), d.h., das läuft i.W. auf die Kettenbruchentwicklung von log(3)/log(2) hinaus und für g/u kommen i.W. die endlichen Näherungsbrüche dafür in Frage.

Direkt kann man zwar jetzt mit der eben genannten Formel noch nichts anfangen, da man ja den Zyklus erst kennen müsste, damit man daraus die ungeraden Werte x ermitteln und so die Summe berechnen könnte, die Teil der oberen Schranke an g/u ist. Aber man kann ja Abschätzungen vornehmen: Klassischer und einfacher Weise macht an sich das Leben einfach und schätzt ab 1/x <= 1/m < 1/limit, d.h., jedes ungerade Folgenglied x innerhalb des Zykluses wird abgeschätzt durch das kleinste (und damit auch ungerade) Folgenglied m dieses Zykluses und dieses wiederum durch die bisher überprüfte obere Schranke limit, von der man weiß, dass keine Zahl <= dieser Teil eines nicht-trivialen Zyklus ist.

So kommt man zur bekannten Aussage, dass ab einem Wert von limit von ca. 2,17*10^20 die obere Schranke an g/u gerade klein genug wird, dass ein bestimmter Näherungsbruch an log(3)/log(2) aus der Kettenbruchentwicklung nun außerhalb des Intervalls liegt und nun der nächste zum Zug kommt, was insbesondere dann die Aussage u > 10^11, die behauptet wird, nach sich zieht.

(Genaueres zu diesem Vorgehen findet man in der schon in diesem Thread verlinkten Master-Arbeit d-scholarship.pitt.edu/24817/1/Masters_-_Collatz.pdf . Dort wird der Spaß auch ordentlich und exakt bewiesen.)


Nun zur Verbesserung: Die Abschätzung der Summe 1/x, die hier vorgenommen wurde, ist offensichtlich alles andere als scharf. Auch in er eben verlinkten Arbeit wird schon eine einfache Überlegung angegeben, wie man den Wert um den Faktor 8/9 verringern kann. Man zeigt dazu sinngemäß, dass auf ein "kleines" ungerades Folgenglied ein nicht mehr ganz so kleines folgen muss, d.h., man kann jenes zweite ungerade Folgenglied durch einen etwas größeren (und damit sein Reziproke durch einen etwas kleineren) Wert abschätzen.

Wir verfolgen diese Idee etwas weiter:

Grob: Zerhacke den Zyklus in bestimmte, paarweise disjunkte Teilstücke (wobei der Begriff hier im Folgenden nur [!] Abschnitte aufeinanderfolgende Folgenglieder meinen soll) und betrachte in jedem dieser die ungeraden Folgenglieder. Wenn es einen Wert val gibt, sodass in jedem dieser Teilstücke die Summe s der Reziproken 1/x der ungeraden Folenglieder s <= val * #u, mit #u der Anzahl der ungeraden Folgenglieder in diesem Teilstück, ist, dann ist auch die Summe <math>S:=\sum_{x\in Z, 2\nmid x} \frac{1}{x}</math> über die Reziproken aller ungeraden Folgenglieder des Zykluses S <= val * u (mit u der Anzahl aller ungerader Folgenglieder des Zykluses): Die Summe S entsteht ja aus der Addition aller Teilstücke, sodass jedes ungerade Folgenglied in genau einem dieser Teilstücke enthalten ist. Analog ist adurch natürlich auch u die Summe der #u der einzelnen Teilstücke.

Anders formuliert: Ist der Durchschnitt der Reziproken der ungeraden Folgenglieder in jedem Teilstück <=val, dann gilt das auch für den gesamten Zyklus.

Wir brauchen am Ende für unsere zu zeigende Aussage <math>\frac{1}{u}\sum_{x\in Z, 2\nmid x} \leq \frac{1}{limit}</math>, wobei limit = 2,17*10^20 der Wert von oben ist. Der Term auf der linken Seite ist genau der durchschnittliche Wert der Reziproken der ungeraden Folgenglieder im Zyklus. Um die hier gestellte Ungleichung zu bweisen, reicht also nach der Vorbemerkung eine Zerlegung des Zykluses in disjunkte Teilstücke zu finden, sodass in jedem Teilstück der Durchschnitt der Reziproken der dort vorkommenden ungeraden Folgenglieder <= 1/limit ist.

Im Folgenden konstruieren wir eine solche Zerlegung des Zykluses, sodass in jedem Teilstück mindestens eine, maximal 128 ungerade Folgenglieder liegen und für alle (bis auf maximal eines) jeweils der Durchschnitt der Reziproken der ungeraden Folgenglieder in einem solchen Teilstück < (1-epsilon) * 1/limit ist. (Das (1-epsilon) mit einem festen, kleinen elspilon brauchen wir, um das evtl. vorhandene Reststück, zu dem wir nur eine schlechtere Abschätzung angeben können, zu "verarzten", sodass am Ende dennoch gezeigt werden kann, dass das durchschnittliche Reziproke über den gesamten Zyklus < 1/limit ist. Dies nur der Vollständigkeit halber, wird hier nicht weiter ausgeführt, da es am Ende nur eine Fehlerabschätzung ist; und die Fehler hier sehr klein sind. Ich habe die Rechnungen gemacht. ;) )



Beginnen wir also mit einer beliebigen ungeraden Zahl x innerhalb unseres betrachteten Collatz-Zykluses und betrachten sie modulo 2^128. Dann ist das das Verhalten der Folge über den Zeitraum der nächsten 128 Halbierungsschritte (und zwischendrin gegebenenfalls einigen 3x+1-Schritten) eindeutig durch die Restklasse res := x Mod 2^128 festgelegt. Die erste Zahl (nämlich x) unserer maximal 2*128 Glieder langen Teilfolge (nämlich 128 Halbierungsschritte und dazwischen + einen am Start noch einmal höchstens so viele (3x+1)-Schritte) ist nach Voraussetzung ungerade. Aber es können eben auch noch maximal 127 weitere ungerade Folgenglieder in dem gerade betrachteten Bereich des Zykluses auftreten. Wir betrachten dabei nun die ersten ein, zwei, drei, ... dieser ungeraden Folgenglieder und berechnen jeweils die Durchschnitte ihrer Reziproken 1/x. Haben wir ein Anfangsstück gefunden, in welchem der Durchschnitt der Reziproken < (1-epsilon) * 1/limit ist, so schließen wir das Teilstück mit dem letzten in dem Anfangsstück vorhandenen ungeradem Folgenglied ab.

Das nächste (also in der Folge als nächstes erreichte) ungerade Folgenglied im Zyklus stellt dann den Ausgangspunkt für das nächste (potentiell bis zu 128 ungerade Folgenglieder umfassende) Teilstück dar, bei dem wir genauso vorgehen. So erhalten wir sukzessive die Zerlegung des gesamten Zykluses in Teilstücke, in denen jeweils der Durchschnitt der Reziproken der in ihnen enthaltenen ungeraden Folgenglieder < (1-epsilon) * 1/limit ist. Nur beim letzten (aus maximal 127 ungeraden Folgengliedern bestehende) Teilstück könnte sich herausstellen, dass es zu kurz ist, um seinen Durchschnitt dieser Reziproken unter diesen Wert zu drücken. Da aber auch dann dieser Durchschnitt recht einfach beschränkt werden kann, und es im gesamten Zyklus >10^10 ungerade Folgenglieder geben muss (das ist schon bewiesen), wird dies durch den Faktor (1-epsilon) bei den übrigen Teilstücken mehr als aufgefangen, sodass das zu zeigende Resultat folgt.

Und wie schätzt man nun (ohne den Zyklus und seine Folgenglieder zu kennen) nun diesen Durchschnitt der Reziproken der ungeraden Folgenglieder eines solchen Teilstücks ab? Dafür werden mehrere Beobachtungen herangezogen, wobei die ersten zwei die "Hauptarbeit" machen, d.h., die folgenden sind nur noch dazu da, um leichte Verbesserungen vorzunehmen:

*) Wir nehmen an, dass schon gezeigt worden wäre, das keine nat. Zahl <= 110 * 2^60 := T in einen nicht-trivialen Zyklus führt. (Dies ist die Voraussetzung des Satzes.) Insbesondere müssen dann also auch alle Folgenglieder des Zykluses größer als T sein.

*) Wir kennen nach Konstruktion die Restklasse der Startzahl x eines Teilstücks modulo 2^128. Damit wissen wir, wie groß die nächsten Folgenglieder (bis 128 Halbierungsschritte aufgetreten sind) relativ zu x sind. (Bzw. kennen wir diese nur "genügend genau", indem wir für die Größenbetrachtung das "+1" in den (3x+1)-Schritten ignorieren. Auch den Fehler, den man dadurch macht, muss man sich genauer anschauen, ist aber durch die Größe der betrachteten Zahlen so klein, dass man ihn nachher auch durch das epsilon "erschlagen" kann. Statt mit 3 wird ja real mit (3+1/x)< (3+10^(-20)) multipliziert, sodass die Abweichung sich ut kontrollieren lässt.) Damit lassen sich also auch die weiteren Folgenglieder, zum Teil deutlich größer als T abschätzen, sodass deren Reziproken also deutlich besser nach oben als nur 1/T abgeschätzt werden können und entsprechend auch der Durchschnitt dieser Reziproken.

Beispiel 1: Sei x == 3 (mod 4), also x = 4k+3. Dann wissen wir, dass die nächsten Folgenglieder 12k+10 "=" 3x und 6k+5 "=" 3/2 x lauten. (Korrekterweise rechnet man leicht nach, dass anstatt "=" hier immer ein >= gesetzt werden kann. Aber der relative Fehler ist für Werte von x der Größenordnung, die wir betrachten, eben recht klein.) Der Wert 6k+5 ist ungerade, d.h., wir haben die nächste ungerade Zahl gefunden. Und da x >= T galt, ist nun dieser Wert ">=" 3/2 * T. Damit sind die Reziproken dieser beiden ungeraden Folgenglieder "<=" 1/T und 2/3 * 1/T, d.h. ihr Durchschnitt ist " <= " (1 + 2/3)/2 * 1/T = 5/6 * 1/T.

Beispiel 2: Sei x == 1 (mod 4), also x = 4k+1. Dann sind die nächsten Folgenglieder 12k+4 "=" 3x --> 6k+2 "=" 3/2 x --> 3k+1 "=" 3/4 x. Da aber mit x auch alle seine Folgeglieder Teil des Zykluses sind, muss auch 3k+1 "=" 3/4 x >= T sein. Also ist in diesem Fall x ">=" 4/3 T und sein Reziproke "<=" 3/4 * 1/T. (Hier sieht man, dass man auf die Fehler, die durch das weggelassene "+1" durchaus schauen muss. Aber, wie gesagt, sie sind recht klein: Der relative Fehler wird nie größer als 10^(-16), was nachher dann leicht durch das epsilon abgedeckt wird.)

*) Wir wissen aber nach Annahme nicht nur, dass kein Folgenglied im Zyklus <= T ist, sondern auch, dass kein Folgenglied im Zyklus aus einer Zahl <= T entstehen kann (da sonst diese Zahl in den Zyklus münden würde, was ausgeschlossen war).

Beispiel 3: Ist x=3k+2 Teil des Zykluses, dann muss wegen 2k+1 --> 6k+4 --> 3k+2 der Wert 2k+1 "=" 2/3 x auch schon > T gewesen sein, d.h. x ">=" 3/2 * T.

*) Wir betrachten ja x mod 2^128. Für viele Restklassen ist allein schon der kleinste positive Repräsentant, d.h. der kleinste Wert, den ein x in dieser Restklasse annehmen kann, deutlich größer als T, sodass sich hier eine deutlich bessere Abschätzung für x (und dann damit auch die folgenden Folgenglieder) treffen lässt.


Diese Beobachtungen befähigen uns nun für jede [!] ungerade Restklasse modulo 2^128 zu zeigen, dass ein Anfangsstück (mit höchstens 128 ungeraden Folgengliedern) existiert, sodass der Durchschnitt der Reziproken der ungeraden Folgenglieder < (1-epsilon) * 1/limit ist.

Natürlich betrachten wir dabei nicht alle 2^127 > 10^38 möglichen Restklassen einzeln. Wenn beispielsweise für eine Restklasse res<2^8 ein Anfangsstück aus 8 Folgengliedern ausreicht, damit der Durchschnitt der Reziproken der darin enthaltenen ungeraden Folgenglieder unter den gewünschten Wert rutscht, dann gilt das auch für alle anderen Restklassen, die kongruent res mod 2^8 sind, denn nur die niedrigsten 8 Bit bestimmen, wie die nächsten 8 Schritte (Halbierung vs. (3x+1)) aussehen; und jede andere Restklasse, die kongruent res mod 2^8 ist, ist höchstens größer.

Konkret wird also eine Baum-Struktur betrachtet, die in jedem Bit verzweigt, ob eine Null oder Eins vorn angehangen werden soll. Dabei wird natürlich nur dann der entsprechende Unterfall aufgerufen, wenn nicht schon ein geeignetes Anfangsstück für diese Restklasse gefunden wurde, die das gewünschte Ergebnis (genügend kleiner Durchschnitt der Reziproken der ungeraden Folgenglieder) liefert.

Durch dieses Vorgehen wird der Baum so sehr beschnitten, dass anstatt 10^38 im aktuellen durchlauf nur ca. 16*10^9 Rekursionsaufrufe nötig waren. (Auf meinem Rechner hat das ca. 2h gedauert.)

(Genauer gesagt hat das Programm natürlich etwas leicht anderes gesucht, nämlich einen Vorfaktor val, sodass für jede Restklasse der Durchschnitt der Reziproken der ungeraden Folgenglieder <= val * 1/T ist. Gefunden wurde val < 0,5844, was genügt, um auch < 1/limit zu sein, da val < T/limit.)

Der Vollständigkeit halber noch ein paar wenige Bemerkungen zum Quellcode, den ich gleich auch angebe:

*) Um den Bau möglichst gut zu beschneiden, startet das Programm schon mit einer Abschätzung des zu erwartenden Ergebniswerts val (, der im Quelltext max_min_mean heißt). Wird auf einem Pfad im Baum ein größerer Wert gefunden, dann heißt dies, dass eben nicht alle Restklassen auf einen Wert <= der anfangs gedachten Schätzung hinauslaufen, sondern eben indestens der eine einen größeren Wert liefert (was für uns eigentlich schlecht ist). Aber, kein Problem: Wir aktualisieren einfach unsere Schätzung. Der dann gefundene größte Wert wird am Ende schließlich ausgegeben.

Wird kein größerer Wert gefunden, so war unsere Schätzung schon ein gültiger Wert im obigen Sinne, d.h., wir können dies einsetzen.

*) Jedoch wurde, um die Laufzeit zu verbessern, dann doch nur dann verzweigt, wenn der bisher gefundene beste "Anfangsstück-Durchschnitt" >= 1,001 * bisherigem Maximum war. Das bedeutet, dass Restklassen, die um maximal 1 Promille größer waren als der aktuelle Maximal-Wert, nicht weiter untersucht wurden. Dadurch können wir also nicht mehr ausschließen, dass es Restklassen gibt, die einen um maximal den Faktor 1,001 größeren Wert als dem gefundenen Maximum besitzen. Drum muss am Ende dann, damit wir eine sichere Abschätzung haben, noch mit diesem Wert von 1,001 multipliziert werden:

Gestartet wurde die Rechnung mit der Schätzung max_min_mean = 0,5843; es wurde kein größerer Wert gefunden, wobei eben nicht weiter untersucht wurde, wenn der für eine Restklasse vorliegende Wert eines Anfangsstücks schon < 1,001 * diesem Wert war. Also können wir "nur" garantieren, dass für jede Restklasse ein Anfangsstück existiert, auf dem der Durchschnitt der Reziproken der ungeraden Folgenglieder < 0,5844 * 1/T ist.

*) Und abschließend: Da 3^80 die ggrößte Dreierpotenz ist, die in einen 128-Bit-Integer passt, musste für größere Iterationen die Variable coef, die beim Übergang a*2^k + b --> ... ---> a * 3^g(b) + f(b) den Koeffizienten von a speichert, angepasst werden. Diese Variable ist deshalb wichtig, da das Anhängen einer führenden 1 an die Restklasse sich dadurch auswirkt, dass in der entsprechenden Collatz-Iteration dieses Werts einfach dann der Wert coef ( = 3^g(b) ) addiert werden muss. Also sind insbesondere die niedrig-wertigen Bits von coef interessant, da sie die Parität des aktuellen (und der folgenden) Folgenglieder beeinflussen. Deshalb wurde, beginnend mit der 76.sten Iteration (gemeint ist Halbierung, da in dem Code jeweils gleich "(3x+1)/2-Schritte" ausgeführt werden), der Wert coef nur noch modulo 2^75 bestimmt, sodass die folgenden weiteren 75 Iterationen noch korrekt verzweigen. Spätestens nach 150 Iterationen wäre auf diese Weise jedoch Schluss.

Bei den sonstigen 128-Bit-Ganzzahlen passiert zum Glück nichts Böses: Die Variable start, die die gerade betrachtete Restklasse angibt, wird nur sukzessive von hinten nach vorn mit Bits befüllt, aber in diesem Durchlauf nie mit mehr als 128. Und bei der Variable path, die die aktuelle Collatz-Iteration der Restklasse anzeigt, kann es zwar zu einem Überlauf kommen, der aber netterweise (dadurch, dass hier nur Additionen stattfinden) mod 2^128 reduziert wird, d.h. analog unsere wichtigen niedrig-wertigen Bits beschützt. Aber spätestens nach 80+128 Iterationen wäre der Fehler auch an die Stelle des "Einer-Bits" gewandert, d.h., hier wäre Schluss.

Dass die Ganzzahl-Versionen der Variablen hier ab der 76.sten Iteration nicht mehr notwendigerweise mehr mit den wahren Parametern gefüllt sind, stört aber nicht: Sie dienen ja sowieso nur dazu, darüber zu entscheiden, ob im nächten Zug eine Halbierung, oder ein (3x+1)-Schritt plus eine Halbierung durchgeführt werden muss. Und dazu brauchen sie nur die letzten Bits. Die "Größenordnung" (die wichtig für die Abschätzungen, für die wir uns ja interessieren, sind) der entsprechenden Werte findet sich jeweils in den Gleitkomma-
Variablen, z.B. coef_f. Und dort gibt es ja kein Problem (bei unseren betrachteten Zahlbereichen) mit Überläufen...


So, abschließend noch der Quellcode:
  1. #include "stdio.h"
  2. #include "math.h"
  3.  
  4. const unsigned int depth = 128;
  5.  
  6. // =0.585683 at depth = 125
  7. // >0.5843 at depth = 128
  8. double max_min_mean = 0.5843;
  9. unsigned __int128 maxclass;
  10. unsigned __int128 nodes = 0;
  11.  
  12. // = best found max_min_mean * 2.16891 * 10^20
  13. const double maxvalue = 1.2703e+20;
  14.  
  15. void printf_128(const unsigned __int128 nr) {
  16.  
  17. unsigned __int128 path = nr;
  18. // Ausgabe int128 im Dezimalformat
  19. // jeweils 6 Ziffern durch Kommata getrennt
  20.  
  21. int ziffer[42];
  22. int cnt = 0;
  23. int loop;
  24.  
  25. while (path>0)
  26. {
  27. ziffer[cnt]=path%10;
  28. path=path/10;
  29. cnt++;
  30. }
  31.  
  32. for (loop=cnt-1;loop>=0;loop--)
  33. {
  34. printf("%i",ziffer[loop]);
  35. if ( (loop%6==0) && (loop>0) )
  36. printf(",");
  37. }
  38. }
  39.  
  40.  
  41. double corfactor(const unsigned int odd, const unsigned __int128 it_rest)
  42. {
  43. double factor = 1;
  44.  
  45. if ((it_rest % 3 == 2) && (odd >= 1))
  46. factor *= 2.0/3; //2k+1 --> 3k+2
  47.  
  48. if (odd >= 2)
  49. {
  50. if (it_rest % 9 == 8)
  51. factor *= 2.0/3; //4k+3 --> 9k+8
  52.  
  53. if (it_rest % 9 == 4)
  54. factor *= 8.0/9; //8k+3 --> 9k+4
  55.  
  56. if (odd >= 3)
  57. {
  58. switch(it_rest % 27)
  59. {
  60. case 13: factor *= 2.0/3; break; //16k+7 --> 27k+13
  61. case 20: factor *= 8.0/9; break; //16k+11 --> 27k+20
  62. case 26: factor *= 2.0/3; break; // 8k+7 --> 27k+26
  63. }
  64. }
  65. }
  66.  
  67. return factor;
  68. }
  69.  
  70. void iteration(const unsigned int nr_it, const unsigned __int128 start,
  71. const unsigned __int128 path, const unsigned __int128 coef,
  72. const double coef_f, const unsigned int odd,
  73. const double sum, const double min_f, const double min_mean)
  74. {
  75. nodes++;
  76. if (nr_it < depth)
  77. {
  78. double mean;
  79. double cor_min;
  80.  
  81. //additional 0 bit before "start" value and next iteration
  82. unsigned __int128 new_start = start;
  83. unsigned __int128 new_path = path;
  84. unsigned __int128 new_coef = coef;
  85. double new_coef_f = coef_f;
  86. unsigned int new_odd = odd;
  87. double new_sum = sum;
  88. double new_min_f = min_f;
  89. double new_min_mean = min_mean;
  90.  
  91. if (new_path % 2 == 0)
  92. {
  93. new_path = new_path >> 1;
  94. new_coef_f /= 2;
  95. cor_min = new_coef_f * corfactor(new_odd, new_path);
  96. if (cor_min < new_min_f)
  97. {
  98. new_min_f = cor_min;
  99. mean = new_sum * new_min_f / new_odd;
  100. if (mean < new_min_mean)
  101. new_min_mean = mean;
  102. }
  103. }
  104. else
  105. {
  106. new_sum += (1.0 / new_coef_f);
  107. new_odd++;
  108. mean = new_sum * new_min_f / new_odd;
  109. if (mean < new_min_mean)
  110. new_min_mean = mean;
  111.  
  112. new_path += (new_path >> 1) + 1;
  113. if (nr_it >= 75)
  114. {
  115. new_coef = new_coef & (((unsigned __int128) 1 << 75) - 1);
  116. }
  117. new_coef *= 3;
  118. new_coef_f *= 3.0/2.0;
  119. }
  120.  
  121. //smallest number in the chain/ its predecessors relative to maxvalue
  122. double minvalue = ((double) new_start) * new_min_f / maxvalue;
  123. if (minvalue < 1.0)
  124. minvalue = 1.0;
  125.  
  126.  
  127. if (new_min_mean / minvalue >= max_min_mean * 1.0001)
  128. {
  129. iteration(nr_it+1, new_start, new_path, new_coef, new_coef_f,
  130. new_odd, new_sum, new_min_f, new_min_mean);
  131.  
  132. }
  133.  
  134.  
  135.  
  136. //additional 1 bit before "start" value and next iteration
  137. new_start = start + ( (unsigned __int128) 1 << nr_it);
  138. new_path = path + coef;
  139. new_coef = coef;
  140. new_coef_f = coef_f;
  141. new_odd = odd;
  142. new_sum = sum;
  143. new_min_f = min_f;
  144. new_min_mean = min_mean;
  145.  
  146. if (new_path % 2 == 0)
  147. {
  148. new_path = new_path >> 1;
  149. new_coef_f /= 2;
  150. cor_min = new_coef_f * corfactor(new_odd, new_path);
  151. if (cor_min < new_min_f)
  152. {
  153. new_min_f = cor_min;
  154. mean = new_sum * new_min_f / new_odd;
  155. if (mean < new_min_mean)
  156. new_min_mean = mean;
  157. }
  158. }
  159. else
  160. {
  161. new_sum += (1.0 / new_coef_f);
  162. new_odd++;
  163. mean = new_sum * new_min_f / new_odd;
  164. if (mean < new_min_mean)
  165. new_min_mean = mean;
  166.  
  167. new_path += (new_path >> 1) + 1;
  168. if (nr_it >= 75)
  169. {
  170. new_coef = new_coef & (((unsigned __int128) 1 << 75) - 1);
  171. }
  172. new_coef *= 3;
  173. new_coef_f *= 3.0/2.0;
  174. }
  175.  
  176. //smallest number in the chain/ its predecessors relative to maxvalue
  177. minvalue = ((double) new_start) * new_min_f / maxvalue;
  178. if (minvalue < 1.0)
  179. minvalue = 1.0;
  180.  
  181. if (new_min_mean / minvalue >= max_min_mean * 1.0001)
  182. {
  183. iteration(nr_it+1, new_start, new_path, new_coef, new_coef_f,
  184. new_odd, new_sum, new_min_f, new_min_mean);
  185.  
  186. }
  187. }
  188. else
  189. {
  190. if (min_mean > max_min_mean)
  191. {
  192. max_min_mean = min_mean;
  193. printf("bisheriger max_min_mean: %f.\n",max_min_mean);
  194. maxclass = start;
  195. }
  196. }
  197. }
  198.  
  199. void init()
  200. {
  201. iteration(1, 1, 2, 3, 3.0/2.0, 1, 1.0, 1.0, 1.0);
  202.  
  203. printf("Nach %d Iterationen ist das maximale", depth);
  204. printf("1 / harmonisches Mittel < %f.\n", max_min_mean * 1.0001);
  205. printf("erzeugende Restklasse de maximalen gefundenen 1/HM : ");
  206. printf_128(maxclass);
  207. printf("\n\n");
  208. printf("Anzahl betrachteter Rekursionsaufrufe: ");
  209. printf_128(nodes);
  210. printf("\n\n");
  211.  
  212. char s;
  213. scanf("%s",&s);
  214. }
  215.  
  216.  
  217. int main()
  218. {
  219. init();
  220.  
  221. return 0;
  222. }


Damit wäre dann alles Gewünschte bewiesen. ;)

Viele Grüße
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 5367
Aus: New York
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.89, eingetragen 2016-11-14 00:17


@ cyrix: Ich habe jetzt nur den Anfang gelesen. Unterscheidet sich dein Beweis(ansatz) von dem in Garner's kurzem 4-Seiten-Artikel "On the Collatz 3n + 1 algorithm" von 1981? (Notizbuch Link) Das war der erste Beweis für die Länge eines nicht-trivialen Zyklus.

Wo finde ich Informationen zur Kettenbruchentwicklung von log(3)/log(2)?


-----------------
Drei kleine Regeln, die dich sicher durchs Leben bringen. 1. Vertritt mich mal eben! 2. Oh, gute Idee, Chef! 3. Das war bestimmt jemand anders! (Homer Simpson)



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2004
Mitteilungen: 2388
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.90, eingetragen 2016-11-14 03:14


Hallo Slash,

soweit ich das sehe, unterscheidet sich die Idee des Beweises schon deutlich. Der Prototyp bzw. der eigentlich relevante Teil des Beweises, in dem die Theorie (insbesondere der Kettenbrüche) steckt, findet sich in diesem Paper von 1993:

www.sciencedirect.com/science/article/pii/0012365X9390052U

Was ich hier mache, ist eigentlich nur, unter einer gewissen Voraussetzung (nämlich die, dass für alle Zahlen <= 110*2^60 schon gezeigt wurde, dass sie nicht in einen nicht-trivialen Zyklus münden) das dort angegebene Theorem 2.1 etwas zu verschärfen (bzw. die schon dort angegebene Variante besser nutzbar zu machen).

Ich drehe also ein klein wenig an einem Parameter und zeige, dass die Rechenarbeit, die bis zum Erreichen des nächsten "tranisition points" (wo also ein Näherungsbruch der Kettenbruchentwicklung aus dem noch möglichen Intervall rausfällt und also der nächste jetzt die untere Schranke an die Anzahl Folgengliedern charakterisiert) nötig ist, nur etwa halb so groß ist, wie gedacht. (Wobei, wenn man etwas ehrlicher ist, und den auch dort schon gegebenen Hinweis nach dem Beweis von Theorem 2.1 berücksichtigt, nur noch der Faktor ca. 2/3 übrig bleibt...)

Das Ganze war eher eine nette Überlegung, die sich parallel aus dem in diesem Thread entstandenen Programmier-Objekt entwickelt hat. (Man wird viele gleiche Code-Teile in den beiden Programmen, an denen ich saß, finden. ;) )


Cyrix
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 5367
Aus: New York
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.91, eingetragen 2016-11-14 03:47


Danke cyrix!

Ich habe noch das hier gefunden: NEW LOWER BOUNDS FOR THE SIZE OF A NON-TRIVIAL LOOP IN THE COLLATZ 3X+1 AND GENERALIZED PX+Q PROBLEM

Dort steht: "Hence, if an alpha-loop exists we must have at least 1.387.806.137.299.329.586 odd numbers in that loop."

Das kann aber auch ein fehlerhafte Arbeit eines Amateurs sein.


@ all: Hier noch eine interessante Arbeit von Gottfried Helms von der Uni Kassel: Cycles in the Collatz-problem


-----------------
Drei kleine Regeln, die dich sicher durchs Leben bringen. 1. Vertritt mich mal eben! 2. Oh, gute Idee, Chef! 3. Das war bestimmt jemand anders! (Homer Simpson)



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2004
Mitteilungen: 2388
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.92, eingetragen 2016-11-14 05:51


@Slash: Deine zuerst zitierte Arbeit ist korrekt. Allerdings hast du den zweiten Fall übersehen: Er unterscheidet zwei Typen von Zyklen. Und im zweiten Fall kommt er "nur" auf eine Schranke von 6.586.818.670 ungeraden Folgengliedern, was interessanterweise genau dem auch auf dem anderen Weg erhaltenen Wert entspricht. (Nagut, beide untersuchen ja auch i.W. das Gleiche, nämlich, wie sehr sich Zweier-Potenzen und diese Produkte von Faktoren der Form (3+1/x) annähern können.)

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 5367
Aus: New York
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.93, eingetragen 2016-11-15 03:15


2016-11-14 00:17 - Slash in Beitrag No. 89 schreibt:
Wo finde ich Informationen zur Kettenbruchentwicklung von log(3)/log(2)?

Mit Cyrix' Hinweis auf das verlikte Paper in #90 möchte ich hier noch den zugehörigen OEIS Eintrag verlinken, den ich selbst zuvor nie gefunden hatte.

A028507 Continued fraction expansion for log_2(3)

Dies nur nebenbei: Ich bin nicht sicher, ob man es so formulieren sollte/kann, doch ein Beweis der Vermutung liegt wohl im Verständnis der Eigenschaften obiger Folge und dieser A022924 Number of 3^m between 2^n and 2^(n+1) Folge verborgen.

EDIT: Soeben neu bei arXiv reingesegelt: Additive Collatz Trajectories


-----------------
Drei kleine Regeln, die dich sicher durchs Leben bringen. 1. Vertritt mich mal eben! 2. Oh, gute Idee, Chef! 3. Das war bestimmt jemand anders! (Homer Simpson)



  Profil  Quote  Link auf diesen Beitrag Link
astrid-clz
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.10.2016
Mitteilungen: 21
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.94, eingetragen 2016-11-15 07:34


Guten Morgen :)

Heute werde ich auch mal Gelegenheit haben, nach und nach meinen aktuellen Stand zu posten. Ich bin dabei das Projekt "nachzuspielen". Mit der gonz'schen Version 6T, die aktuell bei mir auf 5x6 Kernen läuft (*), habe ich folgenden Stand erreicht entsprechend R. #74:

time=70:17:21s path_record[5323,048232,813247]=3,929460,878594,911451,658957,991888

dh mit ungefähr 3 Tagen Zeitdauer. Diesen Versuch werde ich zugunsten der aktuellen cyrix Version demnächst abbrechen (**).

(*) ich habe nun doch meinem Arbeitgeber ein wenig Rechenleistung abgeschwatzt, allerdings mir der Vorgabe, keine Verbindung "nach draussen" herzustellen. Ein Gestell mit Servern für Collatz_mp, das ich nach und nach auffüllen kann. Vielleicht können wir so etwas auch mal gemeinsam irgendwo realisieren, wo sie in Ruhe vor sich hinrechnen können und wir alle Zugriff haben, die Rechnerpreise an sich sind ja nicht so riesig aktuell und wir müssen keine identischen Maschinen haben. Vielleicht in Braunschweig, Wildemann oder...
 
(**) da ich zu faul war das ganze zu automatisieren muss ich die Programmteile für die einzelnen Maschinen von Hand einrichten, das macht einen spontanen Versionswechsel etwas mühselig.

[more to follow]
Astrid



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 16.08.2003
Mitteilungen: 2637
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.95, eingetragen 2016-11-15 08:15


fed-Code einblenden
bye trunx


-----------------
das problem des menschen ist nicht, dass er fleisch von tieren isst, sondern dass er für sein wachstum KRIEG gegen alle anderen lebensformen führt. dieser krieg nennt sich (land)wirtschaft, seine ideologische legitimation kultur.



  Profil  Quote  Link auf diesen Beitrag Link
astrid-clz
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.10.2016
Mitteilungen: 21
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.96, eingetragen 2016-11-15 09:38


2016-11-13 14:19 - matph in Beitrag No. 87 schreibt:
Auch klingt es fast so, als seien nicht alle Optimierungsflags wie -march=native, -funsafe-math-optimizations, -finite-math-only, -fno-trapping-math... gesetzt.
--
mfg
matph

Ich habe ein wenig mit den Compiler Optionen des gcc herumgespielt, -ffast-math z.B. bringt 6%, aber ich habe keine Kombination gefunden, die wirklich was Grösseres wegschafft. Hier wäre sicher noch Forschungsbedarf, ausgereizt habe ich da bestimmt noch nicht alles. Solange algorithmische Verbesserungen noch Faktoren erbringen, sollte man das vielleicht erst einmal zurückstellen, da die Wirksamkeit einzelner Schalter natürlich auch sehr vom konkreten Code abhängen dürften. Dasselbe gilt für das händische Nachoptimieren auf asm Ebene.




  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2004
Mitteilungen: 2388
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.97, eingetragen 2016-11-16 00:37


@Astrid: Das sieht doch schon mal gut aus. :)

Leider komme ich in den nächsten ein bis zwei Wochen eher nicht dazu, an diesem Projekt weiterzuarbeiten. (Irgendwie rückt die Abgabe der Diss. näher, und die sollte dann doch vorgehen. ;) )

Deshalb nur kurz aus Konsistenz-Gründen den Quelltext der Version aus Beitag #81 zum Download.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
gaussmath
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.06.2007
Mitteilungen: 9023
Aus: Hannover
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.98, eingetragen 2016-11-16 11:11


2016-10-25 10:58 - blindmessenger in Beitrag No. 19 schreibt:
Ich würde sagen der Matheplanet sollte mal für eine gtx1080 zusammenlegen... Dann könnten wir noch ganz andere Sachen berechnen... Ich würde die Karte dann auch bei mir verwahren...  biggrin
Und beim nächsten Treffen können wir dann virtuelle Realität genießen. .. cool

Hallo zusammen!

Na ja, Wunder erwarten kann man damit aber nicht. Die IPC einer 1080 GTX liegt im 32bit Integer Bereich bei ca. 3 TIOP/s. Eine aktuelle Intel CPU hat ungefähr 1/10 Leistung davon. Für FP32 sieht das ganz anders aus. Eine 1080 GTX wartet mit brachialen 10 TFLOP/s auf. Allerdings ist wiederum 64bit Integer im Vergleich zu 32bit relativ langsam, weil es nativ gar nicht unterstützt wird.

Ich beschäftige mich zur Zeit mit CUDA und suche nach interessanten Projekten. Falls jemand dieses Verfahren hier in CUDA C implementieren will, dann mache ich gerne mit. Ich habe allerdings nur eine 970 GTX zu Hause in Betrieb...

Grüße, Marc



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2004
Mitteilungen: 2388
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.99, eingetragen 2016-11-16 12:24


Hm, ich habe mal noch etwas nachgedacht, ohne mich gleich wieder an den Rechner zum Programmieren zu setzen. (Meine Priorität gilt auch derzeit eher meiner Diss... ;) ) Folgende Überlegung:

Es scheint so zu sein, dass nur etwa je die Hälfte bis ein Drittel aller Kandidaten einen solchen 13er-Sammelschritt, wie wir ihn gerade in der "inneren Schleife" (der Collatz-Methode) durchführen, überleben. Zumindest die nächsten 4 sind nur abhängig von den letzten 4*13=52 Bit des aktuellen Werts. D.h., den müssen wir gar nicht sooo genau kennen, sondern können eigentlich "lokal", für diese nächsten 4 Sammelschritte mit nur 64-Bit-Arithmetik arbeiten, solang dies uns auf jeden Fall die Exaktheit der letzten 52 Bit garantiert. (Natürlich müssen wir nebenbei die "absolute Größe" schon korrekt mit den passenden double-Variablen mitführen.) Wenn wir durch diese Größenabschätzung der Gleitkomma-Varianten der Zahlen wissen, dass die Stoppzeit erreicht wurde, aber kein neuer Rekord, dann brauchen wir dafür nicht eine 128-Bit-Operation anwenden. Sollte der Kandidat dagegen doch überleben (was aber nur auf < 10% zutreffen sollte), dann müssen wir eben doch alles, was wir gerade nur näherungsweise berechnet haben, exakt nachrechnen, damit wir wieder fr die nächsten Iterationen garantieren können, dass wir die korrekten Bits betrachten.

Dies führt zu eine Mehraufwand für die überlebenden Kandidaten (nämlich einmal die Rechnung mod 2^64, dann noch einmal richtig mod 2^128), dafür aber zu einer Vereinfachung für alle anderen, die in der Zeit ihre Stoppzeit erreichen (wahrscheinlich wohl >90%), wo nun 64-Bit-Operationen ausreichen...

Dies umzusetzen, also die Collatz-Methode entsprechend umzustricken, kann man ja mal überlegen. Ich werde allerdings, wie gesagt, erst einmal zumindest nicht in den nächsten zwei Wochen dazu kommen.



@gaussmath: Wahrscheinlich wird es am Ende eben genau Collatz-Methode sein, von der ich meine, dass man sie auf eine GPU portieren kann. Inhaltlich passiert da nicht viel: Außer ein paar Gleitkomma-Operationen, die i.W. nichts kosten, wird - abhängig von den letzten x Bits einer Zahl - mit dem Inhalt einer bestimmten Array-Zelle multipliziert. Ja, das sind (in Zukunft zumindest nur noch zum Teil) 128-Bit-Integer-Operationen; aber auch dies sollte tendenziell machbar sein, siehe z.B.  diese Bemerkung auf Stackoverflow.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
astrid-clz
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.10.2016
Mitteilungen: 21
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.100, eingetragen 2016-11-16 13:31


@cyrix
Dann los! Erst die Arbeit, dann das Vergnügen!

@cyrix &gauss
wir haben doch keine Eile damit... ich wäre inzwischen auch recht gespannt etwas mit cuda zu machen (auch wenn ich völlig unbeleckt bin in diesen dingen) aber ich habe eine passende GraKa im Rechner. Also... Lasst es uns als längerfristiges Projekt sehen, dann bin ich dabei :)

Grüsse
Astrid



  Profil  Quote  Link auf diesen Beitrag Link
astrid-clz
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.10.2016
Mitteilungen: 21
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.101, eingetragen 2016-11-17 09:18


Sooooo
einen guten Morgen in die Runde!

Ich habe jetzt die "aus-Beitrag-81" Version von cyrix am Start (ich finde es toll dass hier so offen mit dem Quelltext umgegangen wird!)

eingefügt ein
C
#define __int64 long long

liess sich das Ganze unter gcc (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3 problemfrei compilieren.

Es ist nach ersten kurzen Versuchen um einen Faktor > 5 schneller als die Version col_6T die ich bisher am Start hatte. Es läuft aktuell bei mir als single-Thread Version, der Faktor gegenüber der parallelisierten 6T ist entsprechend nur berechnet. Es würde aber glaube ich einfach wieder an denselben stellen zu parallelisieren sein, die fork sind ja nur auskommentiert.

Demnächst dann also mehr :)

einen schönen Tag
Astrid


Nachtrag:

wir haben aktuell ja folgende Möglichkeiten weiterzukommen (... wenn ich einen Antrag schreiben müsste würde ich erwähnen...)

Jetzt so:
- allgemeine Theorie (slash, trunx)
- algorithmische verbesserungen (cyrix, amateur)
- Parallelisierung auf Basis CPU: Multithreaded, mehrere Server (gonz,astrid)

In Arbeit:
- Compileroptimierung / Nachoptimierung Maschinencode (matph,astrid)
- komplette Lösung in Assemblercode für zentrale Routinen (juergen)

Man könnte auch:
- Server etc. für ein Projekt verteilten Rechnens auf CPU (brauchen wir das noch? dann: gonz und/oder astrid! gonz hat server mit Webzugang am Start. wo steckt der eigentlich?)
- GPU/Cuda (gaussmath et. al., ich wäre auch dabei)
- FPGA (mit Aufwand verbunden, ist da jemand wirklich dran interessiert?)

PS.: Vielleicht keine gute Idee da Namen dranzuschreiben, es sollte sich bitte niemand übergangen fühlen, dies ist ja ein Gemeinschaftsprojekt des mp. ich bin da eben nur so... manchmal auf dem orga-trip ... Lasst es euch also nicht verdriessen. vielleicht starten wir ja mal ne umfrage nach dem motto - collatz quo vadis?

Nu aber wirklich genug, Hund jault und ich bin raus an die frische äh kalte luft... bis später und so



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 16.08.2003
Mitteilungen: 2637
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.102, eingetragen 2016-11-17 10:53


@astrid: zuviel der ehre, ich denke cyrix liefert mehr beiträge zur allgemeinen theorie als ich. ich lese hier ja nur mit und mein fokus ist auch ein bisschen anders: ich bin weniger an pathrecords sondern mehr an den bedingungen für nichttriviale loops interessiert. daher meine beschäftigung mit dem rückwärtsrechnen oder den 2*3^k restklassen (neben den 2^k restklassen) und der berechnung von weiteren approximationen von fed-Code einblenden
(hier habe ich bei meiner oben geposteten rekursion a(k)=k ermittelt. immerhin)

bye trunx


-----------------
das problem des menschen ist nicht, dass er fleisch von tieren isst, sondern dass er für sein wachstum KRIEG gegen alle anderen lebensformen führt. dieser krieg nennt sich (land)wirtschaft, seine ideologische legitimation kultur.



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2004
Mitteilungen: 2388
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.103, eingetragen 2016-11-17 13:04


@astrid: Na das sieht doch schon gut aus. :)

Was den Code angeht: Da wir hier zusammenarbeiten und nicht gegeneinander, und es auch nicht ums Geldverdienen o.Ä. geht, sehe ich keinen Grund, hier irgendwelche Informationen geheim zu halten. ;)

Zur Parallelisierung auf mehrere Threads: Hier würde ich tatsächlich den Vorschlag von matph favorisieren, dies der OpenMP-Library zu überlassen. In der derzeitigen, von gonz initierten, low-level-Variante, dass man jedem Thread eigenhändig zuweist, welche Restklasse[n] er bearbeiten soll, läuft man in das Problem, dass alle Threads darauf warten müssen, dass auch der letzte alle seineihm fest zugewiesenen Restklassen abgearbeitet hat. Parallelisiert man mit OpenMP, dann werden die Restklassen dynamisch zur Laufzeit auf die Threads verteilt, sodass dies besser ausbalanciert werden kann.

@trunx: Die Pathrecords sind für mich auch nur ein nettes Beiwerk. ;) Interessanter finde ich es, wenn wir -- mittels Rechnerunterstützung -- ein neues Ergebnis zeigen können. Dafür ist aber der einfachste Weg (s.o.), dass wir den Zahlenraum bis 110*2^60 abgrasen. Und dafür müssen wir algorithmisch noch ein bisschen schneller werden, als wir derzeit noch sind. ;)

Was die rationalen Näherungen an log(3)/log(2) angeht: Hast du dich mal mit dem Thema der Kettenbrüche beschäftigt? Man kann die Näherungsbrüche sehr leicht rekursiv bestimmen; und das ohne herumprobieren zu müssen.


So viel in der Kürze von mir. Einen schönen Tag euch noch :)
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 16.08.2003
Mitteilungen: 2637
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.104, eingetragen 2016-11-17 16:58


hi cyrix,
ja, ich bin ein wenig mit kettenbrüchen vertraut :)
und nein, ich probiere nicht nur so rum, sondern berechne tatsächlich den kettenbruch :D
und habe da auch schon ca. 10.000 kettengliedern (sprich ich kann die oben angeg. oeis-folge bestätigen). ich programmiere in php mit bcadd() usw. aber es dauert halt auch, deshalb hatte ich nachgefragt, weil ich da auch gern optimieren würde.
aber, ich bin trdm ganz ohr, woran dachtest du bei der ermittlung des kettenbruchs? :)
dir (und euch) auch nen schönen abend
trunx


-----------------
das problem des menschen ist nicht, dass er fleisch von tieren isst, sondern dass er für sein wachstum KRIEG gegen alle anderen lebensformen führt. dieser krieg nennt sich (land)wirtschaft, seine ideologische legitimation kultur.



  Profil  Quote  Link auf diesen Beitrag Link
astrid-clz
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.10.2016
Mitteilungen: 21
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.105, eingetragen 2016-11-18 13:16


Guten Morgen :)

time=28:12:12s path_record[406,738920,960667]=25601,393410,042456,822885,239364

Bis zur #70, singlethreaded, "etwas mehr als ein Tag".

openmp gefällt mir, bin dabei mir das anzugucken. sicher etwas was lohnt sich mal reinzuknien. Wird aber noch nen Weilchen dauern bis ich da Ergebnisse habe (kein problem wenn jemand anders schneller ist).






  Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 5367
Aus: New York
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.106, eingetragen 2016-11-18 14:10


Hier mal eine Filter-Idee: Mir ist aufgefallen, dass die Folgenglieder der Path-Records oft in der Nähe späterer Path-Records liegen. Also nur Startzahlen für die Suche verwenden, die in der Nähe* dieser Folgenglieder liegen. *Dieser Nah-Bereich wird natürlich auch zunehmend größer. Natürlich auch nur die Startzahlen nutzen, die die ersten Restklassenfilter bestehen.

Man wird so wohl nicht jeden Path-Record finden, aber mit wachsenden Zahlen einige wohl schneller. Vielleicht hat jemand Lust das mal zu testen, ist ja schnell programmiert. Man sollte wohl die ersten 10-20 Path-Record-Folgenglieder als Anfangswerte vorgegeben, obwohl die 27er-Folge auch schon einige gute Startzahlen liefert.

Bsp.: C(27) besitzt die Folgenglieder 445, 251, 638 und 1822. Diese liegen sehr nah an den späteren Path-Record-Startzahlen 447, 255, 639 und 1819. Das Gesetz der kleinen Zahlen werkelt auch hier, klar. wink Aber dieses Verhalten lässt sich auch bei größeren Zahlen beobachten. Einen Test ist es wohl wert.


-----------------
Drei kleine Regeln, die dich sicher durchs Leben bringen. 1. Vertritt mich mal eben! 2. Oh, gute Idee, Chef! 3. Das war bestimmt jemand anders! (Homer Simpson)



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: im letzten Quartal
Dabei seit: 16.08.2003
Mitteilungen: 2637
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.107, eingetragen 2016-11-18 15:02


hallo :)
ich schreibe mal meine gedanken zu nichttrivialen loops auf, ansatzpunkt ist, dass nur zahlen der form 12k+7 als startwerte dafür in frage kommen.
fed-Code einblenden
soweit zur einfachsten form nichttrivialer zyklen.

bye trunx

[Die Antwort wurde nach Beitrag No.105 begonnen.]


-----------------
das problem des menschen ist nicht, dass er fleisch von tieren isst, sondern dass er für sein wachstum KRIEG gegen alle anderen lebensformen führt. dieser krieg nennt sich (land)wirtschaft, seine ideologische legitimation kultur.



  Profil  Quote  Link auf diesen Beitrag Link
Amateur
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.10.2012
Mitteilungen: 771
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.108, eingetragen 2016-11-19 03:54


Hallo,

hiermit werfe ich mal ein Minimalbeispiel zur Parallelisierung mit OpenMP in die Runde. Es basiert auf dem ursprünglichen Programm von gonz mit der Abbruchbedingung von cyrix und der inneren Schleife aus Beitrag #32.
Damit keine Rekorde verloren gehen, ist die Zeile  path_record = path;  in der Collatz-Funktion auskommentiert. Folglich werden auch Ergebnisse ausgegeben, die keine Rekorde sind. Eine anschließende Säuberung der Ergebnisliste würde jedoch keine nennenswerte Rechenzeit beanspruchen.

C
#include <omp.h> 
 
int main()
{
        k1=(12327829503/32)*32;   //ab hier prüfen
        k2=k1+10708000000;        //bis hierher
        path_record=INT64_MAX;    //größte int64-Zahl
 
        //optional Anzahl der Threads fest vorgeben 
        //omp_set_num_threads(4);
        #pragma omp parallel for 
        for (k=k1; k<=k2 ; k+=32) {
                collatz(k+7);
                collatz(k+15);
                collatz(k+27);
                collatz(k+31);
        }
}


Das Programm habe ich mit  gcc -O3 -fopenmp  übersetzt. Gerechnet wird im Bereich R#46 bis R#47. Nun, es funktioniert, wobei die Skalierung verbesserungswürdig ist. Aber da geht noch was.

Viele Grüße A.



  Profil  Quote  Link auf diesen Beitrag Link
astrid-clz
Wenig Aktiv Letzter Besuch: vor mehr als 3 Monaten
Dabei seit: 06.10.2016
Mitteilungen: 21
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.109, eingetragen 2016-11-19 08:17


Guten Morgen :)

Neuer Tag, neues Spiel, neues Glück ...
Single Threaded, aktuelle Version (cyrix)

#71 : time=42:34:18s path_record[613,450176,662511]=45762,883485,945724,291985,239552

Machen wir die aktuelle Jahresendprognose (die ich hier einfach deshalb poste, damit jemand der mag nachrechnet, ich vertue mich zu gerne bei so etwas lacht):

42 Stunden sind 1.75 Tage

Erreichbare Faktoren:
Rechenzeit: 40 Tage
Kerne: 30

Damit erzielbar gegenüber #71:
1200/1.75 = 685
und damit irgendwo zwischen #82 (dies ggf auch weihnachten schmunzel) und #83

dh wir müssen (nein wir müssen natürlich nicht, aber wir könnten versuchen... ) irgendwie noch einen faktor von gefühlt 3-5 herauszuknautschen, den wir nicht durch zeit oder rechenleistung "erschlagen" wollen, damit es weiter spass macht. das ginge m.E. auch durch assembleroptiomierung, erscheint jedenfalls auf Basis einer multithreaded-CPU Lösung erreichbar.

Anfeuernd guck

(gilt nicht für cyrix wegen diss abgabe)

@amateur
danke für das beispiel :)

@slash
Da lässt sich sicherlich was machen, wir speichern allerdings die folgen ja aktuell gar nicht ab, sodass man da "von vorne anfangen" müsste oder sich die startwerte für die path records aus den log files zusammenklauben müsste um damit dann weiterzugucken. da man dadurch eine sehr begrenzte anzahl von möglichen startwerten bekäme (also zB im Bereich von 10^5, aus 70 startwerten jeweils die +-10 Umgebung von zB 10 Folgegliedern die in Frage kommen) könnte man diese locker durchrechnen lassen. Wenn man dabei eine merkliche anzahl von pathrecords im höheren wertebereich reproduzieren könnte, wäre das schon signifikant (wobei ich persönlich es nicht erwarte, aber das zählt nicht). es könnte ein abfallprodukt des path-record-logs-mit-zu-vielen-kandidaten-die-gar-keine-sind programms sein, das ja auch noch fertig gemacht werden will * schmunzel



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1845
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.110, eingetragen 2016-11-19 19:57


Zum gcc assembler:

Ich realisiere 3 * xmm1+1 durch:

"mov $1,%r14 \n\t"
"movq %r14,%xmm8 \n\t"   // low quadword of xmm8 = 1
"movq %xmm1,%xmm2 \n\t" // xmm1 retten nach xmm2
"PSLLQ $1,%xmm2 \n\t" // xmm1 * 2 nach xmm2 !                          
"paddq %xmm2,%xmm1 \n\t" // xmm2+xmm1 nach xmm1, also 3 mal xmm1
"paddq %xmm8,%xmm1 \n\t" // 3 * xmm1+1 nach xmm1
"movntdq %xmm1, test_12 \n\t"  // Endwert direct in C-Variable,

Leider versagt das PSLLQ an der 64 bit-Grenze und behandelt bit 64 als sign bit des lower quadwords, setzt auch keine flags wie zero, carry, overflow.
Bleibt evtl noch:

"VPSLLVQ xmm1, xmm2, xmm3"

Was das  macht ist "Variable Bit Shift Left Logical".
Wer das versteht bitte mich zu kontaktieren ;)
Wohl auch nur auf core i7 Prozessoren. Mit SSE4 extension.

Ein "shift left 128-Bit integer" gibt es anscheinend nicht.
Der Pentium ist eben eine eierlegende Wollmilchsau. Mehr auf floating point ausgerichtet.
Man muss ein workaround machen an dem ich grad arbeite. Wenn jemand ne Idee hat?
Am besten wär an sich ein Risc prozessor.
Mit der GPU hab ich noch nicht gearbeitet, würde mich sehr reizen.
Bin dankbar für Erfahrungen und Beispielprogramme mit Cuda.
Jürgen








  Profil  Quote  Link auf diesen Beitrag Link
Amateur
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 01.10.2012
Mitteilungen: 771
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.111, eingetragen 2016-11-19 23:50


Hallo,

als Ergänzung zu Beitrag #108 möchte ich noch die soeben ermittelten Meßwerte nachreichen:

Minimalbeispiel
Bereich von R#46 bis R#47
Intel-i5 (4 Kerne)

Threads   Zeit/s   Speedup
   1       84        1.0
   2       42        2.0
   3       29        2.9
   4       23        3.7

Ich denke, das sieht brauchbar aus. Und ein paar Stellschrauben gibt ja auch noch. Bin optimistisch.
Bis später!
 
Viele Grüße A.



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2528
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.112, vom Themenstarter, eingetragen 2016-11-20 10:57


Einen schönen Sonntag allerseits :)

Aus dem Urlaub zurück :) habe ich doch erst einmal die fork's wieder hineingenommen in die aktuelle Version. Nachdem wir uns mit den Kernen aufgeteilt haben 36 (Astrid) + 12 (gonz) komme ich für meinen Teil in einer Stunde bis zur #70. Das ist natürlich nett weil man quasi zusehen kann. Danach wird es dann mühselig, dass wir damit zum Jahresende bei der #82 ungefähr wären passt zu dem was ich hier sehe. Ich würd also auch sehen, dass wir irgendwie versuchen noch was herauszuholen was entweder den Algorithmus betrifft oder doch ggf. mal nen bissl was in Assembler Optimierung.

Ich habe als Drittmeinung auch zu hören bekommen, dass die 128bit Kommandos auf den Intel CPU für unsere Zwecke nicht wirklich brauchbar sind, dh die Empfehlung wäre mit mehreren 64bit Registern zu arbeiten. Aber auch damit wäre ggf. ja einiges herauszuholen.

gonz

PS.: Ich lasse das natürlich jetzt so laufen, und damit wäre morgen zu erwarten dass wir - für unser projekt hier - Neuland erreichen und so bis zur #76 vorstossen...

Nachtrag:

time=11:36:27s path_record[5328,396584,901375]=3,776710,469297,359472,914462,467496

Damit ist die #74 erreicht :) die zufällig zu den von mir bearbeiteten Resten gehört (ich hatte vorher nicht geschaut welche da passen und welche nicht).

Gegenüber der Messung von Astrid aus Beitrag No.94 ist damit sogar ein Faktor von über 6 erreicht.

Zweiter Nachtrag:

wie erwartet heute also Roosendaal #76 erreicht (ich habe offenbar mit der Auswahl der Kerne Glück)

time=23:23:32s path_record[10709,980568,908647]=350,589187,937078,188831,873920,282244

Und damit wird es 4-5 Tage dauern bis wieder ein Treffer ansteht...


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



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2004
Mitteilungen: 2388
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.113, eingetragen 2016-11-20 12:27


2016-11-20 10:57 - gonz in Beitrag No. 112 schreibt:

Ich habe als Drittmeinung auch zu hören bekommen, dass die 128bit Kommandos auf den Intel CPU für unsere Zwecke nicht wirklich brauchbar sind, dh die Empfehlung wäre mit mehreren 64bit Registern zu arbeiten.

Dann sollte man das machen, denn wir haben wirklich nur recht einfache 128-Bit-Operationen:

*) Vergleich --> trivial
*) Addition --> sehr einfach
*) Bitshifts --> auch sehr einfach
*) Multiplikation mit einem 64-Bit- uint:
da intern wohl sowieso bei der Multiplikation zweier 64-Bit-uints sowohl das highword der oberen 64-Bits des Produkts und dsa lowword der unteren 64-Bits berechnet, aber nur der zweite Teil zurückgegeben wird, wäre man hier sehr schnell, wenn man per Assembler auch an diesen "Übertrag" herankommen würde. Der Rest ist dann trivial...

Die einzige Baustelle, die ich gerade bei diesem Vorhaben, den nativen 128-Bit-uint-Datentyp zu ersetzen durch eine eigene Implementierung, sehe, ist die Umwandlung in eine Dezimalzahl (da dort dann mod-Operationen auftauchen). Aber dieser Programmteil wird genügend selten gebraucht, dass man hier auch wieder den unterstützen Datentyp verwenden und in diesen die Daten des eigenen hineinschreiben kann.


Cyrix

p.s.: Das heißt für mich, dass ich (wenn ich vielleicht irgendwann nächste Woche dazu komme) mich eher auf die Idee, vor dem Aufruf der Collatz-Methode noch stärker zu sieben, konzentrieren werde. Denn die Idee, möglichst viele 128-Bit-Multiplikationen durch einen Workaround mit 64-Bit-Näherungen zu sparen, wird durch das eben geschilderte Vorgehen dann obsolet.



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: im letzten Monat
Dabei seit: 31.07.2004
Mitteilungen: 2388
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.114, eingetragen 2016-11-21 05:18


Da wir ja nun doch schon ein gutes Stück die Geschwindigkeit der suche gesteigert haben, eine kurze Überlegung zum Ziel bzw. Umfang, was man hier erreichen kann:

Als durchaus realistisches Ziel halte ich, dass wir den Bereich mit Startzahlen bis 2^67, ca. 10^20 absuchen. Warum gerade diese Schwelle? Nun, wenn man das schafft, könnte man daraus eine Veröffentlichung machen, wo man einerseits über die algorithmischen Ideen erzählt und andererseits das Ergebnis der Verschräfung, wie lang ein nicht-trivialer Zyklus ist, erhält. (Ein neuer Pathrecord allein wird sicherlich kaum die entsprechende "Interessantheits-Schwelle" überschreiten, insbesondere dann, wenn nicht mal lückenlos gesucht hat, also nicht klar ist, ob es denn überhaupt einer ist, da kleinere Startzahlen, die man nicht überprüft hätte, größere Werte liefern könnten...)

Was bedeutet das für einen Rechenaufwand? Nun, derzeit scannen wir einen Bereich von ca. etwas über 10^13/(h * Kern). Das heißt, mit der derzeitigen Performance bräuchten wir für das hier von mir ausgegebene Ziel ca. 10^7 Kern-Stunden.

Ich bin guter Dinge, dass wir durch tieferes Sieben vor dem ersten Aufruf der Collatz-Methode und durch eine eigene, maschinennahe Implentierung der von uns benötigten einfachen 128-Bit-Integer-Operationen zusammen noch einmal einen Faktor 10 in der Zeit herausholen können. Dann wären wir bei noch ca. 10^6 benötigten Kern-Stunden.

Bei ca. 100 Kernen wäre damit die Laufzeit auf nur noch ca. 10^4 Stunden, also etwa ein Jahr, gesunken. Und das ist eine Größenordnung, die mir machbar erscheint.

Dazu müsste man sich aber schon noch etwas (so viel sind 100 Kerne ja nun nicht) Rechenleistung von außen holen...


Viele Grüße
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2528
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.115, vom Themenstarter, eingetragen 2016-11-21 09:22


Moin cyrix,

das klingt doch nach einem guten plan. Damit wären Startwerte>64 Bit und Pathrecords mit >128 Bit zu verarbeiten. Das passt aber ganz gut zu unserem Plan, mit n*64 Bit zu arbeiten.

In Sachen Hardware bereitstellen: Wenn wir auf der mehrfach-CPU Schiene bleiben (was ja nicht ausschliesst, parallel GPU oder FPGA zu anzugehen, einfach weil es zB für mich erstrebenswertes neuland wäre), könnte man das Ganze entweder irgendwo hosten (Astrid sprach schon von einem Gestell, und es würden dann ja um die 20 Server benötigt, die man gut irgendwo unterbringen könnte) oder wir arbeiten mit verteilten Servern und verbinden sie via Web (oder macht beides - ein zentraler Server der die Aufgaben verteilt und die Ergebnisse sampelt wäre in beiden Fällen ja gut zu haben. Bei verteiltem Arbeiten bräuchten wir halt eine Handvoll Leute, die jeweils so um dir 20 kerne, also 5x4 oder 3x6 beispielsweise stellen).

Wenn man sich für das Hosting "irgendwo zentral" entscheidet, würde das fast danach klingen, dass es ein prima Projekt/Praktikum für angehende Fachinformatiker handelt. Ich könnte mal mit meiner Chefin sprechen ob sie nen Schreibtisch und die Stromrechnung sponsort * feix

Eigentlich gefällt mir ein gemischtes Modell am besten, ich würde als dann mal meinen Schwerpunkt drauf legen wirklich einen zentralen Server aufzusetzen und eine Schnittstelle zu schaffen für den Datenabgleich. Da wir wenig Daten senden (Reste bzw. Wertebereich zum Client, gefundene Kandidaten für path records und keep alive messages in Richtung Client->Server) brauchen wir da eigentlich nicht auf performance zu achten. an sich würde ich sowas (alter vermittlungstechniker der ich bin) einfach in UDP oder TCP/IP einpacken, bin aber auch gerne aufgeschlossen wenn wir da auf irgendeinem Transportprotokoll aufsetzen wollen (XML, SOAP, whatever). Das hätte den Vorteil, dass sich dann "jemand" problemfrei um eine Client Implementierung für die Windows Welt kümmern könnte, was nicht so mein Ding ist.

(nun ist es doch ein langes post geworden, ich wollte eigentlich nur cyrix zuwinken und was zu den <64bit sagen)

Ach ja: wenn wir nicht zentral rechnen und damit alles unter kontrolle haben, würde ich einen faktor 2 einplanen wollen, um jedes ergebnis das von einem client "irgendwo" kommt andersweitig nachzurechenen, also jedes paket 2mal zu vergeben ...

Einen schönen Tag wünscht
gonz


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



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2528
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.116, vom Themenstarter, eingetragen 2016-11-27 09:38


Nummero #77

time=109:14:04s path_record[49163,256101,584231]=603,506208,138015,336516,148529,351572

Etwas verspätet da ich die letzten Tage andersweitig beschäftigt war. wo steckt eigentlich Astrid?

Einen schönen Adventssonntag wünscht

gonz


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



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2528
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.117, vom Themenstarter, eingetragen 2016-11-28 11:25


Nummero #78

time=185:48:10s path_record[82450,591202,377887]=1751,225500,192396,394150,998842,490900


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



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2528
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.118, vom Themenstarter, eingetragen 2016-11-28 11:40


So das Server-Client Modell hat auch Form angenommen.

Basis für den Client wird bei mir das C Programm "Bauart Cyrix". Dieses meldet sich über eine TCP/IP basierte Schnittstelle beim Server an und erhält von diesem einen Startwert zugeteilt. Es sendet dann regelmäßig an den Server ein Lebenszeichen und/oder gefundene Candidate Records. Der Server speichert dieses in einer Datenbank, und kann auch ggf. einen neuen Startwert zuweisen, wenn ein bereits anderen Clients zugeteilter Wert erreicht wurde. Die Schnittstelle halte ich in ASCII over TCP/IP menschenlesbar, sodass sie mit einem normalen Terminalprogramm ausgetestet werden kann. Da wir noch keine parallelisierte Version haben, bzw. daran noch gearbeitet wird, muss man das Programm dann eben wenn mehrere Kerne zur Verfügung stehen mehrfach starten. Ich werd die Netzwerkanbindung im Client erstmal für Linux machen, da findet sich dann ja ggf. jemand, der das "für die Windows Welt" machen kann. Des weiteren wird es erstmal keine Verifizierung der Ergebnisse geben, da wir uns ja in einem goodwill-Umfeld bewegen und auch gegen Roosendaal testen können. Um den Zugriff etwas einzuschränken werde ich Kennungen vergeben, die man hier auf dem mp via PN austauschen kann, sodass nur autorisierte Nutzer mit Clients an den Start gehen können.

Soweit? Dann wäre das mein Arbeitsprogramm für die nächsten Tage.

mit besten Grüssen
und frohes Schaffen in der neuen Woche!

gonz


PS.: Astrid schrieb mir, dass sie im Krankenhaus ist - und internetfreie Zeit nimmt bzw. nehmen muss.




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



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2528
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.119, vom Themenstarter, eingetragen 2016-11-30 10:31



Als durchaus realistisches Ziel halte ich, dass wir den Bereich mit Startzahlen bis 2^67, ca. 10^20 absuchen.

Aktuell sind wir (wobei ich den Status bei Astrid aktuell nicht kenne) mit 48 Kernen am Start und schaffen damit ziemlich genau einen Bereich von 10^16 pro Tag. An #79 ist mein Server "vorbeigerauscht", im Dezember sind damit noch die Werte 80..82 in Reichweite.


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



  Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 3Gehe zur Seite: 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8  
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]