Die Mathe-Redaktion - 30.03.2017 10:41 - Registrieren/Login
Auswahl
Schwarzes Brett
Fragensteller hat Anwort gelesen, aber bisher nicht weiter reagiert2017-03-29 23:35 bb
MPCT 2017 Planung
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 Feb. 2017

Für Mitglieder
Mathematisch für Anfänger
Wer ist Online
Aktuell sind 544 Gäste und 25 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 6   [1 2 3 4 5 6 7 8]   8 Seiten
Autor
Kein bestimmter Bereich Die Collatz-Folge programmieren
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2591
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.200, eingetragen 2016-12-29 22:07


hi, zu den rückwärtsiterationen:
2016-12-24 20:09 - cyrix in Beitrag No. 161 schreibt:

2k+1 --> 3k+2

4k+3 --> 9k+8
8k+3 --> 9k+4

16k+7  --> 27k+13
16k+11 --> 27k+20
 8k+7  --> 27k+26

64k+7 --> 81k+10
32k+7 --> 81k+20
32k+15--> 81k+40
64k+55--> 81k+71
64k+59--> 81k+76
16k+15--> 81k+80

128k+ 39 --> 243k+ 76
128k+ 47 --> 243k+ 91
 64k+ 27 --> 243k+107
 64k+  1 --> 243k+121
128k+ 71 --> 243k+137
 64k+ 39 --> 243k+152
128k+ 91 --> 243k+175
 64k+ 47 --> 243k+182
128k+121 --> 243k+233
128k+123 --> 243k+236
 32k+ 31 --> 243k+242
die meisten der genannten reste sind 2mod3 (zb. 8mod9, 20mod27 usw.) desweiteren gibt es etliche reste 4mod9 (zb. 13mod27, 40mod81 usw.) und auch 10mod81 kommt vor (91mod243). all diese reste brauchen nicht berücksichtigt werden, sd. nur noch
2mod3
4mod9
10mod81
433,604mod729 (aus 303,423mod512)
usw. bleiben.

EDIT: es ändern sich natürlich die vergleichsverhältnisse, insofern sind diese reste vllt doch nicht unnütz.


-----------------
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: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2328
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.201, eingetragen 2016-12-29 22:29


@trunx: Genau, die Vergleichswerte ändern sich. Insofern macht es schon einen Unterschied, ob ich die Berechnung für eine Startzahl x abbrechen kann, wenn ich ein Folgenglied == 2 (mod 3), dass kleiner ist als 3/2 x ist, gefunden habe; oder auch schon, wenn es sogar == 8 (mod 9) ist, dafür aber nur kleiner als 9/4 x sein muss.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 20.04.2013
Mitteilungen: 109
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.202, eingetragen 2016-12-31 11:56


2016-12-28 21:15 - cyrix in Beitrag No. 189 schreibt:

-1.: Sieb der Restklassen mod 2^32. Diese werden "herausgeschrieben" und können so zur Parallelisierung auf mehrere Threads und auch über verschiedene Rechner verteilt werden.

0.: Jede dieser Restklassen wird intern, innerhalb eines CPU-Threads weiter bis etwa 2^50 vorgesiebt.

1. Abhängig von einer vorgegebenen Startzahl (Vielfaches von 2^60) werden nun für jede dieser Restklassen mod 2^50 für die Startwerte "Startzahl + i * 2^50 + Restklasse", i= 0 bis 1023 entweder direkt, oder schon ihre gerade berechneten 50. Iterationen an die GPU übergeben. (Letzteres ist bezügl. der Berechnung effektiver, da da die Berechnung der 50. Iteration ja schon implizit erfolgt ist; aber bezügl. der Kommunikation via BUS teurer, da mehr Daten transferiert werden müssen.) Dort werden die nächsten 32 oder 64 Schritte für diese konkreten Startwerte näherungsweise und hochgradig parallel berechnet. Zurückgemeldet an die CPU wird, bei welchen - wenigen - Startzahlen eine genauere Berechnung von Nöten ist.


zu 1.
wenn Du schreibst "entweder direkt oder schon ihre gerade berechneten 50. Iterationen", heißt das doch, das für jeden Startwert schon 50 Iterationen durchgeführt wurden, bevor die GPUs überhaüpt zum Einsatz kommen?

Sollte man nicht gerade die ersten Iterationen möglichst parallelisiert ausführen (mit dem zusätzlichen Vorteil, dass man von 1024 Startwerten nur den ersten übergeben muss, die restlichen Startwerte kann sich die GPU selber berechnen und man nicht von 1024 Startwerten 50 Iterationen verschenken muss?

eben nachgerechnet:
log(319391343969356241864419199325107352/2^68)/log(1.51000) = 84.00122844921479013097
log(319391343969356241864419199325107352/2^68)/log(1.50100) = 85.23769379462913975583
log(319391343969356241864419199325107352/2^68)/log(1.50010) = 85.36376005096275547547
log(319391343969356241864419199325107352/2^68)/log(1.50001) = 85.36376005096275547547
Man könnte also zunächst bis zu 85 Iterationen auf den GPUs laufen lassen (ohne dass man auf einen neuen Rekordwert prüfen müsste), bevor man eine Folge mit der CPU anfasst?




 



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2328
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.203, eingetragen 2016-12-31 13:01


Das Ergebnis der ersten Iterationen erhält man aus dem Sieb-Prozess quasi geschenkt. Warum also erneut durchühren?

edit: Die derzeit 32. (später vlt. 50.) Iterationen der 1024 auf einmal auf einer GPU berechneten Startwerte haben weiterhin die Form einer arithmetischen Folge, eben weil wir sie aus jeweils genau einer Restklasse k * 2^32 + rest wählen, von der wir wissen, dass ihre 32. Iteration dann die Form k * Koeffizient + Absolutglied hat. Zu übertragen wäre dann nur das Intervall, in welchem sich k bewegen soll, der Koeffizient und das Absolutglied.

btw: Es sollte auch möglich sein, die Kosten des Datentransfers zu "verbergen", indem man diesen parallel zur Berechnung der vorhergehenden "Serie an Startwerten" durchführt. Aber da kenne ich mich nicht genügend aus...

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2449
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.204, vom Themenstarter, eingetragen 2016-12-31 16:22


Liebe Freunde der Collatz-Folge :)

So ich hab noch ne idee *(1)

siebe bauen sollte ja zeit sparen gegenüber dem stumpfen durchrechnen. das problem an "grossen" sieben (gross im sinne der bittiefe) ist dann eigentlich nur, dass man den platz braucht, um alle reste zu speichern. wie nun, wenn wir schrittweise vorgehen, dh mit einem kleinen sieb anfangen, und dann jeweils nur für einen rest weiter sieben
so zB

bestimme für 2^10 die zu betrachtenden reste
und speichere sie (platzbedarf < n*1k byte)
schnappe dir einen dieser reste
    bestimme für diesen rest die nächsten 2^10 schritte
    platzbedarf weitere < n*1k byte
    nimm dir einen der reste
         bestimme....
       
der gesamtspeicherbedarf wächst damit nur noch ungefähr linear mit der bitzahl, und von der laufzeit sollte es egal sein, in welcher reihenfolge ich was rechne...

wenn keinem nen grober schnitzer in dem plan auffällt würd ichs mal angehen auf die art.

einen guten weg ins neue jahr wünscht
gonz

*(1) wobei ich mich grad frage ob ihr das nicht eh schon so gemeint hattet und ich nur nicht auf den trichter gekommen bin)


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



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1818
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.205, eingetragen 2016-12-31 20:45


2016-12-29 19:26 - cyrix in Beitrag No. 198 schreibt:
@Rückwärtsiterationen:
Wir wissen ja, dass aus 2k+1 man in eine Schritt zu 3k+2 gelangt.
Ein Rückwärtsschritt besteht also nun in der Erkenntnis, dass, sollte in der Collatz-Folge für einen Startwert x irgendwann ein Element y auftauchen,
dass == 2 (mod 3) und < 3/2 * x ist, dessen weitere Berechnung abgebrochen werden kann: Es existiert dann nämlich ein Collatz-Vorgänger z von y, der kleiner als x ist.

Wieso wissen wir das hab ich was uebersehen...?
habe ausprobiert bis: Nachfolger von
<math>2015 = 2*1007+1 = 3023 \rightarrow 3*1007+2 = 3023 > 3/2 * 2015 </math>.

Der Vorgänger 2015 ist kleiner als der Nachfolger 3023 wie bei jeder OE Aktion aber es ist nicht <math>3023 < 3/2 * 2015</math>. Die nächsten wären 9070, 4535.
Wir kommen hier aus 3k+2 in eine einfache 2er -Potenz, aber das machts nicht kleiner. Bis ich mal nachrechnete:
Logisch, denn es  kann nicht

<math>\displaystyle\frac{3*(2k+1)+1}{2} = 3k+2 < \frac{3}{2}\cdot(2k+1)
= \frac{6k+3}{2} = 3k + \frac{3}{2}</math> sein, sei k gerade oder ungerade. oder?

Dass 3k+2 abgebrochen werden kann unter o.a Bedingungen hab ich nicht verstanden. Weil die nicht eintreten.
Ist das aus dem Beitrag 88 von cyrix gefolgt? confused

Thx



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2328
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.206, eingetragen 2016-12-31 21:56


@Jürgen: Wenn du 3k+2=3023 setzt, dann ist ein Collatz-Vorgänger dieser Zahl offenbar 2k+1=2015. Und genau deshalb kann man die Berechnung für alle Startzahlen x, auf deren Berechnungspfad irgendwann 3023 auftaucht, dann abbrechen, wenn x > 2015 ist, weil dann der nachfolgende Teil schon für die Startzahl 2015 berechnet wurde.

Formulieren wir es allgemeiner: Hat man auf einer Berechnung x --> ... ---> 3k+2=:y, so kann man abbrechen, wenn man 2k+1 < x ist, also insbesondere erst recht, wenn man 2/3 y = 2k + 4/3 < x hat, was äquivalent zu y < 3/2 x ist.

edit: Zahlenwerte im ersten Paragraphen angepasst, da ich deinen Beitrag zuerst bezüglich dieser falsch gelesen hatte.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 2943
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.207, eingetragen 2016-12-31 22:21


@Juergen007

Hier noch ein konkretes Beispiel, anhand dessen man das imho sehr gut verstehen kann. Die Collatzfolge für 155 sieht so aus

155, 233, 350, 175, 263, 395, 593, 890, 445, 668, 334, 167, 251, 377, 566, 283, 425, 638, 319, 479, 719, 1079, 1619, 2429, 3644, 1822, 911, 1367, 2051, 3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122,...

d.h., es dauert relativ lange, bis mit 122 erstmals die Startzahl 155 unterschritten wird. Aber schon bei 167=3*55+2, also viel, viel früher, kann man aufhören, da diese Zahl unmittelbarer Nachfolger von 111(=2*55+1) ist und ein eventueller path-record daher schon bei 111 gefunden worden wäre.



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2328
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.208, eingetragen 2016-12-31 22:25


@Gonz: Dein Vorgehen sollte funktionieren. Wobei du natürlich immer nur die Restklasen abspeichern musst, die noch nicht ausgesiebt wurden.

Olivera e Silva hat in seinem Rekord-Lauf vor ein paar Jahren deshalb gar nichts bezügl. dieser Werte zwischengespeichert, sondern dann die jeweilige Restklasse "on the fly" untersucht: Er hat bis Bit 48 vorgesiebt und dann jeweils 2^10 Startwerte in dieser Restklasse untersucht, sodass er in jedem Durchlauf einen Bereich von 2^58 abgedeckt hat. Insgesamt bestand seine Berechnung dann aus 20 solchen Durchläufen...

Das Einzige, was man hier dann wirklich machen muss, ist, eine ordentliche Verwaltung von Path-Record-Kandidaten durchführen.

Cyrix

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



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1818
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.209, eingetragen 2016-12-31 22:29


2016-12-31 21:56 - cyrix in Beitrag No. 206 schreibt:

Formulieren wir es allgemeiner: Hat man auf einer Berechnung x --> ... ---> 3k+2=:y, so kann man abbrechen, wenn man 2k+1 < x ist, also insbesondere erst recht, wenn man 2/3 y = 2k + 4/3 < x hat, was äquivalent zu y < 3/2 x ist.

edit: Zahlenwerte im ersten Paragraphen angepasst, da ich deinen Beitrag zuerst bezüglich dieser falsch gelesen hatte.

Cyrix

Ja danke, ich muss das mal nachrechnen, aber dieses Jahr nicht mehr ;)
Happy New Year Dir und allen die ich kenn, Jonas, Gonz, Goswin & son, Buri Martin und den mit dem Jupiter Teleskop, und wessi90, Epsilonkugel, Annakath, Bernhardt , ... etc fallen jetzt nicht alle ein :) Und allen anderen auch:)
Merry Glühwein!!

Jürgen


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



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2449
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.210, vom Themenstarter, eingetragen 2017-01-01 11:03


Guten Morgen und willkommen in 2017 :)

2016-12-29 22:07 - trunx in Beitrag No. 200 schreibt:
hi, zu den rückwärtsiterationen:
[...]
2mod3
4mod9
10mod81
433,604mod729 (aus 303,423mod512)

Bezogen auf die Verwendung für den Filter, bevor man überhaupt in die Folgen einsteigt, hilft folgende Betrachtung:
3^1 : 33%
3^2 : weitere 11%
3^3 : keine verbesserung
3^4 : weitere 1,2%

Zum Vergleich bringt der Schritt von 2^17 auf 2^18 ebenfalls 1,2%, allerdings bei einer einfachen Verdoppelung der Basis.

Wie man die mitlaufende Prüfung auf 3-er Reste theoretisch machen kann, ist mir klar, aber ich habe noch keinen Weg gefunden, das wirklich effizient zu programmieren.

Beste Grüsse aus dem Harz
gonz


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



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2328
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.211, eingetragen 2017-01-01 11:19


@gonz: Du beziehst dich immer nur auf eine Überprüfung der Startwerte. Der Spaß bringt deutlich mehr, insbesondere auch höhere Verbesserungsraten, wenn man diese Aussagen aus den Rückwärts-Iterationen auch bei späteren Folgengliedern anwendet. (Und da gehören alle obigen Werte dazu, nicht nur die, die trunx genannt hat. Warum, hatte ich im darauf folgenden Beitrag ja schon dargestellt.)

Deshalb war ich ja auch verwundert, dass plötzlich grob ein Drittel der Restklassen mod 2^32 aussortiert wurden, als ich das Rückwärts-Sieb von mod 3^3 auf mod 3^5 erweitert habe...

Und das Schöne dabei ist: Die Basis verändert sich nicht, denn der Koeffizient der meisten Folgenglieder ist ja durch 3 (und dann später höhere Dreierpotenzen) teilbar, nämlich alle nach dem ersten (3x+1)-Schritt; was bei uns der erste ist, da wir nur ungerade Restklassen betrachten müssen.

Cyrix



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


Ahaaa :)
Denkfehler erkannt. Danke cyrix :)


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



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2328
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.213, eingetragen 2017-01-01 11:34


2017-01-01 11:03 - gonz in Beitrag No. 210 schreibt:
Guten Morgen und willkommen in 2017 :)
Wie man die mitlaufende Prüfung auf 3-er Reste theoretisch machen kann, ist mir klar, aber ich habe noch keinen Weg gefunden, das wirklich effizient zu programmieren.

Die Methode corfactor in dem von mir geschriebenen Teil des Quelltextes acht genau das, was du hier suchst:

Sie bekommt die aktuelle Restklasse entgegen sowie die Anzahl odd, wie viele (3x+1)-Schritte bei der Berechnung bisher schon vorgekomen sind. Letzteres bedeutet, dass der Modul der Restklasse jetzt genau durch 3^odd teilbar ist (und evtl. als weiteren Faktor noch eine Zweierpotenz enthält, der hier aber nicht von Bedeutung ist).

Beispiel:

Man hat 4k+3 --> 6k+5 -->  9k+8. Beim Aufruf der Methode corfactor für 4k+3 wäre odd=0, für 6k+5 gleich 1 und für 9k+8 gleich 2.

(Aufgerufen wird sie hier real allerdings nie, da sie immer nur nach einem x/2-Schritt benötigt wird, weil das Ziel ist, einen möglichst kleinen Vorgänger zu finden...)

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
weird
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.10.2009
Mitteilungen: 2943
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.214, eingetragen 2017-01-01 11:35


2017-01-01 11:25 - gonz in Beitrag No. 212 schreibt:
Ahaaa smile
Denkfehler erkannt. Danke cyrix smile

Eigentlich habe ich ja das Beispiel in #207 für juergen007 angegeben, aber ich denke auch für dich wäre es sehr instruktiv gewesen.  wink

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



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2449
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.215, vom Themenstarter, eingetragen 2017-01-01 11:47


@weird :
:)

@cyrix
"Die Methode corfactor in dem von mir geschriebenen Teil des Quelltextes acht genau das, was du hier suchst:"

D.h. ich kann mir auf Basis deines Programms etwas bauen, was unterwegs die Reste herausschreibt, und das als Input für mein "brute force" assembler Programm nehmen, sprich eine passende reste.h Datei erzeugt. Mal gucken wie weit ich damit komme :) Bei meinem alten Ansatz für das Generieren der Filter ist eh Schluss, da ich unter PHP nicht so einfach über 2^18 hinauskomme.

Dass ich an dieser Assemblerroutine immer noch schraube bringt uns natürlich insgesamt nicht weiter, da es im Ergebnis langsamer ist als das was wir schon haben. Aber ich bin da noch am Erkenntnisse sammeln und werd noch ein bisschen daran herumforschen.

Was ja auch noch ansteht ist der Record-Sortierer, ich hab aktuell zwei Modelle im Kopf, um diesen mit den worker-threads zu verbinden, entweder über shares memory oder über eine TCP Verbindung. Ggf. baue ich beides und aufrufkompatibel zum Einbinden in beliebige C Programme...

soweit der Plan :)


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



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1818
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.216, eingetragen 2017-01-02 22:18


2016-12-31 22:21 - weird in Beitrag No. 207 schreibt:
@Juergen007

Hier noch ein konkretes Beispiel, anhand dessen man das imho sehr gut verstehen kann. Die Collatzfolge für 155 sieht so aus

155, 233, 350, 175, 263, 395, 593, 890, 445, 668, 334, 167, 251, 377, 566, 283, 425, 638, 319, 479, 719, 1079, 1619, 2429, 3644, 1822, 911, 1367, 2051, 3077, 4616, 2308, 1154, 577, 866, 433, 650, 325, 488, 244, 122,...

d.h., es dauert relativ lange, bis mit 122 erstmals die Startzahl 155 unterschritten wird. Aber schon bei 167=3*55+2, also viel, viel früher, kann man aufhören, da diese Zahl unmittelbarer Nachfolger von 111(=2*55+1) ist und ein eventueller path-record daher schon bei 111 gefunden worden wäre.

Ja nochmal danke, das war eine echt gut verständliche Erklärung. Die 3x+2 Zahlen können ja kaum 3y+1 Zahlen sein.
Deswegen könnte man nach jeder beendeten Halbierungssequenz, die ja lang werden können, im Extremfall 341,1024,,,,,,,,1.(schlechtes Beipiel gg) so ein "mod-3-check" machen.
Die Anzahl der auszuführenden Halbierungen weiss man vorher z.B.durch trailing zero count. Danach zum Aufstöbern eines 3x+2 Frühabbruchs den "mod-3-check", ich denke der Aufwand lohnt.
Eine Division durch 3 ist auf-128 bit-mikrocode ohne divq register1,register2  gar nicht trivial.
Habe noch keinen optimalen Ablauf nur mit logischen Befehlen and or xor shl shr jc,jz etc. gefunden, das parity bit bietet einen guten  Ansatzpunkt.
Eine div r1,r2 Division erfordert ca. 20 Zyklen bei 64/64 bit.
siehe auch:
www.mikrocontroller.net/topic/413678?goto=4815738#4847963

Gruß
Jürgen




  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2328
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.217, eingetragen 2017-01-03 01:20


@Jürgen: Um zu testen, ob ein Collatz-Folgenglied kongruent 2 (mod 3) ist, reicht es zu schauen, wie oft es seit der letzten 3x+1-Operation halbiert wurde: Ungeradzahlig oft, dann ja; geradzahlig oft, dann nein.

Allerdings muss man, um abbrechen zu können, darüber hinaus noch haben, dass das aktuelle Folgenglied < 3/2 * Startzahl ist.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1818
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.218, eingetragen 2017-01-04 22:24


2017-01-03 01:20 - cyrix in Beitrag No. 217 schreibt:
@Jürgen: Um zu testen, ob ein Collatz-Folgenglied kongruent 2 (mod 3) ist, reicht es zu schauen, wie oft es seit der letzten 3x+1-Operation halbiert wurde: Ungeradzahlig oft, dann ja; geradzahlig oft, dann nein.

Allerdings muss man, um abbrechen zu können, darüber hinaus noch haben, dass das aktuelle Folgenglied < 3/2 * Startzahl ist.

Cyrix

jo thx :)
Einige echt gute Ideen für rest 2 mod 3  für x86 durch Abzählen der geraden und ungeraden Bits usw. fand ich noch unter
www.mikrocontroller.net/topic/413678?goto=4829284#4848901

Das werden sicher einige der MPler  mitverfolgen wenn nicht empfehle ich es:) Einige schreiben da ja auch.
Frohes Dinx und Bums (mainly Bums)






  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2449
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.219, vom Themenstarter, eingetragen 2017-01-05 07:40


Guten Morgen :)

Nachdem ich nun hoffentlich verstanden habe, was Sache ist :) und nichts doppelt machen will, entnehme ich die vorgesiebten Reste dem Programm von cyrix (20 Mio Reste nach 2^32) zusammen mit dem jeweils neuen Basiswert und dem Rest der sich nach den ersten 32 Schritten ergibt.

Dadurch dass ich die ersten 32 Schritte nicht neu berechne ergibt sich eine Laufzeitverbesserung von ca. Faktor 2, dh ich brauche für einen Rest bis zur 64Bit Grenze des Startwertes um die 5 Min (das streut natürlich sehr in abhängigkeit vom konkret behandelten Rest), das heisst wir brauchen für ein Programm das ggf. den nächsten Record "jenseits" der Roosendaal Liste finden kann, ca. 70.000 KernTage, was noch deutlich zu viel ist, anpeilen bzw. zur Verfügung haben wir aktuell 60 Kerne * 100 Tage, es fehlt also immer noch ein Faktor von 10.

Ideen diesen Faktor noch zu gewinnen sind:
- das steppen über alle startwerte für einen Rest vom C-Programm mit in die asm Routine verlagern,
- das vorgeschaltete sieb nochmal verfeinern

Jedenfalls scheint es soweit sinnvoll zu sein, damit konkrete Vorbereitungen für verteiltes Rechnen auf Basis von cpu Kernen zu treffen. Astrid schlug vor, die Reste in eine mysql Datenbank einzupflegen (einfach indem wir eine Variante des cyrix Programms bauen, die eine entsprechende sql input Datei erzeugt) und über einen in C geschriebenen Server zu verteilen, wobei wir ein Format basierend auf XML über TCP/IP verwenden würden, sodass jeder auch mit eigenen Clients herumexperimentieren kann.

Soweit
wünsche ich einen schönen Tag

gonz


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



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 20.04.2013
Mitteilungen: 109
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.220, eingetragen 2017-01-05 14:49


2017-01-05 07:40 - gonz in Beitrag No. 219 schreibt:
zur Verfügung haben wir aktuell 60 Kerne * 100 Tage, es fehlt also immer noch ein Faktor von 10.

Wenn ich den aktuellen Softwarestand korrekt interpretiere, kann die den "Großen Haufen" recht gut sieben und es gibt gedankliche Ansätze, den Rest, der durchfällt, auf viele GPU-Kerne zu verteilen.

Da typischerweise sehr viel mehr GPU-Kerne als CPU-Kerne zur Verfügung stehen (ich vermute mal, dass die Hardware mit den 60 Kernen nebenbei auch wenigstens 1000 GPU-Kerne bereit hält), sollte man mal vielleicht ein paar Gedanken darüber verschwenden, mit welchen Techniken man u.U. den "Großen Haufen" mit den GPUs sieben und das, was durchfällt, dann mit den CPUs beackern kann - ich hab' den Eindruck, dass da der gesuchte Faktor 10 drin sein könnte!?



  Profil  Quote  Link auf diesen Beitrag Link
astrid-clz
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 06.10.2016
Mitteilungen: 21
Aus:
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.221, eingetragen 2017-01-05 16:30


Hallo dlchnr,

im prinzip hast du recht und ich glaube auch dass der Weg mit GPU zu arbeiten der richtige ist. die rechner die ich am start haben sind jedoch "abgezweigte" Server in einem Rechenzentrum, die über ssh/terminalprogramm angesprochen werden und von haus aus keine (oder nur eine standard) GraKa haben, also "blind" sind.

Es wäre aber sicherlich möglich, da mal zu gucken, wer in seinem heimischen rechner eine passende graka hat. wir wollen ja eigentlich auch etwas höher hinaus und uns (von cyrix vorgeschlagen) am liebsten noch bis 67 bit also nochmal um faktor 8 weiter hinaufarbeiten.

Einen weiteren filter vorzuschalten könnte gut gehen, denn wir hätten auf der festplatte natürlich platz für mehr als die 20 Mio jetzt bearbeiteten reste, und auch ggf. tagelang zeit, um ein vorgeschaltetes sieb laufen zu lassen. wenn man feststellt, dass dieses vorgeschaltete sieb recht lange braucht könnte man sogar die schon gefundenen reste abarbeiten, während "vorne" noch weiter gesiebt wird. Es sollte dann ggf. reichen, nochmal um 2^10 weiter vorzusieben, damit wären wir unter 20 Mrd Reste (was noch irgendwie handhabbar ist) und hätten ggf. den gewünschten Faktor schon gewonnen...

liebe grüsse aus dem verschneiten oberharz
Astrid



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2449
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.222, vom Themenstarter, eingetragen 2017-01-06 08:41


2017-01-05 16:30 - astrid-clz in Beitrag No. 221 schreibt:
Wenn man feststellt, dass dieses vorgeschaltete sieb recht lange braucht könnte man sogar die schon gefundenen reste abarbeiten, während "vorne" noch weiter gesiebt wird.

dann können wir doch sortieren, und zwar nach der Anzahl der in den ersten 32 Schritten vorkommenden 3-er Faktoren.

Werte, bei denen dieser gering ist, haben gute chancen, dass sie bei weiterem Sieben eine merkliche verbesserung erzielen,

Werte, bei denen dieser hoch ist, können ohne weitere zeit zu verlieren sofort in die verteilte Reste-Nachbereitung geworfen werden.

gonz



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



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2328
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.223, eingetragen 2017-01-08 11:03


So, ich habe mal etwas gebastelt und das angesprochene tiefergehende Sieb geschrieben. Die schlechte Nachricht vorweg: Die "Verbesserung" auf ca. 20 Millionen (von 30) Restklassen mod 2^32 entstand aufgrund eines Programmierfehlers; real ist es nur eine auf ca. 29 Millionen.

Jetzt die gute Nachricht:
Anteil übrigbleibender Restklassen beim Sieben bis Iteration x : f(x)

32 | 0,67%
40 | 0,22%
48 | 0,12%

Dies lässt erwarten, dass wir, siebt man bis Iteration 56 vor, und betrachtet dann für die übrig bleibenden Restklasen mod 2^56 die jeweils 2^11 Startzahlen bis 2^67, so könnten wir dadurch unsere Größenordnung für die Laufzeitbeschleunigung gefunden haben.


Hier erst einmal der Quellcode, den ich versucht habe, möglichst lesbar zu halten:
C
  1. #include "stdio.h"
  2.  
  3.  
  4. #define sieve_depth 40
  5. unsigned __int64 rescnt = 0;
  6.  
  7.  
  8. // Zweier- und Dreier-Potenzen
  9. unsigned __int64 pot2[64];
  10. unsigned __int128 pot3[64];
  11.  
  12. #define sieve_depth_first 32
  13.  
  14. // Arrays zum Rausschreiben der Restklassen nach sieve_depth_first Iterationen
  15. // reicht bis sieve_depth_first = 32
  16. unsigned __int32 reste_array [29000000];
  17. unsigned __int64 it32_rest[29000000];
  18. unsigned int it32_odd[29000000];
  19.  
  20. // Anzahl übriger Restklassen nach sieve_depth_first Iterationen
  21. unsigned __int64 restcnt_it32 = 0;
  22.  
  23. // Füllt das Zweier- und Dreier-Potenz-Array
  24. void init_potarrays()
  25. {
  26. unsigned __int128 p3 = 1;
  27. unsigned __int64 p2 = 1;
  28. unsigned int i = 0;
  29.  
  30. for (i = 0; i < 64; i++)
  31. {
  32. pot2[i] = p2;
  33. pot3[i] = p3;
  34. p2 *= 2;
  35. p3 *= 3;
  36. }
  37. }
  38.  
  39. // Gibt an, um welchen Faktor ein Collatz-Faktor kleiner ist als die aktuell
  40. // betrachtete Restklasse; Der Wert odd gibt dabei die Anzahl der
  41. // bisher erfolgten (3x+1)-Schritte, und damit den Exponenten der
  42. // Dreier-Potenz an, durch die das Modul der Restklasse teilbar ist
  43. double corfactor(const unsigned int odd, const unsigned __int128 it_rest)
  44. {
  45. double factor = 1.0;
  46.  
  47. if (odd >= 1)
  48. {
  49. switch (it_rest % 3)
  50. {
  51. case 2: factor = 2.0/3; break; //2k+1 --> 3k+2
  52. }
  53. }
  54. else
  55. return factor;
  56.  
  57. if (odd >= 2)
  58. {
  59. switch (it_rest % 9)
  60. {
  61. case 4: factor = 8.0/9; break; //8k+3 --> 9k+4
  62. case 8: factor = 4.0/9; break; //4k+3 --> 9k+8
  63. }
  64. }
  65. else
  66. return factor;
  67.  
  68. if (odd >= 3)
  69. {
  70. switch (it_rest % 27)
  71. {
  72. case 13: factor = 16.0/27; break; //16k+7 --> 27k+13
  73. case 20: factor = 16.0/27; break; //16k+11 --> 27k+20
  74. case 26: factor = 8.0/27; break; // 8k+7 --> 27k+26
  75. }
  76. }
  77. else
  78. return factor;
  79.  
  80. if (odd >= 4)
  81. {
  82. switch (it_rest % 81)
  83. {
  84. case 10: factor = 64.0/81; break; //64k+7 --> 81k+10
  85. case 20: factor = 32.0/81; break; //32k+7 --> 81k+20
  86. case 40: factor = 32.0/81; break; //32k+15--> 81k+40
  87. case 71: factor = 64.0/81; break; //64k+55--> 81k+71
  88. case 76: factor = 64.0/81; break; //64k+59--> 81k+76
  89. case 80: factor = 16.0/81; break; //16k+15--> 81k+80
  90. }
  91. }
  92. else
  93. return factor;
  94.  
  95. if (odd >= 5)
  96. {
  97. switch (it_rest % 243)
  98. {
  99. case 76: factor =128.0/243; break; //128k+ 39 --> 243k+ 76
  100. case 91: factor =128.0/243; break; //128k+ 47 --> 243k+ 91
  101. case 107: factor = 64.0/243; break; // 64k+ 27 --> 243k+107
  102. case 121: factor = 64.0/243; break; // 64k+ 1 --> 243k+121
  103. case 137: factor =128.0/243; break; //128k+ 71 --> 243k+137
  104. case 152: factor = 64.0/243; break; // 64k+ 39 --> 243k+152
  105. case 175: factor =128.0/243; break; //128k+ 91 --> 243k+175
  106. case 182: factor = 64.0/243; break; // 64k+ 47 --> 243k+182
  107. case 233: factor =128.0/243; break; //128k+121 --> 243k+233
  108. case 236: factor =128.0/243; break; //128k+123 --> 243k+236
  109. case 242: factor = 32.0/243; break; // 32k+ 31 --> 243k+242
  110. }
  111. }
  112. else
  113. return factor;
  114.  
  115. return factor;
  116. }
  117.  
  118. void startiteration (const int nr_it, const unsigned __int128 rest,
  119. const unsigned __int128 it_rest,
  120. const double it_f, const unsigned int odd)
  121. {
  122. switch (nr_it)
  123. {
  124. case sieve_depth_first:
  125. {
  126. reste_array[restcnt_it32] = (unsigned __int32) rest;
  127. it32_rest[restcnt_it32] = (unsigned __int64) it_rest;
  128. it32_odd[restcnt_it32] = odd;
  129. restcnt_it32++;
  130. break;
  131. }
  132.  
  133. case sieve_depth:
  134. {
  135. // Siebausgang
  136. // k * 2^sieve_depth + rest --> k * 3^odd + it_rest
  137.  
  138.  
  139. // Dummy-Zähler als Platzhalter für die richtigen Tests
  140. #pragma omp atomic
  141. rescnt++;
  142. break;
  143. }
  144.  
  145.  
  146. default:
  147. {
  148. //new_rest = 0 * 2^nr_it + rest
  149. unsigned __int128 new_rest = rest;
  150. unsigned __int128 new_it_rest = it_rest;
  151. double new_it_f = it_f;
  152. unsigned int new_odd = odd;
  153.  
  154. if ((new_it_rest & 1) == 0)
  155. {
  156. new_it_rest = new_it_rest >> 1;
  157. new_it_f /= 2.0;
  158. }
  159. else
  160. {
  161. new_it_rest += (new_it_rest >> 1) + 1;
  162. new_it_f *= 1.5;
  163. new_odd++;
  164. }
  165.  
  166. if (new_it_f * corfactor(new_odd, new_it_rest) > 0.98)
  167. startiteration(nr_it + 1, new_rest, new_it_rest, new_it_f, new_odd);
  168.  
  169. //new_rest = 1 * 2^nr_it + rest
  170. new_rest = rest + pot2[nr_it];
  171. new_it_rest = it_rest + pot3[odd];
  172. new_it_f = it_f;
  173. new_odd = odd;
  174.  
  175. if ((new_it_rest & 1) == 0)
  176. {
  177. new_it_rest = new_it_rest >> 1;
  178. new_it_f /= 2.0;
  179. }
  180. else
  181. {
  182. new_it_rest += (new_it_rest >> 1) + 1;
  183. new_it_f *= 1.5;
  184. new_odd++;
  185. }
  186.  
  187. if (new_it_f * corfactor(new_odd, new_it_rest) > 0.98)
  188. startiteration(nr_it + 1, new_rest, new_it_rest, new_it_f, new_odd);
  189.  
  190. break;
  191. }
  192. }
  193. }
  194.  
  195. void init()
  196. {
  197. init_potarrays();
  198.  
  199. // 2^1 * k + 1 --> 3^1 * k + 2
  200. startiteration(1, 1, 2, 1.5, 1);
  201.  
  202. printf("Anteil ueberlebender Restklassen (%d) nach %d Iterationen: %f%%.\n", restcnt_it32, sieve_depth_first, 100.0 * restcnt_it32 / pot2[sieve_depth_first]);
  203.  
  204.  
  205. unsigned __int64 i = 0;
  206.  
  207. // Möglichkeit zur Parallelisierung
  208. #pragma omp parallel for private(i) shared(rescnt)
  209. for (i = 0; i < restcnt_it32; i++)
  210. {
  211. startiteration(sieve_depth_first + 1, reste_array[i], it32_rest[i], (double) pot3[it32_odd[i]] / pot2[sieve_depth_first], it32_odd[i]);
  212. }
  213.  
  214. printf("Anteil ueberlebender Restklassen (%d) nach %d Iterationen: %f%%.\n", rescnt, sieve_depth, 100.0 * rescnt / pot2[sieve_depth]);
  215. }
  216.  
  217. int main()
  218. {
  219. printf("Sieb bis Iteration %d gestartet:\n\n", sieve_depth);
  220. init();
  221. printf("\n Sieb beendet\n");
  222.  
  223. while (1)
  224. {
  225.  
  226. }
  227.  
  228. return 0;
  229. }

Dabei wird folgendes getan:

Zuerst einmal wird - wie bisher - mit einem einzelnen Thread bis Iteration 32 vorgesiebt und die entsprechenden Daten herausgeschrieben. Dies dient dazu, um dann über diese Restklassen mod 2^32 (sowohl in einem, aber auch potentiell über mehrere Rechner) parallelisieren zu können.

Denn nun wird jede einzelne von diesen aufgerufen (Zeilen 207 bis 212) und weiter gesiebt. Die Parallelisierung auf meinem Rechner erfolgt hier durch Anwendung von OpenMP, was man durch das Compilerflag -fopenmp beim gcc erreicht. (Andernfalls werden die pragmas einfach ignoriert und man erhält eine single threaded Variante.)

In der hier abgespeicherten Programmversion wird dann bis zur Iteration 40 weiter gesiebt. Dies kann man aber sehr leicht anpassen, indem man den Wert sieve-depth in Zeile 4 entsprechend setzt.

Dabei wird nun, nach diesem zweiten Siebschritt, das Ergebnis nicht mehr herausgeschrieben, sondern muss direkt der Aufruf für die nun zu erfolgenden Tests der Zahlen erfolgen. Dies muss dann an der entsprechenden Stelle des "Siebausgangs" (Zeilen 135-141) erfolgen. Aktuell steht dort kein Test, sondern nur ein Dummy-Zähler, der die noch zu betrachtenden Restklassen zählt, und mir so die Daten für obige Tabelle geliefert hat.

Man beachte, dass man für alle noch zu testenden Zahlen an dieser Stelle schon die ersten sieve-depth Iterationen berechnet hat:

Für die Startzahl k * 2^sieve-depth + rest ist das Ergebnis der sieve-depth.ten Iteration dann k * 3^odd + it_rest, wobei der Quotient der Dreier- durch die Zweierpotenz dem Wert it_f entspricht, d.h., die Iteration um diesen Faktor größer ist als die Startzahl.


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2449
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.224, vom Themenstarter, eingetragen 2017-01-08 19:29


cyrix,

funktioniert prima. Ich habe das mal mit meinem asm Krams "verheiratet" und suche jetzt erstmal einfach Kandidaten im Bereich bis 2^67 Startwert, die einen Pathrecord von über 125 bit beisteuern, angefangen mit den Werten an, die eine besonders grosse 3er Potenz "mitbringen" nach dem Sieb. Die Nachbereitung pro gefundenem Rest braucht aktuell bei mir so an die 30s auf einem Kern. Die Übergabe zwischen dem Sieb und der Aufbereitung mach ich aktuell noch händisch, das zu automatisieren wird ja erst erst lohnen wenn wir an mehreren Standorten CPU Leistung zusammenschmeissen wollen (ich hab aktuell keinen Kontakt zu Astrid - schreibt einer von euch mit ihr?). Genauer gesagt habe ich mir eine version deines programms "gebastelt", die einen input file schreibt mit je einem teil der reste, den ich in mein programm hineinkompiliere.

einen schönen Sonntagabend
gonz

PS.: Nebenbei gucke ich auch nach Werten, die die 118 bit überschreiten, also ggf in den gap zwischen #87 und #88 fallen könnten. Die die ich bisher gefunden habe, zB

start = 115,222371,812774,737135
record < 5,316911,983139,663473,168484,167411,826688

haben einen startwert jenseits der #88. Das < resultiert daraus, dass ich durch die ermittlung des pathrecords mit dem OR anstelle der vergleiche nur das erreichte höchste bit sicher weiss (was aber ntürlich reicht, um candidaten auszuwerfen).


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



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2328
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.225, eingetragen 2017-01-08 19:55


30s/ Rest auf einem Kern entspricht also für das gesamte Projekt einem Aufwand von ca. 10.000 Kern-Tagen. Das erscheint mir mittlerweile tatsächlich realistisch. :)

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2449
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.226, vom Themenstarter, eingetragen 2017-01-08 20:10


yep, ich bin auch ganz begeistert, zumal ich jetzt mal nen paar wirklich "grosse" werte konkret rauspurzeln sehe :)


-----------------
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: 2449
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.227, vom Themenstarter, eingetragen 2017-01-09 10:07


Guten Morgen und einen angenehmen Start in die Woche!

Zweckens der Möglichkeit zum peer-review und um ggf. Mitspieler zu finden, die Rechenleistung investieren wollten beschreib ich mal den Weg und was ich dazugebastelt habe :)

Zweck ist es, die gefundenen Reste in einer Form zu exportieren, die es erlaubt, sie in ein Programm zur weiteren Auswertung einzubinden. Dabei werden die Daten Blockweise geschrieben, und zwar für jeweils einzelne 3-Potenzen (ich fange mit den höchsten an, da hier m.E. die Wahrscheinlichkeit weiter oben Treffer zu landen etwas grösser ist).

Ich habe inzwischen auch Routinen am Start, die dasselbe in eine mysql Datenbank eintragen, oder gar per TCP/IP über das grosse weite Internet versenden können, aber solange die Rechner an einem Ort stehen ging es natürlich am bequemsten, das soweit "händisch" zu machen...

Oben in das cyrix'sche Sieb habe ich folgendes eingebaut.
C
// **********************************
// eingefuegt 2017-01-09 gonz
 
    #define ms_pot3 38
 
    // zur kompatibilitaet gcc
    #define __int64 long
    #define __int32 int
 
    // die reste werden blockweise auf dateien verteilt
    // und vorher auf einem begrenzten zwischenspeicher
    // gehalten.
 
    #define ms_blocksize 1000
    int ms_restecnt=0;
    unsigned long long ms_2rest[ms_blocksize];
    unsigned long long ms_3rest[ms_blocksize];
 
    int ms_blockcnt=0;
 
    void ms_writeblock()
        {
 
        FILE *fout;
        char filename[128];
 
        sprintf(filename,"ms_reste_%i_%i.c",ms_pot3,ms_blockcnt);
        fout = fopen(filename,"w");
        fprintf(fout,"#define ms_restecnt %i\n",ms_restecnt);
        fprintf(fout,"#define ms_pot2 %i\n",sieve_depth);
        fprintf(fout,"#define ms_pot3 %i\n",ms_pot3);
        fprintf(fout,"unsigned long long ms_2rest[ms_restecnt];\n");
        fprintf(fout,"unsigned long long ms_3rest[ms_restecnt];\n");
 
        int gloop;
        for (gloop=0;gloop<ms_restecnt;gloop++)
                {
                fprintf(fout,"ms_2rest[%i]=%lli; ms_3rest[%i]=%lli;\n",gloop,ms_2rest[gloop],gloop,ms_3rest[gloop]);
                }
        fclose(fout);
 
        printf("%i reste wurden in Datei %s geschrieben.\n",ms_restecnt,filename);
 
        ms_blockcnt++;
        ms_restecnt=0;
 
        }
 
// gonz ende
// **********************************

Unten unter dem Stichwort "Siebausgang" dann folgendes:
C
// **********************************
// eingefuegt 2017-01-09 gonz
 
                        // da 128 bit typen nicht geschrieben werden koennen mit printf
                        // diese variablen zur uebergabe
                        unsigned long long dis1 = rest;
                        unsigned long long dis2 = it_rest;
 
                        // und vermerken der werte.
                        if (odd==ms_pot3)
                                {
                                printf("Found 2base=%i 2rest=%lli odd=%i 3rest=%lli\n",sieve_depth,dis1,odd,dis2);
                                ms_2rest[ms_restecnt]=dis1;
                                ms_3rest[ms_restecnt]=dis2;
                                ms_restecnt++;
                                if (ms_restecnt>=ms_blocksize)
                                        ms_writeblock();
                                }
 
// gonz ende
// **********************************

Der Grund dafür, die Werte erst in einem Array zwischenzuspeichern und dann erst blockweise in die Datei zu schreiben, ist es, dass ich oben in die Datei die Anzahl der enthaltenen Daten schreiben will und diese erst weiss, wenn ich sie gefunden habe.

Dann noch am Ende um einen noch angefangenen, aber nicht ganz aufgefüllten Block zu schreiben, dh nach dem Stichwort "Sieb beendet"
C
// **********************************
// eingefuegt 2017-01-09 gonz
 
        if (ms_restecnt>0)
                ms_writeblock();
 
// gonz ende
// **********************************

Das Programm läuft auch damit auf einem handelsüblichen Rechner in einer Zeit durch, die man mit "Kaffee holen und kurz mit den Kollegen plaudern" verbringen kann. Was mit der Ausgabedatei dann weiter passiert, beschreibe ich im nächsten Post, sowie ich es ein bissl aufgehübscht habe. Die Ausgabe sieht dann so aus (hier: Blockgrösse auf 1 gestellt für Testzwecke)
plain Text
Sieb bis Iteration 40 gestartet: Suche nach Resten mit pot3 38
Found 2base=40 2rest=610362574619 odd=38 3rest=750473176484995604

(man sieht ich habe noch ein wenig mehr geändert und Texte ein wenig angepasst, was aber für die Funktion unerheblich ist)

Und der Output ist dann so etwas wie
C
#define ms_restecnt 1
#define ms_pot2 40
#define ms_pot3 38
unsigned long long ms_2rest[ms_restecnt];
unsigned long long ms_3rest[ms_restecnt];
ms_2rest[0]=610362574619; ms_3rest[0]=750473176484995604;

Einen schönen Tag allerseits!
Wünscht gonz
(eingeschneit im Harz - endlich mal was mehr Schnee! ggg)

PS: das praefix ms_ steht für "megasieb" - irgendwie muss das kind ja heissen :)




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



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 20.04.2013
Mitteilungen: 109
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.228, eingetragen 2017-01-09 19:05


Ich hab' mal ein paar Ideen umgesetzt und damit meine C-Version
um den Faktor 2 beschleunigen können - ich könnte mir vorstellen,
dass die verwendeten Techniken auch für die Assembler-Version
interessant sind (FCM.cpp)

Ideen:
- loop unrolling (kein loop overhead).
- Minimierung der fast immer ins Leere laufenden Abfragen gegen
  einen neuen Pfadrekord.
- Reduzierung des Aufwands zur Abprüfung gegen den Startwert
  (statt 128Bit-Vergleich ein einfacher int-Vergleich)
- Rest 2 mod 3 Prüfung
- Konzentration aller RightShifts von insgesamt fünf "3x+1"-Operation
  auf eine Stelle
- Konzentration der Bearbeitung der oberen 64bit von insgesamt fünf
  "3x+1"-Operation auf eine Stelle

Die Version dürfte noch nicht mal komplett ausgereizt sein!

- ich habe es noch nicht genau untersucht, vermute aber mal, dass
  bei den im Programm verwendeten Eingangsdaten (Werte nach
  gonzens Sieb) die ersten zwanzig Abfragen gar nie zuschlagen -
  die Routine könnte also an die Eingangsdaten angepasst werden.
- einige Abfragen sind vollkommen überflüssig und nur der
  momentanen Orthogonalität geschuldet.
- die Routine enthält eine Rest 2 mod 3 Prüfung (besser kann man
  die vermutlich nicht realisieren), die mir nicht besonders effektiv
  erscheint und gegebenenfalls mitsamt den dadurch entstandenen
  überflüssigen Abfragen entfernt werden kann (ersten Beobachtungen
  nach trägt die Rest 2 mod 3 Prüfung weniger als 0,5% zum Sieberfolg
  mit einem verbleibenden Rest von 2% bei).
- die Verarbeitung der oberen 64bit lassen sich u.U. komplett tilgen
  wenn man gar nicht mehr gegen ein oberes Limit prüft - wie in
   Beitrag No.202  nachgerechnet, könnte man eine derart optimierte
  Routinie zweimal hintereinander laufen lassen, bevor im
  interessanten Bereich ein Startwert bis in die Nähe des
  Pfadrekords #87 iteriert sein kann (und es ist sicherlich
  effektiver, bei 2 von hundert Folgen die Folgewerte erneut
  zu ermitteln als bei 98 von hundert Folgen, die ausgesiebt
  werden, die oberen 64bit mitzuschleppen),
- u.U. kann man dann sogar auch auf die RigthShifts verzichten und
  komplett auf OnkelGeorgis Pfaden wandeln (Beitrag No.59).


Die Version ermittelt die Pfadrekorde ab #40 korrekt (soweit in
angemesserner Zeit zu testen war), wurde sonst aber keinen
eingehenderen Tests unterzogen - bei Übernahme von Codeteilen
sollte diese einem eingehenden CodeReview unterzogen werden,
insbesondere wäre zu prüfen,  ob ich cyrixs Vorgaben für die
Rest 2 mod 3 Prüfung korrekt umgesetzt habe.
Den Start erst ab #40 habe ich gewählt, weil ich einen größeren
Faktor zwischen Startwert und aktuellem Pfadrekord benötige,
um die Abfragen gegen ein oberes Limit reduzieren zu können.



  Profil  Quote  Link auf diesen Beitrag Link
dlchnr
Aktiv Letzter Besuch: im letzten Quartal
Dabei seit: 20.04.2013
Mitteilungen: 109
Aus: Aalen, DE
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.229, eingetragen 2017-01-09 19:09


Hier noch ein paar Bilder des Codes im Folding Editor.

Die Kernroutine besteht aus 8 Gruppen mit fünf "3x+1"-Stufen.  



In jeder dieser Gruppe wird Platz für sämtliche Carries der
folgenden fünf "3x+1"-Stufen geschaffen.
Nach den fünf "3x+1"-Stufen werden die oberen 64bits und die
Überträge verarbeitet, bevor der Platz für die Carries gelöscht
wird, um danach die gesammelten RightShifts auszuführen und
um gegen den aktuelle Pathrecord/256 zu prüfen.



Das letzte Bild zeigt weitere Details (Falten aufgeklappt),
u.a. auch eine jener Abfragen ("if ((dif  & 1) && (sum >= 13))"),
die komplett überflüssig ist, weil nie wahr werdend.





  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2328
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.230, eingetragen 2017-01-10 02:39


@gonz, Beitrag #227:

M.E. verwendest du das Sieb "falsch": Man sollte sinnvollerweise obrhalb von 32 Bit nicht mehr die Daten herausschreiben. Bei 40 Bit bleiben ja noch ca. 2 *10^9 Restklassen über... (Ich hoffe, dass die Laufzeit von 30s/Kern pro Restklasse in Beitrag #224 sich nicht auf diese Milliarden, sondern auf die knapp 30 Millionen übriger Restklassen mod 2^32 beziehen.)

Gedacht war, dass man bis sieve-depth 56 vorsiebt und dann die Zahlen k*2^56 + rest (bzw. schon ihre 56. Iterationen k*3^odd + it_rest) direkt testet. (Durch das Weiter-Sieben von 40 auf 56 Bit fliegen, insbesondere bei den Restklassen mit kleinerer Dreierpotenz, allein schon ca. 3/4 aller zu testenden Werte raus.)


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2449
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.231, vom Themenstarter, eingetragen 2017-01-10 09:20


dlchnr:
Das muss ich mir in ruhe ansehen :)

cyrix:
leider bezogen sich die 30 sec auf die 2^40 restklassen. allerdings bin ich inzwischen deutlich schneller, sodass die wahrheit irgendwo in der mitte liegt. ich werd da asap ordentliche benchmarks nachliefern.

Tatsächlich wollte ich die daten auch nicht komplett herausschreiben, sondern habe eben eine lockere kopplung zwischen dem siebporzess und dem "abarbeiten" der überlebenden reste vor augen - insgesamt eine lösung, die auf mehrere server verteilt ist, die via ethernet verbunden sind. dafür wäre doch der siebausgang der richtige punkt, um "weiter zu verteilen". dass ich sie jetzt blockweise in dateien schreibe ist ein behelf, weil ich einfach zu neugierig uaf erste ergebnisse bin. an der stelle kommt dann natürlichwerise ein anderer ipc mechanismus zur anwendung...

ich hoffe damit treffen sich unsere vorstellungen irgendwo.

wie soll die erhähung auf 56bit sieben denn eigentlich erfolgen - indem man die entsprechende konstante in deinem vorliegenedne programm von 40 auf 56 erhöht, oder willst du dort, wo jetzt der siebausgang ist, noch einen prozess nachschalten?

beste grüsse
und einen schönen tag

gonz


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



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1818
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.232, eingetragen 2017-01-10 12:48


2017-01-08 11:03 - cyrix in Beitrag No. 223 schreibt:
So, ich habe mal etwas gebastelt und das angesprochene tiefergehende Sieb geschrieben. Die schlechte Nachricht vorweg: Die "Verbesserung" auf ca. 20 Millionen (von 30) Restklassen mod 2^32 entstand aufgrund eines Programmierfehlers; real ist es nur eine auf ca. 29 Millionen.




Cyrix
C
#include "stdio.h"
#define sieve_depth 40
 
    unsigned __int64 rescnt = 0;
.
.

Ich habe den obigen code block als cyrixx.c gespeichert mit gcc -Ofast cyrixx.c -o cyrix versucht zu compilieren und bekomme gleich:
                                                                                  ^
root@h2543043:/home/juergen# gcc -Ofast cyrixx.c -o cyrix
cyrixx.c:4:22: error: expected ‘=’, ‘,’, ‘;’, ‘asm’ or ‘__attribute__’ before ‘rescnt’
     unsigned __int64 rescnt = 0;

Sorry meine Unkenntnisse der Sprache c, aber was mach ich da falsch?
Jürgen



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2449
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.233, vom Themenstarter, eingetragen 2017-01-10 12:51


du brauchst folgendes:
C
   // zur kompatibilitaet gcc
    #define __int64 long
    #define __int32 int



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



  Profil  Quote  Link auf diesen Beitrag Link
juergen007
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 17.08.2006
Mitteilungen: 1818
Aus: Braunschweig
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.234, eingetragen 2017-01-10 13:12


2017-01-10 12:51 - gonz in Beitrag No. 233 schreibt:
du brauchst folgendes:
C
   // zur kompatibilitaet gcc
    #define __int64 long
    #define __int32 int


ja und rescnt ist from Typ "$li" wg der betroffenen Print formate.



  Profil  Quote  Link auf diesen Beitrag Link
Slash
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 23.03.2005
Mitteilungen: 4972
Aus: New York
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.235, eingetragen 2017-01-10 23:46


Hi,

ich komme hier zwar programmiertechnisch schon lange nicht mehr mit, aber ich wollte schon seit langem ein Video von Marc Chamberland verlinken. Es gibt auch einen zweiten Teil.

The 3x+1 Problem: Status and Recent Work Part 1

Gruß, Slash


-----------------
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
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2449
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.236, vom Themenstarter, eingetragen 2017-01-12 09:38


cyrix:

oder meintest du mit "falsch benutzt" einfach "technisch" falsch? wenn ich die Werte abgreife unterhalb des Kommentars "Sieb Ausgang" bekomme ich einfach falsche Werte, und ich weiss nicht woran es liegt... Wenn ich zB auf odd=35 triggere bekomme ich als ersten Wert

Sieb bis Iteration 40 gestartet: Suche nach Resten mit pot3 35
Found 2base=40 {1099511627776} 2rest=365046399003 odd=35 [50031545098999707} 3rest=16805122279692461

und dabei stimmt weder die odd anzahl noch der 3-er Rest, wenn ich mir die Folge konkret anschaue....

Jeder Hinweis willkommen :)

mit besten Grüssen
und einen schönen Tag wünscht

gonz



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



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2328
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.237, eingetragen 2017-01-13 14:01


@gonz: Erst einmal danke für dein Testen! Du hast mich dadurch auf einen Programmierfehler aufmerksam gemacht. (Es gab einen "off by one"-Fehler beim Übergang Rausschreiben nach 32-Iterationen zum Weitersieben mit Iteration 33... Um das Problem zu beseitigen, sind die zwei Siebabschnitte jetzt in getrennte Methoden ausgelagert, auch wenn sie sich in großen Teilen des Codes gleichen. Genauer gesagt, sind es jetzt 3 Methoden: Eine [startiteration] siebt bis 32 Iterationen, die nächte [nextiterations] bis Iteration 40 und die letzte [nnextiterations] bis zum Sieblimit, was man auf wohl etwa 10 Bits unterhalb der Suchgrenze, für uns also sinnvollerweise in der Gegend von 56, festlegen sollte. Dort fallen dann die zu testenden Zahlen raus. Im letzten Siebabschnitt wurde die Überprüfung auf Rückwärtsiterationen aus Laufzeitgründen weggelassen.)

Gegenüber der letzten Version (Beitrag #223) sind noch zwei weitere, kleinere Änderungen durchgeführt: Ich siebe jetzt in corfactor einen weiteren, nun den 6. Rückwärtsschritt und habe dort zwei Restklassen entfernt, bei denen fälschicherweise ein zu großer Wert stand (man also besser den Wert mod einer kleineren Dreierpotenz für diese Restklasse genommen hätte; und nun tut).

Die aktuelle Version findet man  hier. Setzt man für Testzwecke corfactor auf 1, (d.h., die Methode gibt konstant den Wert 1 zurück), so erhält man genau die von Olivera e Silva ermittelten Werte der Anzahl übrigbleibender Restklassen bis 2^40. Auch meine Testausgaben sahen gut aus, was die Berechnung der einzelnen Restklassen angeht. Gern kann und soll man aber auch weitertesten! :)

Als neue Werte für den Anteil überlebender Restklassen gilt nun:

nach 32 Iterationen: 0,638% (ca. 27,4 Millionen)
nach 40 Iterationen: 0,380%
nach 48 Iterationen: 0,24 % (ohne Überprüfung auf mögl. Rückwärtsschritte nach Iteration 40)


Dies entspricht einer Verringerung auf ca. 2/3 der Werte nach 32 bzw. 40 Iterationen gegebenüber den Ergebnissen von Olivera e Silva.


Ich werde auch demnächst noch hier wieder die ersten Multisteps immplementieren, sodass dann nur die Kandidaten, die die ersten ca. 80 Iterationen überleben, ausführlich getestet werden müssen.

Grüße
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2449
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.238, vom Themenstarter, eingetragen 2017-01-19 11:54


Hi :)

um auch meinen Stand diesbezüglich ein wenig zu dokumentieren - ich habe jetzt eine Kette laufen, bestehend aus

- "Cyrix Sieb" erzeugt Reste bis 2^57 (verteilt auf 3 Kerne) und liefert gleich das Ergebnis nach diesen Iterationen (3-er Faktoren und zugehörige Reste)
- "brute-force" berechnet aufbauend darauf alle Folgen bis startwert 2^67 und vermerkt Folgen die pathwerte von 2^112 überschreiten ("candidates")
- "storage" berechnet für die vom bforce identifizierten Kandidaten den wirklichen Pathwert (bforce guckt nur auf das höchste bit) und verwaltet, welche Candidates verbleiben und welche sich gegenseitig schon topen.

Richtige Benchmarks habe ich hierzu noch nicht, das System gelangt damit jedenfalls schonmal in den interessanten Bereich und erzeugt einen ganz lustigen Output. Leider habe ich es die Tage immer wieder neu starten müssen weil ich noch am Software frickeln war.

Vielleicht schreib ich Richtung WE mal einen kleinen Artikel dazu, um ggf. auch den einen oder anderen anzusprechen, der Rechenleistung beisteuern mag - sprich einen oder gar mehrere Kerne auf einem Linuxrechner mit Internetverbindung...



Glück auf! oder... have fun!
gonz


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



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2328
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.239, eingetragen 2017-01-19 15:53


@gonz: Schön, dass u Fortschritte erzielst!

Auch ich habe noch ein wenig gebastelt und i.W. im Vergleich zur letzten Version eine Multistep-Variante gebastelt, die nach dem Sieben bis Iteration 56 dann die entsprechenden Startzahlen bis 2^67 erzeugt und dann weiter berechnet.

Dabei werden je 12 Iterationen auf einmal erledigt und je 5 solcher Multisteps zusammengefasst, sodass die ganzen Operationen mit 64-Bit-Integers ablaufen kann. Nur für die Kandidaten, wo dann noch nicht die Stoppzeit erreicht wurde, muss die Rechnung mit 128-Bit-Arithmetik wiederholt werden. Darauf folgt dann der rekursive Aufruf der nächsten 5*12 Iterationen...

Als Abbruchbedingung habe ich der Einfachheit halber formuliert, dass der maximal erreichte Wert 10^17 mal größer als der Startwert ist. (Es wird also nicht der absolute Wert überprüft, weil jener Faktor "kostenfrei" zur Verfügung steht.) Eine Verwaltung der Kandidaten findet nicht statt.

Die aktuelle Version findet man  hier. Damit erziele ich Laufzeiten von im Schnitt ca. 4 Kern-Minuten pro zu testender Restklasse mod 2^32, was bei knap 30 Millionen solcher noch zu testender Restklassen ein Aufwand von ca. 80.000 Kern-Tagen entsprechen würde.

Allerdings sehe ich hier für mich nun keine Ideen zur weiteren Laufzeitverbesserung mehr.

@gonz: Du könntest mal ausprobieren, ob es für dich was bringt, wenn du einen solchen Multistep-Durchlauf (also die 5*12-Iterationen, ohne Rekursionsaufruf) deiner Assembler-Implementation der Single-Step-Variante vorschaltest. Ob die nun deutlich entschlackte Multistep-Methode vielleicht auch ganz in Assembler gegossen werden kann, ist vielleicht auch noch einmal von den Fachleuten zu überlegen.


Viele Grüße
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
-->> Fortsetzung auf der nächsten Seite -->>
Seite 6Gehe 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]