Die Mathe-Redaktion - 27.03.2017 20:23 - Registrieren/Login
Auswahl
Schwarzes Brett
Wartet darauf, dass Fragensteller die Antwort(en) liest2017-03-27 14:37 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 603 Gäste und 32 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 4   [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: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.120, eingetragen 2016-12-01 08:40


hallo an alle,

ich habe mir mal deinen  'kleinen' satz genauer angesehen, cyrix (#88), und auch die von dir dazu angegebene literatur. unabhängig davon, dass ich selbst in der lage bin fehler zu machen, scheint mir dein argument der splittung in die teilzyklen (entsprechend den ungerade restklassen von 2^128) nicht schlüssig.

in der genannten masterarbeit wird der dort <math>\mu</math> genannte mittelwert der ungeraden reziproken durch die teilung aller ungeraden zahlen in eine hälfte mit kleineren und eine hälfte mit grösseren werten vorgenommen. das finde ich schlüssiger, denn diese betrachtung braucht kein wissen darüber wieviele T's davor oder danach waren. wie gesagt, ich verstehe dein ansinnen, die ungeraden zykluszahlen nicht nur in zwei gruppen, sondern in 2^n gruppen zu splitten, aber sehe (noch) nicht, wie du die verteilung ausreichend begründest. tut mir leid, aber vllt mache ja auch ich, wie gesagt, den fehler.

dennoch sehe ich (wie du) entwicklungspotenzial in der verbesserung von <math>\mu</math>. in der genannten masterarbeit findet sich <math>\mu \le \frac{8}{9}m^{-1}</math> und das lässt sich verbessern auf <math>\mu \le \frac{7}{8}m^{-1}</math>. genauer, im nachweis, dass für alle ungeraden <math>n<\frac{9}{7}m</math> der nächste schritt ungerade ist, liefert eine bedingung an m (in der masterarbeit ist dies <math>m \ge 21</math>, da ist allerdings ein rechenfehler drin, richtig wäre <math>m \ge 7</math>). nutzen wir jetzt aus, dass m deutlich grösser ist und auch noch von der form 12k+7 sein muss, dann ist <math>\mu \le \frac{14k+8}{16k+9}\frac{1}{12k+7}</math>.

genauer: man würde ungerades <math>n<\frac{x_1}{x_2}*m</math> mit <math>x_1>x_2</math> ansetzen, sd. <math>T^2(n)=\frac{3n+1}{4}<\frac{3(\frac{x_1}{x_2}m)+1}{4}<m</math>. Dies führt auf <math>x_2 \le (4x_2 - 3x_1)m</math> und mit <math>x_1=x_2 +a</math> auf <math>x_2 \le (x_2 -3a)m</math>. nun soll weiter <math>x_2 -3a=1</math> sein, es ist also <math>x_1 = 1+4a</math> und <math>x_2 =1+3a</math>.

den mittelwert <math>\mu</math> bilden wir wie folgt <math>\frac{1}{2}(1+\frac{1+3a}{1+4a})m^{-1}=\frac{2+7a}{2+8a}m^{-1}</math>. schon hier sieht man, dass für grosse a dieser wert gegen <math>\frac{7}{8m}</math> geht.
berücksichtigen wir darüber hinaus, dass m=12k+7 ist, dann ist a=4k+2 und <math>\mu</math> ergibt sich wie oben behauptet.

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
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.121, eingetragen 2016-12-01 17:03


zu den obigen überlegungen vllt noch ein statistisches argument:

nehmen wir an, dass sich die verteilung "max. die hälfte der ungerade zahlen befindet sich im intervall <math>I_1=(m,\frac{1+4a}{1+3a} m)</math>, min. die (andere) hälfte im intervall <math>I'_2=(\frac{1+4a}{1+3a} m, \infty)</math>" auch im intervall <math>I'_2</math> fortsetzt (sprich dieses teilt sich in ein intervall <math>I_2=(\frac{1+4a}{1+3a} m,\frac{1+4a}{1+3a} \frac{1+4a}{1+3a} m)</math> und <math>I'_3=(\frac{1+4a}{1+3a} \frac{1+4a}{1+3a} m,\infty)</math>, ebenso <math>I'_3</math> in entsprechende intervalle <math>I_3</math> und <math>I'_4</math> usw.), dann ergibt sich bei der berechnung von <math>\mu</math> letztlich eine geometrische reihe mit dem ergebnis <math>\mu \le \frac{1+4a}{1+5a} m^{-1}</math>. für große a ist das also höchstens ein faktor 0,8 vor dem 1/m.

der faktor 0,5... aus #88 würde bedeuten, dass es deutlich mehr "große" ungerade zahlen gäbe, was ich wie gesagt im moment nicht sehe.

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
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.122, eingetragen 2016-12-01 17:25


Hallo miteinander,

ich bin vorübergehend ausser Gefecht gesetzt - man nennt es Reha, ich hoffe in ein paar Wochen wieder am Start. Viel Erfolg bis dato gerade mit dem Collatz Projekt, ich melde mich, versprochen.

Kofferpackende Grüsse
Astrid



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


@trunx: Nurkurz, da ich gerade auch an anderer Stelle beschäftigt bin:

Die Argumentation geht wie folgt:

Ich fange mit irgendeiner ungeraden Zahl x des Zyklusses an und betrachte (je nach Restklasse von x mod 2^128) die nächsten (bis zu 128) ungeraden Folgenglieder des Zyklusses. Für diese kann ich zeigen, dass die Summe über deren Reziproke < 1/(188*2^60) * "Anzahl hier betrachteter ungerader Folgenglieder" ist, also das durchschnittliche Rizproke < 1/(188*2^60). Dann nehme ich mir die nächste ungerade Zahl im Zyklus x' und zeige die gleiche Schranke, usw., da diese für alle [!] Restklassen mod 2^128 gültig ist. Damit folgt sie auch insgesamt für den gesamten Zyklus.

Cyrix

@edit, @Astrid: Erhole dich gut! :)

[Die Antwort wurde vor Beitrag No.1 begonnen.]



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.124, eingetragen 2016-12-01 18:11


@astrid: auch von mir gute besserung :)

@cyrix: ich glaube, der fehler liegt darin, dass die ungeraden folgenglieder x des zyklus' mod 2^128 betrachtet werden. da x < 2^128 ist, ist der rest nicht von x verschieden. anders ausgedrückt, in x = 2^128 * k + r, ist k=0. daher spielt das verhalten von 2^128 unter der collatz-funktion keine rolle und kann auch nicht für die abschätzung benutzt werden. du müsstest also die überlegungen vllt für mod 2^32 machen (ist jetzt nur eine idee).


-----------------
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: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.125, eingetragen 2016-12-01 18:28


Ob nur Folgenglieder < 2^128 vorkommen oder nicht, ist doch für die Betrachtung egal. Erstens wissen wir nicht, wie groß die Folgenglieder werden; und zweitens ist es doch nur allgemeiner...

Du kannst die gleiche Überlegung auch modulo 4 durchführen:

1. Fall: x == 1 (mod 4), also x= 4k+1. Dann ist das nächste ungerade Folgenglied y <= 3k+1 (oder kleiner). Da aber auch dies >= de minimalen Wert m ist, ist also x >= 4/3 m und also 1/x + 1/y <= (3/4 + 1) * 1/m = 2* (7/8 * 1/m).

2. Fall: x == 3 (mod 4), also x= 4k+3. Dann ist das nächste ungerade Folgenglied y=6k+5. Da x >= m, ist also y >= 3/2 m und also 1/x+1/y <= (1 + 2/3) * 1/m = 2 * (5/6 * 1/m).

Wir haben also gezeigt, dass in beiden Fällen gilt, dass der "durchschnittliche Reziproke" <= 7/8 * 1/m ist.


Genau das Gleiche mache ich in #88 auch, nur mod 2^128 statt 2^2...

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.126, eingetragen 2016-12-01 19:16


sry, dass ich so hartnäckig bin (ich will dir auch nicht die zeit rauben).

aber das beispiel 2^2 zeigt sehr gut, was ich meine: du teilst angeblich alle ungeraden zahlen in die zwei disjunkten restklassen 1 und 3 auf, und für die startwerte gilt dies auch, aber eben nicht mehr für 3k+1 und auch nicht für 6k+5. es ist nun nicht mehr klar zu welcher restklasse der eine oder andere wert gehört. der mittelwert könnte nun verfälscht sein, weil (offenbar größere) werte mehrfach gezählt werden.

wie gesagt, vllt raffe ich's ja auch nur einfach nicht...




-----------------
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: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.127, eingetragen 2016-12-01 19:49


Seien die ungeraden Folgenglieder des Zyklusses mal mit a_1, a_2, a_3, a_4, ... bezeichnet.

Dann macht die Betrachtung mod 4 folgendes:

*) Fange mit a_1 an. Entweder das ist kongruent 1 oder 3 mod 4. in beiden Fällen haben wir nachgeiwesen, dass 1/a_1 + 1/a_2 sich nach oben durch 2 * (7/8 * 1/m) abschätzen lässt.

*) Fahre nun mit dem ersten ungeraden Folgenglied, was bisher noch nicht betrachtet wurde, fort. Also mit a_3. Es folgt analog 1/a_3 + 1/a_4 < 2 * (7/8 * 1/m).

*) ...


Addiere alles zusammen: Damit ist 1/a_1 + 1/a_2 + 1/a_3 + 1/a_4 + ... < n * (7/8 * 1/m), wobei n die Anzahl der hier betrachteten ungeraden Folgenglieder ist.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.128, eingetragen 2016-12-01 21:36


das mit der mittelwertbildung ist klar.

ich versuche dir noch mal anders mein 'unbehagen' zu vermitteln (wenn man dieses wort überhaupt benutzen darf :D)

der mittelwert von was auch immer ist <math>\frac{1}{n} \sum \limits_{k=1}^{n} a_k</math>. jetzt macht es ja nichts in der summe mit (im einfachsten fall) zwei zu erweitern, wir bekommen also <math>\frac{1}{n} \sum \limits_{k=1}^{n} \frac{a_k +a_{k+1}}{2}</math>, wobei wir <math>a_{n+1}=a_1</math> berücksichtigen. ok?

jetzt sind die <math>a_k</math> wie bei dir die ungeraden (geordneten) zykluszahlen und logischerweise folgt daher <math>a_{k+1}</math> auf <math>a_k</math>. wenn wir jetzt wie du alle diese zahlen in restklassen mod 2^m aufteilen, dann könnten wir den mittelwert tatsächlich abschätzen.

zwingende voraussetzung ist jedoch, dass <math>a_{k+1}</math> auch wirklich eine ungerade zahl ist! nach 4k+1 kommt aber 3k+1 und das ist nicht sicher eine ungerade zahl. es wird dir auch mit keinem anderen m>2 gelingen, dass allen restklassen direkt im nächsten schritt wieder eine ungerade zahl folgt.

dass in einem zyklus auf jede ungerade zahl iwann wieder eine ungerade folgt, ist klar, aber hier in der abschätzung des mittelwert folgt diese eben nicht eindeutig, so dass von einer ordentlichen abschätzung nicht die rede sein kann (meiner meinung nach).

ich hoffe, dass es dieses mal klarer ist, was ich meine :)

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
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.129, eingetragen 2016-12-01 22:11


aber mir fällt grad was auf, vllt kann man deine idee ja doch noch retten :) oder ich habs endlich verstanden :D
mehr dazu morgen, ich muss jz ins bett


-----------------
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: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.130, eingetragen 2016-12-01 23:44


Natürlich ist es zwingend, dass a_k+1 eine ungerade zahl ist; so sind die a_i ja gerade definiert. Und, wenn du oben mal genauer schaust, ist auch nicht gesagt, dass im Fall a_k = 4k+1 nun a_k+1=3k+1 ist; sondern genauer a_k+1 <= 3k+1. Denn entweder ist 3k+1 ungerade, dann gilt das Gleichheitszeichen, oder es ist gerade. In dem Fall entsteht das nächste ungerade Folgenglied durch weiteres Halieren von 3k+1, ist also explizit kleiner...

@trunx: Meine Idee muss hier nicht gerettet werden; du musst sie nur verstehen. Dazu mus ich sie eben offensichtlich besser erklären.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.131, eingetragen 2016-12-02 00:10


Ok, also nun noch einmal formaler:

Es sei <math>a_1</math>, <math>a_2</math>, ... , <math>a_n</math> die Folge der ungeraden Folgenglieder eines nicht-trivialen Collatz-Zyklusses. Dann zerlegen wir diese in (nicht notwendigerweise gleich lange) Teilstücke <math>a_1</math> bis <math>a_{i_1}</math>, <math>a_{i_1+1}</math> bis <math>a_{i_2}</math>, ... , <math>a_{i_{k-1}+1}</math> bis <math>a_{i_k}</math> und <math>a_{i_k+1}</math> bis <math>a_n</math>, der Länge jeweils <= 128, sodass für alle, bis auf das letzte Teilstück die Ungleichung

<math>\sum_{j={i_l}+1}^{{i_{l+1}}} \frac{1}{a_j} \leq \left({i_{l+1}} -  {i_l} \right) \cdot \frac{1}{188*2^{60}}</math>

gilt. Dann folgt das auch für die Summe, die man aus der Addition all dieser Abschnitte (bis auf den letzten) erhält. Die letzten Folgenglieder kann man nicht ganz so scharf abschätzen. Da es aber maximal 127 sind; und da es > 6 Millionen insgesamt gibt (also n > 6 Millionen), verändert die dadurch entstehende, leicht schlechtere Abschätzung dieses letzten Abschnitts die Gesamtabschätzung nicht mehr wesentlich. (Und ja, ich habe das exakt durchgerechnet.)


Wie zeigt man, dass auf einem solchen Teilabschnitt die entsprechende Abschätzung über die Summe der Reziproken gilt? Nun, genau wie oben am Beispiel der Betrachtung des jeweils ersten Glieds einer solchen Teilfolge modulo 4 aufhezeigt:

Durch die Betrachtung modulo 2^k können wir Aussagen darüber treffen, wie die nächsten Schritte der Collatz-Folge aussehen. Insbesondere erhalten wir Aussagen darüber, wie groß die nächsten bis zu k ungeraden Folgenglieder sind. Und für alle wissen wir, dass sie >= dem Minimum der im Zyklus auftretenden Folgenglieder sind. Daraus ergeben sich wiederum entsprechende Abschätzungen für die anderen, in diesem Abschnitt vorkommenden ungeraden Folgenglieder, sodass wir schließlich für die meisten darin vorkommenden ungeraden Folgenglieder deutlich bessere Abschätzungen als <math>a_j \geq m</math> erhalten. Berechnen wir dann die Summe der Reziproken, erhalten wir schließlich die oben angegebene Ungleichung für diesen Abschnitt.

Und wie sichert man, dass diese Abschätzung für jeden solchen Abschnitt (bis auf den letzten) gültig ist? Indem man eine volle Fallunterscheidung macht, in welche Restklasse das jeweils erste Folgenglied eines solchen Abschnitts fällt. In irgendeine muss es ja fallen... Zeigen wir also für jede solche Restklasse, dass ein solcher Abschnitt, der mit einem Element dieser Restklasse beginnt, die gewünschte Abschätzung erfüllt, dann folgt das insbesondere also auch für alle "real existierenden" Abschnitte, wie sie sich bei einem konkreten nicht-trivialen Zyklus ergeben, wenn man nach obiger Konstruktion verfährt.


edit: Wir zeigen natürlich schärfer, dass der durchschnittliche Reziproke < 1/(188 * 2^60) ist; unter der Annahme, dass keine Startzahl < 110 * 2^60 auf einen nicht-trivialen Zyklus führt. Die Zahlenwerte muss ich noch anpassen, hatte ich zuvorderst hier heute Abend falsch notiert.


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.132, eingetragen 2016-12-02 12:57


hallo cyrix,
vielen dank nochmal für deine geduld :)

mit "retten" meinte ich nur das, was ich verstanden habe. wie gesagt, ich hatte gestern abend eine idee, was du gemeint haben könntest, sehe aber, dass das nicht der fall ist. deshalb schreibe ich mal ausführlicher meine gedanken auf (in der hoffnung, dass wir uns iwann mal gegenseitig verstehen):

ich gehe wie du von dem (hypothetischen) nichttrivialen zyklus mit den ungeraden folgengliedern <math>a_i</math> i=1,...,n aus. mittelwert ist also <math>x=\frac{1}{n} \sum \limits_{i=1}^{n} a_i^{-1}</math>.

jz betrachte ich einen schritt in der folge, um den mittelwert über die teilmittelwerte unter der summe in <math>x=\frac{1}{n} \sum \limits_{k=1}^{n} \frac{a_k^{-1} +a_{k+1}^{-1}}{2}</math> mit <math>a_{n+1}=a_1</math> abzuschätzen. dazu betrachte ich zunächst die restklassen mod4, wir haben 4k+3 -> 6k+5, also ein reziprokes verhältnis von 2/3 zwischen ausgangswert und nachfolger. bei 4k+1 kommen wir zunächst auf keine ungerade zahl, dh. wir betrachten 8k+1 und 8k+5. 8k+1 führt auf 6k+1, 8k+5 müsste wieder detaillierter betrachtet werden (also 32k+5, 32k+13, 32k+21, 32k+29).

das brauchen wir aber nicht zu tun, denn für die abschätzung brauchen wir nicht alle reziproken verhältnisse, die möglich sind, sondern nur die größten! und diese bekommen wir auf andere weise.

für die größten reziproken verhältnisse kommen für den k-ten schritt stets nur zwei werte in frage nämlich <math>\frac{2^{\lfloor k* log_2 3 \rfloor}}{3^k}</math> und <math>\frac{3^k}{2^{\lceil k*log_2 3\rceil}}</math>. für den ersten schritt sind dies 2/3 bzw. 3/4, für den zweiten schritt 8/9 bzw. 9/16 usw.

für die abschätzung von x nach K schritten benutzen wir das jeweilige maximum, sprich wir haben
<math>\displaystyle x\le \frac{1}{K+1} (1+ \sum \limits_{k =1}^K max(\frac{2^{\lfloor k * log_2 3 \rfloor}}{3^k},\frac{3^k}{2^{\lceil k *log_2 3\rceil}}))m^{-1}=\frac{1}{K+1} (1 +\frac{3}{4} +\frac{8}{9} +\cdots)m^{-1}</math>.

ich hab das jz mal in php programmiert:
php
$k=1000;
$k2='1'; $z2_global=0; $k3='1';
$mu=array(); $p=array(); $q=array(); $q2=array(); $q3=array();
$mu[0]=1; $p[0]='1'; $q[0]='1'; $q2[0]=0; $q3[0]=0;
$p_min='1'; $q_min='1'; $z_min=0; $sig="";
for($i1=1;$i1<=$k;$i1++) {
  $k3=bcmul('3',$k3);
  $z2_local=0;
  $k2_orig=$k2;
  while(bccomp($k2,$k3)<0) {
    $k2=bcmul('2',$k2);
    $z2_local++;
  }
  for($i2=1;$i2<$z2_local;$i2++) { $k2_orig=bcmul('2',$k2_orig); }
  if(bccomp(bcmul($k2,$k2_orig),bcmul($k3,$k3))<0) {
    $sig="+";
    $z2_global+=$z2_local;
    $q2[$i1]=$z2_global;
    $q3[$i1]=$q3[$i1-1];
    $er2='1';
    for($i2=0;$i2<$q2[$i1]-$q2[$i1-1];$i2++) { $er2=bcmul('2',$er2); }
    $er3='1';
    for($i2=0;$i2<$q3[$i1];$i2++) { $er3=bcmul('3',$er3); }
    $p[$i1]=bcadd(bcmul($p[$i1-1],$er2),bcmul($k3,$er3));
  } else {
    $sig="-";
    $z2_global=$z2_global+$z2_local-1;
    $k2=$k2_orig;
    $q2[$i1]=$q2[$i1-1];
    $q3[$i1]=$i1;
    $er2='1';
    for($i2=0;$i2<$q2[$i1];$i2++) { $er2=bcmul('2',$er2); }
    $er3='1';
    for($i2=0;$i2<$q3[$i1]-$q3[$i1-1];$i2++) { $er3=bcmul('3',$er3); } 
    $p[$i1]=bcadd(bcmul($p[$i1-1],$er3),bcmul($k2,$er2));
  }
  $w2='1'; $w3='1';
  for($i2=0;$i2<$q2[$i1];$i2++) { $w2=bcmul('2',$w2); }
  for($i2=0;$i2<$q3[$i1];$i2++) { $w3=bcmul('3',$w3); }
  $q[$i1]=bcmul(bcmul($w2,$w3),strval($i1+1));
  if(bccomp(bcmul($p[$i1],$q_min),bcmul($q[$i1],$p_min))<0) { $p_min=$p[$i1]; $q_min=$q[$i1];
  $z_min=$i1; 
  $mu[$z_min]= bcdiv($p_min,$q_min,10);
  }
//  echo $sig." ".$p[$i1]." / ".$q[$i1]."<br>";
}
echo "Minimum ".$z_min.": ".$p_min." / ".$q_min."<br>";
echo "<pre>";
print_r($mu);

der kleinste wert wurde bisher für k=211 mit <math>x<0.8451052997</math> ermittelt (obwohl ich mich frage, ob man für die abschätzung nicht den größten wert nehmen müsste, der wäre dann 7/8 und damit exakt derselbe wie in den anderen überlegungen).

das entspricht wiederum eher meinen abschätzungen, der wert <math>x=0,5\cdots</math> ist immer noch nicht in sicht.

ich lasse jz mal das programm mit k=10000 laufen, aber ich fürchte, viel ändert sich nicht daran. EDIT: das programm lief jz bis k=10.000 und das minimum blieb bei k=211.

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
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.133, eingetragen 2016-12-03 09:56


ich möchte noch folgende ergänzungen zu #132 machen:

allgemein kann der obige mittelwert <math>x</math> durch erweiterung mit einer beliebigen, natürlichen zahl <math>0<l<n</math>, wie folgt geschrieben werden
<math>\displaystyle x=\frac{1}{n} \sum \limits_{k=1}^{n} \frac{a_k^{-1} +a_{k+j_1}^{-1}+a_{k+j_2}^{-1}+\cdots +a_{k+j_l}^{-1}}{l+1}</math>.
dabei sind die <math>0<j_i<n</math> die jeweiligen schrittweiten, die so ausgewählt werden, dass ihre maximalen reziproken verhältnisse besonders klein sind. betrachtet werden also nicht unbedingt die einzelnen schritte nacheinander, sondern bspw. der wert nach 3, dann nach 7 usw. schritten. da alle diese teilmittelwerte die gleiche abschätzung besitzen gilt also
<math>\displaystyle x \le \frac{1}{l+1} (a_{m'}^{-1} + \sum \limits_{k=1}^{l} a_{m'+j_k}^{-1})</math>
für beliebiges m'.

jeder der so erreichten werte ist daher eine obere schranke für <math>x</math>, d.h. wenn wir besonders kleine werte erreichen, sind diese natürlich zu bevorzugen.

besonders klein werden die werte, wenn in
<math>\displaystyle max(\frac{2^{\lfloor k * log_2 3 \rfloor}}{3^k},\frac{3^k}{2^{\lceil k *log_2 3\rceil}})</math>
beide werte etwa gleich gross werden. daraus lässt sich wie folgt eine untere Schranke aller oberen Schranken ermitteln. es ist nämlich mit <math>max(\frac{a}{b},\frac{b}{2a})</math> und <math>\frac{a}{b}=\frac{b}{2a}=\frac{1}{2} \sqrt{2}=0,7071...</math> und dieser wert ist zugleich die untere schranke der oberen schranken von <math>x</math>. man beachte aber, dass dieser wert selbst keine obere schranke ist! trdm zeigt er, was max. zu erreichen möglich ist (mit dieser methode).

eine reale kleine, obere schranke erhält man, wenn man unter den (kettenbruch)approximationen von <math>\log_2 3</math> diejenigen verwendet, deren zähler <math>q_i =2k_i</math> ist. dann sind die besonders kleinen werte von
<math>\displaystyle max(\frac{2^{\lfloor k_i * log_2 3 \rfloor}}{3^{k_i}},\frac{3^{k_i}}{2^{\lceil k_i *log_2 3\rceil}})</math>
zu suchen.

das mache ich jetzt mit nem kleinen programm.


-----------------
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: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.134, eingetragen 2016-12-03 10:11


Ich komme gerade nicht zum Antworten: Nächste Woche will ich meine Diss. abgeben. Ich melde mich dann wieder...

Grüße
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.135, eingetragen 2016-12-03 15:21


@cyrix: viel erfolg :)


-----------------
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
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 2441
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.136, vom Themenstarter, eingetragen 2016-12-05 10:14


@cyrix: ja, viel Erfolg damit!
@astrid: gute Besserung!

Guten Morgen :)

nachdem Jürgen da schon einiges an Vorarbeit geleistet hat, und er/wir uns im Hintergrund immer noch an der Programmierung der 128bit Register abarbeiten, konnte ich nicht anders als eine 64bit Version zu schreiben, bei der das Rechenwerk rein in Assembler ist [1], siehe unten. Ich habe damit auf dem Stand der Dinge aufgesetzt, den wir so um Beitrag #30 herum hatten, also betrachte 9 Reste nach 96 (entsprechend 2^5 und 3^1) und lasse das Ganze auf einem Kern laufen.

Das Ergebnis ist ganz nett: 6sek bis #44 nach Roosendaal, 55sek bis zur 64bit Grenze. Das heisst aus dem Stand eine Verbesserung um Faktor >2 gegenüber unserem damaligen Benchmark. Das Problem dürfte natürlich sein, dass eine Umsetzung der inzwischen vorliegenden Versionen mit der zusammenfassung mehrerer Schritte und der Aufteilung in float Berechnung und exakte Berechnung der letzten Bit recht aufwendig zu programmieren wäre. Es zeigt aber eben anders herum, dass man mit Assembler Programmierung doch noch nen Faktor herausholen kann, und weist einen Weg auf die Erweiterung > 128 bit. Die Frage für mich ist erstmal, ob es Sinn macht, darauf (unter benutzung des Carry Flags und verzicht auf wirkliche 128bit register) eine 128bit Version zu bauen. Wahrscheinlich tue ich es aber einfach die tage, weil... (er eben da war, der berg, den man hinauf muss).

Ausserdem gefällt mir, dass das jetzt ein recht kompakter Code geworden ist :) Ich hab deshalb sogar mal 1-2 kommentare spendiert und variablen umbenannt.

Compilierbar einfach mittels gcc, allerdings ohne die Optimize Stufen, da diese mit dem Inline Assembler nicht klarkommt.

Nach einer Messung an einem "Leerprogramm", das nur aus dem Rahmen in C besteht und bei dem die Assemblerroutine "nichts" macht, verbraucht der in C geschriebene Programmrahmen geschätzt < 1/40 der Rechenzeit, sodass es nicht lohnt, hier zu optimieren.

C und x86 Assembler
#include <stdio.h>
 
// ein paar globale Variablen, hoffentlich selbsterklaerend
unsigned long long start;
unsigned long long start_96;
unsigned long long record;
unsigned long long merkrecord;
int roosendaal_number;
unsigned long starttime;
int was_overflow=0;
 
int reste_96[9]={7,15,27,31,39,59,63,79,91};
int cnt_96=0;
 
// procedure zur Ausgabe der zeitstempel
// aus bisherigem C Programm entnommen
 
void printf_time() {
long nowtime = time(NULL)-starttime;
int now_min = nowtime/60;
int now_sec = nowtime%60;
if (now_min<1) printf("%is",now_sec);
        else printf("%i:%02is",now_min,now_sec);
}
 
// und hier beginnt das hauptprogramm :)
 
int main ()
{
 
        printf("\nCollatz-Testprogramm Assemblerversion \n");
        starttime = (unsigned)time(NULL);
 
        start_96 = 0;
        // da wir hier (3x+1)/2 schritte durchfuehren
        // sind unsere intern ermittelten records nur
        // halb so gross wie die bei Roosendaal gelisteten
        record = 8;
        roosendaal_number = 2;
 
        while (was_overflow<1)
        {
 
        // wir betrachten nur spezielle reste
        start=start_96+reste_96[cnt_96];
        cnt_96++;
        if (cnt_96>8) { cnt_96=0;start_96=start_96+96; }
 
        // und los gehts :)
        merkrecord = record;
 
  asm(
 
                // Vorab die Registerbelegung in der Assembler Routine:
                // r8 : startwert (bleibt erhalten fuer stopp pruefung)
                // r9 : aktueller Folgewert
                // r10 : dessen haelfte fuer (3x+1)/2 schritt
                // r11 : record (wird mitgefuehrt, ursprungs-record wert geht verloren)
 
                // Startwert und bisherigen Record aus RAM in Register kopieren
                  "MOV start(%rip),%r8 \n\t"
                  "MOV record(%rip),%r11 \n\t"
                  "MOV %r8,%r9 \n\t"
 
                // und hier beginnt die Rundreise
                  "collatz_start: \n\t"
 
                // pruefen, ob gerade oder ungerade
                  "TEST $1,%r9 \n\t"
                  "JZ gerade \n\t"
 
                // hier: ungerade. fuehre den (3x+1)/2 Schritt durch.
                // dazu nehmen wir x+x/2 letzteres auf r10 errechnet
                  "MOV %r9,%r10 \n\t"
                  "SHR $1,%r10 \n\t"
 
                // beim addieren kann hier die 64bit Grenze erreicht werden.
                  "ADD %r10,%r9 \n\t"
                  "JO overflow \n\t"
                  "ADD $1,%r9 \n\t"
                  "JO overflow \n\t"
 
                // nach einem (3x+1)/2 Schritt koennte ein neuer Pass Record erreicht sein
                  "CMP %r9,%r11 \n\t"
                  "JG pruefe_fertig \n\t"
 
                // wenn ja diesen aufs passende Register uebertragen
                  "MOV %r9,%r11 \n\t"
                  "JMP pruefe_fertig \n\t"
 
                // nebenbei und weil hier grad platz ist: routine fuer overflow
                  "overflow: \n\t"
                  "MOV $1,%r11 \n\t"
                  "MOV %r11,was_overflow(%rip) \n\t"
                  "JMP fertig \n\t"
 
                // hier: gerade. fuehre den x/2 Schritt durch
                  "gerade: \n\t"
                  "SHR $1,%r9 \n\t"
 
                // so und damit... schauen, ob Stoppwert erreicht. Wenn nicht: naechste runde :)
                  "pruefe_fertig: \n\t"
                  "CMP %r9,%r8 \n\t"
                  "JL collatz_start \n\t"
 
 
                // habe fertig: Register wieder ins RAM kopieren.
                  "fertig: \n\t"
                  "MOV %r11, record(%rip) \n\t"
 
                );
 
//      printf("Checking: %llu returned %llu\n",start,record);
 
        if (record>merkrecord)
                {
                printf_time();
                roosendaal_number++;
                printf(" #%i start=%lli, record==%llu\n",roosendaal_number,start,record*2);
                }
        }
 
printf_time();
printf(" 64bit Grenze erreicht.\n");
}
 

Wie gesagt, die Priorität hieran liegt bei Jürgen, ich hab es nur einfach nicht mehr ausgehalten einen Zwischenstand "fertig zu machen". Wir gehen den Weg weiter :) Und es sollte ja an sich auch möglich sein, diese XMM Register irgendwie sinnvoll zu nutzen (leise fluchend dahergesagt)

gonz

ASCII output
Collatz-Testprogramm Assembler
0s #3 start=7, record==52
0s #4 start=15, record==160
0s #5 start=27, record==9232
0s #6 start=255, record==13120
0s #7 start=447, record==39364
0s #8 start=639, record==41524
0s #9 start=703, record==250504
0s #10 start=1819, record==1276936
0s #11 start=4255, record==6810136
0s #12 start=4591, record==8153620
0s #13 start=9663, record==27114424
0s #14 start=20895, record==50143264
0s #15 start=26623, record==106358020
0s #16 start=31911, record==121012864
0s #17 start=60975, record==593279152
0s #18 start=77671, record==1570824736
0s #19 start=113383, record==2482111348
0s #20 start=138367, record==2798323360
0s #21 start=159487, record==17202377752
0s #22 start=270271, record==24648077896
0s #23 start=665215, record==52483285312
0s #24 start=704511, record==56991483520
0s #25 start=1042431, record==90239155648
0s #26 start=1212415, record==139646736808
0s #27 start=1441407, record==151629574372
0s #28 start=1875711, record==155904349696
0s #29 start=1988859, record==156914378224
0s #30 start=2643183, record==190459818484
0s #31 start=2684647, record==352617812944
0s #32 start=3041127, record==622717901620
0s #33 start=3873535, record==858555169576
0s #34 start=4637979, record==1318802294932
0s #35 start=5656191, record==2412493616608
0s #36 start=6416623, record==4799996945368
0s #37 start=6631675, record==60342610919632
1s #38 start=19638399, record==306296925203752
1s #39 start=38595583, record==474637698851092
1s #40 start=80049391, record==2185143829170100
1s #41 start=120080895, record==3277901576118580
1s #42 start=210964383, record==6404797161121264
2s #43 start=319804831, record==1414236446719942480
6s #44 start=1410123943, record==7125885122794452160
38s #45 start=8528817511, record==18144594937356598024
55s 64bit Grenze erreicht.
 



[1] für die Lesbarkeit: der build-in assembler des gcc, den ich benutze, ist etwas grottig (meine subjektive sicht!), insbesondere werden die operanden in (aus meiner Sicht, "damals...") vertauschter Reihenfolge angegeben also zB MOV source,dest



-----------------
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: 2441
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.137, vom Themenstarter, eingetragen 2016-12-07 10:49


Soooo ... gonz hat den Fehler gefunden und konnte damit auch eine 2x64bit Version zum laufen bringen.

Was in der Version im vorhergehenden post falsch ist: JG gilt für signed Werte, stattdessen ist JA (jump above) zu verwenden wenn man auf unsigned Werte schaut und entsprechend JB (jump below) statt JL.

Damit findet diese Version übrigens auch den Record #46, der zwar bei Roosendaal als 65 bit Record bezeichnet ist, wenn man ein programm verwendet, das konsequent mit unsigned arbeitet und den (3x+1)/2 Schritt durchführt, also intern die Records nur halb so gross sind, wird dieser Wert vor dem Erreichen des Overflow noch berechnet.

aktuell wird #60 auf einem Kern in 1:09 Std erreicht.

Die Parallelisierung ist genauso wie bisher via fork am rechten ort oder durch compilieren von versionen für bestimmte reste einfach möglich.

Eine Version für records > 128 bit ist damit auch gut zu bauen (einfach ein drittes 64bit register in die kette einhängen), wir müssten nur dann eine ausgaberoutine bauen (oder die werte als hexadezimal auswerfen).

Soweit
und einen schönen Weg durch den Tag wünscht

gonz


Das neue Rechenwerk sieht so aus (das umfeld ist gleich ausser den variablentypen)

asm x86
                // Vorab die Registerbelegung in der Assembler Routine:
                // r8 : startwert (bleibt erhalten fuer stopp pruefung)
                // r9,r13 : aktueller Folgewert (niederwertig...hoeherwertig)
                // r10,r14 : dessen haelfte fuer (3x+1)/2 schritt
                // r11,r15 : record (wird mitgefuehrt, ursprungs-record wert geht verloren)
 
                // Startwert und bisherigen Record aus RAM in Register kopieren
                  "MOV start(%rip),%r8 \n\t"
                  "MOV record(%rip),%r11 \n\t"
                  "MOV record+8(%rip),%r15 \n\t"
 
                // Register fuer aktuellen Wert auf Startwert setzen
                  "MOV %r8,%r9 \n\t"
                  "MOV $0,%r13 \n\t"
 
                // und hier beginnt die Rundreise
                  "collatz_start: \n\t"
                  "TEST $1,%r9 \n\t"
                  "JZ gerade \n\t"
 
                // ungerade. fuehre den (3x+1)/2 Schritt durch.
                  "MOV %r9,%r10 \n\t"
                  "MOV %r13,%r14 \n\t"
                  "SHR $1,%r14 \n\t"   // hoeherwertig - und ins carry
                  "RCR $1,%r10 \n\t"   // niederwertiges uebernimmt carry
                  "ADD %r10,%r9 \n\t"  // niederwertig - und ins carry
                  "ADC %r14,%r13 \n\t" // hoeherwert uebernimmt carry
                  "ADD $1,%r9 \n\t"    // niederwertig - und ins carry
                  "ADC $0,%r13 \n\t"   // hoeherwertig - und uebernimmt carry
 
                // nach einem (3x+1)/2 Schritt koennte ein neuer Pass Record erreicht sein
                  "CMP %r13,%r15 \n\t"
                  "JA collatz_start \n\t"
                  "JB do_record \n\t"
                  "CMP %r9,%r11 \n\t"
                  "JA collatz_start \n\t"
 
                // wenn ja diesen vermerken
                  "do_record: \n\t"
                  "MOV %r9,%r11 \n\t"
                  "MOV %r13,%r15 \n\t"
                  "JMP collatz_start \n\t"
 
                  "gerade: \n\t"
                // fuehre den x/2 Schritt durch
                  "SHR $1,%r13 \n\t"
                  "RCR $1,%r9 \n\t"
 
                // Stoppwert erreicht? Wenn nicht: naechste runde :)
                  "CMP $0,%r13 \n\t"
                  "JNZ collatz_start \n\t"
                  "CMP %r8,%r9 \n\t"
                  "JA collatz_start \n\t"
 
                // habe fertig: Register zurueck ins RAM
                  "MOV %r11, record(%rip) \n\t"
                  "MOV %r15, record+8(%rip) \n\t"



-----------------
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: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.138, eingetragen 2016-12-09 11:08


So, die Arbeit ist abgegeben, aber die nächsten Schritte fordern auch schon ihren Tribut: Wohnungssuche, Umzugsplanung usw.

Deshalb jetzt auch nur ganz kurz:

@trunx, zu deinen Beiträgen 132 und 133: Dies sieht erst einmal ganz gut aus. Um aber bessere Schranken zu erhalten, betrachte ich nicht nur - wie du das in den Beiträgen erläuterst - einige "Vorwärts-Iterationen", sondern u.A. auch "Rückwärts-Iterationen": Wenn ich weiß, dass vor einem Folgenglied ein deutlich kleineres kommen muss; und ich weiß, dass dieses kleinere dennoch mindestens so groß wie die Schranke, von der ich angenommen habe, dass keine Startzahl <= dieser in einen nichttrivialen Zyklus mündet, ist, dann ist mein betrachtetes Folgenglied auch einen entsprechenden Faktor größer.

Des Weiteren kann ich auch folgenden Fakt ausnutzen: Ist der kleinste Repräsentant einer Restklasse schon > der betrachteten Schranke, dann gilt das natürlich auch für jeden anderen. Hier geht also - anders als in deiner Überlegung - ein absoluter [!] und nicht nur ein relativer Wert ein. (Deshalb ist meine Rechnung auch massiv abhängig von der oben postulierten Schranke von 110*2^60; wählt man einen höheren Wert, dann kann man auch nur "weniger" zeigen, i.S. des Faktors "Durchschnittsreziproke < q * 1/m".)


Diese beiden Überlegungen schließen vermehrt die Folgen, die bei dir die jeweils bestmöglichen Schranken defienieren, nämlich diejenigen, bei denen sich "x/2"- und "(3x+1)"-Schritte im Verhältnis nahezu log 3 : log 2 "abwechseln", sodass man nie allzuweit weg vom Startwert kommt, aus. Deshalb komme ich auf bessere Ergebnisse.

Beispielbetrachtung: Du hast eine Folge der Länge 211 betrachtet. Das liefert eine Restklasse modulo 2^211, in der die Startzahl sein muss, damit die Folge von Halbierungs- und "Verdreifachungs-Schritten" genau so kommt, wie du sie in deiner Folge betrachtet hast. Diese Restklasse hat aber fast sicher (ich habe es nur nicht nachgerechnet) nur Repräsentanten, die deutlich grßer als 110*2^60 sind. D.h., deren durchschnittliche Reziproken sind deutlich kleiner als der Wert von 1/(217*2^60), den wir für den zu zeigende Satz brauchen. Insofern stellt die in dieser Folge betrachtete Abfolge von Halbierungs- und "Verdreifachungs-Schritten" kein Problem mehr dar, da sie einen Wert deutlich kleiner als benötigt liefert.


Ich hoffe, das Vorgehen wird damit etwas klarer.

Viele Grüße
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.139, eingetragen 2016-12-14 20:37


@cyrix: vielen Dank für deine Mühe, aber leider wird das nix mit meinem Verständnis. 2^211 da kann ich nichts rechnen.
Wenn du doch mal iwann Zeit haben solltest, dann wäre eine deutlich kleinere Schrittweite besser, z.B. 6, die Reste von 2^6 sind überschaubar, und als Folge könnte man c(27) nehmen, T^6(27) wäre 161 usw., auch wenn die nicht zyklisch ist, aber halt fürs Prinzip.
Aber wie gesagt, es eilt nicht und du hast Wichtigeres vor :)


-----------------
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: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.140, eingetragen 2016-12-15 04:58


Die Betrachtung modulo großer Zweierpotenzen ist aber essentiell.

Machen wir trotzdem mal ein kleineres Beispiel:

Damit für eine Startzahl u die nächsten 3 Berechnungs-Schritte in der Collatz-Folge in dieser Reihenfolge "x/2", "(3x+1)/2" und "(3x+1)/2" sind, muss <math>u \equiv 6\pmod{8}</math> gelten:

Seien nämlich <math>u=a_0</math>, <math>a_1=\frac{a_0}{2}</math>, <math>a_2=\frac{3a_1+1}{2}</math> und <math>a_3=\frac{3a_2+1}{2}</math> die entsprechenden Folgenglieder der Collatz-Folge, so muss ja insbesondere, damit <math>a_3</math> entsprechend gebildet wird, <math>a_2 \equiv 1 \pmod{2}</math> sein. Daraus erhält man, dass <math>3a_1+1\equiv 2 \pmod{4}</math> und also <math>a_1\equiv 3\pmod{4}</math> ist und schließlich <math>u=a_0\equiv 6 \pmod{8}</math>.

Auf diese Weise entspricht jede Folge von insgesamt k ("x/2"- und "(3x+1)/2"-Schritten) genau einer Restklasse modulo 2^k, in die der Startwert fallen muss, damit dessen nächsten k Operationen in der mit ihm beginnenden Collatz-Folge so aussehen, wie wir es gerade gefordert haben.

Wenn wir also nun für eine solche Folge von Schritten, wie du sie etwa in deinen Beispielen beschreibst, die entsprechende Restklasse ermitteln, dann stellt sich oft heraus, dass selbst die kleinsten positiven Repräsentanten viel größer sind als die Schranke, die wir für unseren Satz brauchen: Wenn der durchschnittliche Reziproke unter den ungeraden Werten der gerade betrachteten Teilfolge < 1/(217*2^60) ist, dann sind wir mit dieser Teilfolge fertig, denn die erfüllt das Gewünschte.

Wichtig ist zu bemerken, dass dies eine Betrachtung der absoluten Größe der (ungeraden) Folgenglieder ist, nicht mehr nur eine relative der Form ... < c * 1/m, wobei m der minimale Wert der Folge sei.


Vielleicht wird es jetzt klarer.

Grüße
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.141, eingetragen 2016-12-15 05:48


Oder um es noch etwas plastischer zu machen: Mal angenommen, wir wollten nicht zeigen, dass der durchschnittliche Reziproke < 1/(217*2^60), sondern nur < 1/13 ist. (Dies soll hier als Beispielaussage herhalten, damit der Gedanke hinter dem Vorgehen im Beweis der eigentlichen Aussage verständlicher wird.)

Dann betrachten wir nun nacheinander alle ungeraden Restklassen modulo 16, in die eine Startzahl einer Teilfolge unseres Zyklus' fallen kann. Dies sei am Beispiel <math>u\equiv 11 \pmod{16}</math> genauer ausgeführt:

Ist <math>u=a_0=16k+11</math>, so sind die nächsten Folgenglieder <math>a_1=24k+17</math>, <math>a_2=36k+26</math>, <math>a_3=18k+13</math> und <math>a_4=27k+20</math>. Insbesondere sind <math>a_0</math>, <math>a_1</math> und <math>a_3</math> ungerade, d.h., der "durchschnittliche Reziproke" der ungeraden Folgenglieder dieser Teilfolge (<math>a_0</math> bis <math>a_3</math>) ist <math>S_{11}=\frac{1}{3}\cdot\left(\frac{1}{a_0}+\frac{1}{a_1}+\frac{1}{a_3}\right)</math>.

Nun sind diese Folgenglieder minimal positiv für k=0. Also ist <math>S_{11}\leq \frac{1}{3}\cdot\left(\frac{1}{11}+\frac{1}{17}+\frac{1}{13}\right)<\frac{1}{13,23}<\frac{1}{13}</math>.

Wenn wir jetz für jede Restklasse, in der die Startzahl einer Teilfolge fallen kann, analog zeigen können, dass der "durchschnittliche Reziproke" in dieser Teilfolge <1/13 ist, dann sind wir fertig: Nach dem Ende einer Teilfolge beginnen wir die nächste, in deren Teilbereich dies auch gilt, usw.


Dieser Ansatz wirkt mit den kleinen Zahlen jetzt nicht so spektakulär. Interessant ist aber, dass er in gewissem Sinne "orthogonal" zu dem auch von trunx oben verfolgten verläuft: Dort sind ganz bestimmte Folgen von Schritten, ob nun halbiert oder "verdreifacht" werden soll, kritisch. Diese gehören aber zu Restklassen modulo großer Zweierpotenzen und besitzen allermeist nur Repräsentanten, die schon für sich genommen riesig sind. Damit kann dieser Ansatz diese Restklassen (und damit kritischen Teilfolgen) aussortieren; und so die Kombination von beiden Ansätzen zusammen deutlich bessere Ergebnisse erzielen.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.142, eingetragen 2016-12-15 09:16


vielen dank cyrix, jetzt ist mir dein vorgehen endlich klar geworden.
ich rechne dann jz mal deinen beweis durch, aber ich denke, das wird schon ok so sein.

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
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.143, eingetragen 2016-12-15 18:03


sry gonz, dass ich noch weiter auf der theorie rumhacke, was du machst sieht auch super aus :)

@cyrix: wie gesagt, ich habe ja jz deinen beweisansatz so weit verstanden. ich denke, du brauchst den fall der teilfolge < 128 nicht berücksichtigen, da er nicht existiert (einfach weil man die folge "vervielfältigen" kann, ohne den durchschnitt zu ändern). aber eine andere frage: warum nimmst du ausgerechnet 128 schritte? nur damit die reste größer sind? das ist glaube nicht nötig. hast du den überblick, was an mittelwerten für kleinere schrittweiten rauskommt?


-----------------
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: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.144, eingetragen 2016-12-15 19:24


Hallo trunx,

2016-12-15 18:03 - trunx in Beitrag No. 143 schreibt:
ich denke, du brauchst den fall der teilfolge < 128 nicht berücksichtigen, da er nicht existiert (einfach weil man die folge "vervielfältigen" kann, ohne den durchschnitt zu ändern).

ja, das ist mir heute früh - beim Schreiben der obigen Beiträge - auch aufgefallen. :) Durch das mehrfache Durchlaufen des Zyklus' kann man den Einfluss des einzelnen, letzten "Rest-Stücks" unter jede positive Schranke drücken.


aber eine andere frage: warum nimmst du ausgerechnet 128 schritte? nur damit die reste größer sind? das ist glaube nicht nötig. hast du den überblick, was an mittelwerten für kleinere schrittweiten rauskommt?

Warum gerade 128 Schritte? Weil das das Maximum war, was ich auf die Schnelle aus dem Programm herausholen konnte. ;) (Insbesondere weil eben so die Restklasse in einen unsigned 128-Bit-Integer gepasst hat, ohne, dass ich mir da Gedanken über Überläufe machen musste.)

Und warum so groß wie möglich? Nun, nach Konstruktion ist die Schranke, die man für "den maximalen durchschnittlichen Reziproken" erhält, monoton fallend in der Länge der maximal betrachteten Folgenglieder: Entweder mit dem nächsten Folgenglied erhält man einen besseren Wert; oder man bleibt beim alten. (Deshalb wird der ganze Zyklus nur in Abschnitte variabler, maximal 128 Folgenglieder umfassende, Länge eingeteilt, nicht in feste je 128 Folgenglieder. So kann ich nämlich z.B. bei Startzahlen der Form 8k+7 direkt nach den erten drei ungeraden Folgengliedern aufhören, da diese allein schon ein "durchschnittliches Reziproke" kleiner dem gewünschten Schwellwert besitzen.) Insofern gilt: Je mehr Schritte betrachtet werden, desto besser die Schranken, die man erhalten kann.

Ich mache bei Gelegenheit mal Testläufe für kleinere Anzahlen an maximal betrachteten Folgengliedern in einem solchen Bereich. (Hatte ich beim Schreiben des Programms schon gemacht, die Daten aber gerade nicht mehr zur Hand.)


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.145, eingetragen 2016-12-15 21:01


ich habe jz die mittelwerte für die schrittweiten 2-6 per hand berechnet, um ein gefühl dafür zu bekommen, wie man das programmiert, hmm ist mir noch nicht geglückt. anyway, meine frage nach der größe der schrittweite hat den hintergrund, dass ich nicht glaube, dass der mittelwert monoton mit der länge der schrittweite fällt, sondern dass man durchaus auch sehr niedrige werte für kleinere schrittweiten bekommt. jedenfalls sind die werte für
k=2: 0,833333333
k=3: 0,875
k=4: 0,851851852
k=5: 0,805555556
k=6: 0,826388889
tendenziell wird das sicher kleiner werden, aber eben um dieses kleiner-werden herum schwanken. es wäre daher gewissermassen "glück", dass der wert für 128 so gering ausfällt.

EDIT: programm läuft...


-----------------
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
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.146, eingetragen 2016-12-16 08:37


moin, moin
ich glaube, ich bin jz soweit mit cyrix' beweis durch, um mein anfängliches unbehagen besser in worte fassen zu können. trdm möchte ich ausdrücklich sagen, dass ich die idee gut finde, sonst würde ich mich nicht so damit beschäftigen :)

die ganze mittelwertberechnung basiert ja zunächst auf betrachtung der ungeraden reste zu bestimmten klassen.

bsp: mod 16
1: 16k+1, 24k+2, 12k+1, 18k+2,| 9k+1
3: 16k+3, 24k+5, 36k+8, 18k+4,| 9k+2
...
11: 16k+11, 24k+17, 36k+26, 18k+13,|...
13: 16k+13, 24k+20, 12k+10, 6k+5,|...
15: ...

daher enthalten die reziproken verhältnisse zunächst auch k
fed-Code einblenden
um nur einige zu nennen (berechnet habe ich sie natürlich alle)

für die ersten repräsentanten, also k=0, 1, 2, usw. sind diese werte natürlich verschieden vom grenzwert <math>k\rightarrow\infty</math>.
für das beispiel sind die unterschiede erstaunlicherweise nicht soo groß, wie man vermuten könnte, sie liegen durchaus in der nähe und fallen bzw. steigen monoton (welcher rest wie ist unklar) richtung grenzwert.

für das beispiel erhält man für den rest 11 den größten mittelwert, sowohl für k=0 (wenn man den rest 1 systematisch ausschliesst), als auch im grenzwert. das eine mal sind es 0,831... der grenzwert ist 0,851...

mein programm hat nun bis schrittweiten 27 die grenzwerte berechnet (es ist nicht doll, ich weiss, ich programmiere mit php und lass das von der konsole laufen, aber die performance ist natürlich furchtbar :D). jedenfalls ist dort das minimum für mod 2^18 mit 0,7461... was ich jedoch nicht weiss, ist, ob ich diesen wert von oben bzw. unten erreiche.

so wie es aussieht, hast du, cyrix, dagegen die werte für kleine k bzw. sogar für k=0 berechnet(?). daher meine frage, ob du für kleine potenzen werte hast, damit man das besser einschätzen kann.

so, und jz zum punkt :)
dieser grenzwert wird erst nahezu realisiert, wenn k eine nennenswerte größe hat bspw. 2^10, also ein faktor 1000. d.h. der mittelwert gilt bei dir erst in einem bereich > 2^138 wird aber für den bereich > 2^60 benutzt.

auch da würde wiederum helfen, die kleineren werte zu kennen, also bis ca. 2^50.

habt einen schönen tag
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
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.147, eingetragen 2016-12-16 14:04


www.mikrocontroller.net/topic/413678#4830918



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


@trunx: Am Ende erhalte ich keine relativen Werte "durchschnittliches Reziproke" < c * 1/m, sondern absolute ...  < 1/(217*2^60); unter der Voraussetzung, dass kein Startwert < 110*2^60 in einen nicht-trivialen Zyklus führt. Und mehr will ich auch gar nicht zeigen, da dieser Wert für die neue untere Schranke, wie lang ein nicht-trivialer Zyklus denn mindestens sein muss, ausreicht.

Insbesondere kann ich mich also auf k=0 beschränken, da für größere k der absolte Wert des betrachteten Reziproken nur noch kleiner wird.


Grüße
Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
cyrix
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 31.07.2004
Mitteilungen: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.149, eingetragen 2016-12-17 16:19


Dann mal einige Werte, die alle Optimierungen in dem Verfahren gemäß des Prgramms in Beitrag #88 benutzen. Dabei wird der Zyklus in Abschnitte der Länge maximal k aufeinanderfolgende Folgenglieder zerlegt. Angenommen wird jeweils, dass keine Startzahl < 1,27*10^20 in einen nicht-trivialen Zyklus führt. Angegeben ist dann der maximale Wert, den ich als obere Abschätzung des "durchschnittlichen Reziproken" eines ungeraden Folgenglieds unter den Restklassen mod 2^k der Startzahlen eines jeden solchen Abschnitts erhalte; und zwar in der Form c * 1/(1,27*10^20):

<math>
\begin{tabular}{ll}
k  & c \\
5 & 0.787116 \\
10 & 0.747731 \\
20 & 0.742210 \\
30 & 0.740874\\
40 & 0.737215\\
50 & 0.735581\\
60 & 0.732265\\
70 & 0.723668\\
80 & 0.699251\\
90 & 0.687161\\
100 & 0.661881\\
110 & 0.635674\\
120 & 0.596223\\
128 & 0.584412\\
\end{tabular}
</math>

edit: Das sind jeweils obere Abschätzungen, da ich Sicherheiten bei der Berechnung mit Gleitkomma-Zahlen ins Programm eingebaut habe, um sicher obere Abschätzungen zu erhalten.

Das Sinken der Werte am Anfang kommt erst einmal nur durch die relativen Überlegungen (Vorwärtsiterationen, wie sie auch trunx betrachtet, aber auch Rückwärtsiterationen) zu Stande, d.h., sie gelten unabhängig von der geforderten Schranke.

Ab k=70 jedoch fangen jedoch die absoluten Betrachtungen an, zu Buche zu schlagen: Wenn nämlich die kleinsten Repräsentanten einer Restklasse schon deutlich größer als 2,17*2^20 sind, dann werden auch die betrachteten Reziproken deutlich kleiner als 1/(2,17*2^20), müssen also nicht weiter berücksichtigt werden.

Insbesondere reicht der für k=128 gezeigte Wert für die Schranke im Satz.


btw, um noch ein mögliches Missverständnis auszuräumen: Sei mal <math>a_1, a_2, \dots </math> die entsprechende Collatz-Folge eines nicht-triialen Zyklus'. Dann zerlege ich diese in nicht gleich große Teil-Abschnitte derart, dass in jedem Teilaschnitt das "durchschnittliche Reziproke" der ungeraden Folgenglieder dieses Teilabschnitts < c * 1/(1,27*10^20) ist. Wenn das schon ein Abschnitt der Länge 5 tut, dann breche ich da ab, und beginne mit dem nächsten darauf folgenden Folgenglied den nächsten Abschnitt.

Das führt dazu, dass automatisch der Wert c monoton sinkend in der maximal betrachteten Länge k solcher Abschnitte sein muss: Wenn ein Anfangsstück einer Folge schon die zu zeigende Bedingung erfüllt, dann ist ja alles nachfolgende egal, da dies schon im nächsten Abschnitt liegt.


Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.150, eingetragen 2016-12-19 23:37


hallo cyrix,
ein weiteres mal dank an dich für deine mühe.
leider kann ich nicht einen deiner werte reproduzieren.
nehmen wir der einfachheit halber k=5.
bei mir ist 25 die restklasse mit dem höchsten reziprokendurchschnitt.
genauer habe ich folgende folge:
32n+25,48n+38,24n+19,36n+29,54n+44,|27n+22
woraus ich folgenden reziprokenmittelwert bilde:
<math>\frac{1}{3}(\frac{1}{24n+18}+\frac{1}{32n+25}+\frac{1}{36n+29})=\frac{1}{3}(1+\frac{24n+19}{32n+25}+\frac{24n+19}{36n+29})\cdot\frac{1}{24n+19} \ge c \frac{1}{m}</math>
für k=0 erhalte ich c=0,80505...
mit grösser werdenden k steigt c an, sd. für <math>k\rightarrow\infty</math> c=0.8055555... wird.
auch für die anderen werte erhalte ich höhere werte für c.
für welche restklasse erhältst du denn bei k=5 dein c?
(für k=10 ist die restklasse 1101101011 und für k=20 11011010110110101101; die genauen werte könnte ich noch ermitteln)


-----------------
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: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.151, eingetragen 2016-12-20 00:24


Hallo trunx,

wie schon geschrieben, gehen hier weitere Überlegungen ein. Betrachten wir die Restklasse 25 (mod 32), dann sehen die nächsten Folgenglieder aus, wie du es beschreibst.

Wir bemerken, dass 24n+19 der minimale Wert in dieser Liste ist. Dieser ist also >= m, wobei mit m hier die gezeigte Schranke, unterhalb derer keine Startzahl in einen nicht-trivialen Zyklus führt, bezeichnet sei.

Dann ist <math>32n+25 \geq \frac{4m-1}{3} = \frac{4}{3} m - \frac{1}{3} = \frac{4}{3} m \cdot \left(1 - \frac{1}{4m}\right) = \frac{4}{3} m \cdot \left(1 - \epsilon\right)</math> mit <math>\epsilon= \frac{1}{4m}</math>.

Insbesondere ist also <math>\frac{1}{32n+5} \leq \frac{3}{4} \cdot \frac{1}{1-\epsilon} \cdot \frac{1}{m} < 0,76 \cdot \frac{1}{m}</math> für unsere betrachteten Werte von <math>m > 10^{20}</math>.

Wenn ich den entsprechenden Teilabschnitt, der mit einer ungeraden Zahl aus der Restklasse 25 mod (32) beginnt, schon nach diesem Wert wieder abbreche, dann ist der "durchschnittliche Reziproke" in diesem Abschnitt also kleiner als <math>0,76 \cdot \frac{1}{m}</math>. Der nächste Abschnitt beginnt dann mit dem nächsten ungeraden Folgenglied.

edit: Wie du siehst, schätze ich das kleinste Folgenglied nach unten durch m ab. Wenn ich aber weiß, dass dieses kleinste Folgenglied die Form "irgendwas * n + große_Zahl" hat, wobei "große Zahl" selbst schon > m ist, dann kann ich besser dieses Folgenglied durch "große_Zahl" nach unten hin abschätzen. Das mache ich aber natürlich nur genau dann, wenn es besser ist, als mit m selbst zu arbeiten...

edit2: Der maximale Wert des "durchschnittlichen Reziproken" sollte bei k=5 von der Restklase 27 mod (32) angenommen werden und 0,787037 betragen. "Sollte", da das Programm auf Effektivität getrimmt ist, und auch alle Restklassen schon aussortiert, für die ein Anfangsstück höchstens den Faktor 1,001 schlechtere Ergebnisse als dieser Maximalwert liefert. Damit kann ich nicht ausschließen, dass es Restklassen gibt, die ein höheres "durchschnittliches Reziproke" besitzen; aber dieser ist dann höchstens 0,787037 * 1,001 = 0,787116.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.152, eingetragen 2016-12-20 08:42


du benutzt also 24n+19 um das reziproke von 32n+25 abzuschätzen, aber lässt es bei der mittelwertbildung aussen vor.
bei mir ist dieser minimale wert immer teil der mittelwertbildung, als reziprokes erscheint es dort als die 1 am anfang.
hier wäre also (1+3/4)/2 = 7/8 zu rechnen.
und wegen dieser 1 fallen alle meine mittelwerte höher aus als bei dir. warum lässt du sie weg?


-----------------
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: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.153, eingetragen 2016-12-20 10:01


Warum lasse ich es weg? Weil es einen größeren, und damit nicht optimalen, Wert erzeugt...

Ich nehme das Anfangsstück, welches den kleinsten Wert für "das durchschnittliche Reziproke" besitzt; bzw. genauer: das erste solche Anfangsstück, was einen entsprechenden Wert kleiner dem (1,0001-fachen des) bisher gefundenen Maximum(s) besitzt.

Cyrix



  Profil  Quote  Link auf diesen Beitrag Link
trunx
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.08.2003
Mitteilungen: 2585
Aus: Berlin
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.154, eingetragen 2016-12-20 11:04


die 1 gehört zum anfangsstück.
bei der mittelwertabschätzung kann man natürlich mal zu grosse ausreißer weglassen, aber das trifft hier nicht zu. die 1 ist als referenzwert der bezug zu allen anderen relativen werten und daher essentiell.
ich glaub, jz haben wir den grund, warum deine mittelwerte nach mm. zu klein sind (natürlich kann ich mich auch irren, was auch ok wäre).


-----------------
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: 2326
Aus: Flensburg
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.155, eingetragen 2016-12-20 11:23


Hallo trunx,
nein, das passt schon so.

Ziel war es, den nicht-trivialen Zyklus in Abschnitte zu unterteilen, sodass in jedem Abschnitt das "durchschnittliche Reziproke" höchstens c  * 1/m ist. Für k=5 haben wir c=0,78116.

Dabei besteht ein Abschnitt, der mit einem Startwert kongruent 1 (mod 8) beginnt (also etwa die Zahlen, die auch 25 (mod 32) sind), aus nur genau diesem Folgenglied, da wir für diesen Abschnitt genau die obige Aussage zeigen können: Das "durchschnittliche Reziproke" in diesem Abschnitt ist eben genau das einzige darin vorhandene und hat einen Wert < 0,76 * 1/m.

Das nächste ungerade Folgenglied stellt dann den Anfang des nächsten Abschnitts dar. Dass wir zwar nun zusätzlich wissen, dass dieses dann die Form 24n+19 haben muss, stört ja nicht weiter: Wir ignorieren dieses Wissen einfach (und erhalten damit höchstens eine schlechtere Abschätzung, als mit diesem Wissen möglich wäre). Trotzdem ändert sich nichts daran, dass wir mit dem dann erhaltenen Wert eine obere Abschätzung erhalten.


Cyrix



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


Guten Morgen :)

Ich fasse mal zusammen wo ich so stehe mit der Sache.

a) Cyrix Algo und C-Programm

Mit der hier vorgestellten Implementierung von Cyrix sind wir - Astrid hat erheblich Rechenleistung beigesteuert - auf 50 Kernen nach 581 Stunden Rechenzeit bei der #82 nach Roosendaal angelandet - das sind 24 Tage oder 3,5 Wochen. Damit kann man einfach hochrechnen, wie lange wir zum Nachstellen des Projektes von Tomás Oliveira e Silva bräuchten, etwa achtmal so lange entsprechend über einem halben Jahr. Würde das etwas neues und Erkenntnisgewinn bringen, dann würden wir es laufen lassen, aber so - habe ich das Ganze gestoppt und warte darauf, dass sich ggf. eine nochmal um einen merklichen Faktor beschleunigte Version ergibt.

Ein möglicher Faktor wäre eine weitere Verteilung auf mehr beteiligte Rechner. Ich möchte deshalb einfach mal in die Runde fragen, wer Lust hätte, ein solches Programm auf einem oder gar mehreren Kern(en) einer (Linux-) Maschine bei sich laufen zu lassen, dh auf einem zeitgemässen Rechner 1/4 der Rechenleistung für so ein Projekt beizusteuern. Wenn sich da Interessenten finden, würden wir einzelne Reste an einzelne Leute verteilen, erst einmal rein informell und "händisch", und dann das ganze automatisieren bzw. via WWW ein Netzwerk dafür aufbauen, wenn uns der Verwaltungsaufwand lästig wird. Ich würde das Programm dazu auch Restart-fähig machen, sodass man nicht durchgängig die Maschine(n) laufen lassen muss. Sollten wir damit versuchen, den nächsten Record nach der #89 anzugehen, könnten wir die Reste verlosen und einen Preis für den glücklichen Gewinner auslosen, dessen Rechner... (einfach nur wegen dem Spassfaktor).

Weitere Frage dazu: Wäre es einfacher, da Rechenleistung zu bekommen, wenn es auch eine fix und fertig zu benutzende Windows Variante gäbe?

b) Programmierung brute force in Assembler

Nicht ganz so fix ist das was ich aktuell in Assembler habe, weil meine Assembler Version aktuell nur auf dem Aussortieren von Restklassen nach 3*2^n beruht und alle weiterführenden Finessen des Cyrix'schen Algos nicht nutzt. Dafür bekomme ich sehr kompakten Code, und liege nach aktueller Abschätzung um Faktor 3-4 hinter dem was Variante a) bringt. Ich persönlich verfolge diesen Weg eher deshalb, weil ich damit meine Kenntnisse in Assembler Programmierung mal auf den Stand der Zeit bringen kann (das letzte was ich "damals" gemacht habe lief auf 386 bzw. mc51). Was ich da inzwischen herausgefunden habe kommt nachher in gesondertem Post. Juergen wünscht sich dieses Programm noch in einer fork-parallelisierten Version, die werde ich, weils eigentlich recht einfach geht nach dem bekannten Verfahren, in den nächsten Tagen bereitstellen, und auch nochmal eine genaueren Benchmark machen, um herauszufinden, wie gross der Faktor wirklich zwischen a) und b) ist und ggf. welcher Anteil daran am Algorithmus liegt, und welcher an der Implementierung in Assembler.

Denn: man könnte natürlich versuchen, den Algorithmus aus a) nach Art von b) in Assembler zu giessen, aber das wäre einfach mit einer Menge an Mühe verbunden, von der ich noch nicht wirklich einschätzen kann, ob es Sinn macht.

c) FPGA: Ich lausche gebannt der Diskussion auf microcontroller.net, es sieht so aus, als wenn man insgesamt unter Einsatz eines Clusters aus FPGA auf eine Verbesserung von max. Faktor 10 kommen würde. Das heisst für mich als persönliche Einschätzung: Das bringt es eigentlich nur, wenn ich es als Projekt zur Erforschung dieses an sich spannenden Themas sehe. Ggf. wird das aber angegangen.

d) GPU: Bleibt spannend, für mich aber noch kein definitiver Stand. Gefühlt wäre es vom erreichten Durchsatz gleichwertig, auf einer GraKa (die finanzierbar ist) zu arbeiten oder ein kleines Netzwerk aus Servern und CPU nutzung laufen zu haben, wie wir es jetzt betreiben. Auch hier gilt, dass ich den bisher vorgetragenen Meinungen entnehme, dass wir ggf. einen Faktor von 10 gewinnen könnten. Es wäre dort auch die Frage, ob man es (mangels breiter register) hinbekommt, einen komplexen algo nach a) zu implementieren, oder ob man nicht register zusammenbasteln müsste und damit - mit dem entsprechenden performance verlust - auf eine lösung nach b) kommen würde.

Soweit als zusammenfassung und zum start in den tag - ich geh mal kaffee kochen und dann schreib ich noch was zur aktuellen asm version :)

have fun!
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: 2441
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.157, vom Themenstarter, eingetragen 2016-12-21 08:37


So... gonzens goes assembler :)

Eine Erkenntnis ist, dass es auf aktuellen Prozessoren durch die Pipeline gar nicht so teuer ist, viel "herumzurechnen", weil das eben einfach parallel ausgeführt wird, sondern dass die Sprünge teuer sind, weil da entweder eine prediction über das Sprungziel gemacht wird, die falsch sein kann und dann sehr teuer wird, oder man zumindest das berechnen beider zweige und nachfolgende rückwirkende entscheidung benötigt. Eine Version, in der ich den (3x+1)/2 zweig und den /2 zweig gleichzeitig bereche spart da bedingte sprünge, und ich bin auf die idee gekommen, dass ich die entscheidung eh aus dem Carry ableiten kann, das beim shiften nebenbei abfällt.

Die folgende Version der Rechenschleife spart gut 25%:
x86 Assembler
// r9,r13 : aktueller Folgewert (niederwertig-hoeherwertig)
// r10,r14 : haelfte dessen
// r11,r15 : candidate record
// rax : null (da komischerweise cmovnc nicht mit konstante geht)
 
// Startwert aus RAM in Register kopieren und register vorbereiten
  "MOV start(%rip),%r8 \n\t"
  "MOV %r8,%r9 \n\t"
  "MOV $0,%r11 \n\t"
  "MOV $0,%r13 \n\t"
  "MOV $0,%r15 \n\t"
  "XOR %rax,%rax \n\t"
 
// auf gehts! lets do the collatz ...
  "collatz_start: \n\t"
 
// auf r10,14 eine kopie des aktuellen wertes
  "MOV %r13,%r14 \n\t"
  "MOV %r9,%r10 \n\t"
// halbieren diese
  "SHR $1,%r14 \n\t"   // shr+rcr rotiert ueber und in das carry
  "RCR $1,%r10 \n\t"
// aus dem Carry kann man jetzt entnehmen ob gerade oder ungerade
// wenn der gerade fall loeschen des bisherigen Folgenwertes
  "CMOVNC %rax,%r13 \n\t"
  "CMOVNC %rax,%r9 \n\t"
// fuer "ungerade": carry is set, auf r9,13 der bisherige wert
// fuer "gerade": carry clear und r9/13 geloescht :)
  "ADC %r10,%r9 \n\t"   addieren uebers/mit/ins carry
  "ADC %r14,%r13 \n\t"
// habe fertig: auf 9,13 steht jetzt der neue folgewert.
// ueberlaufprüfung würde das carry prüfen, das spare ich mir 

Ok und die zweite verbesserung: es "kostet" einiges, in jedem (zumindest ansteigenden) folgeschritt mit dem record zu vergleichen. da eh nach dem durchlauf im C programmg geprüft wird, ob der neue wert höher ist als der vermerkte, reicht es, einen ungefähren anhaltswert zu haben. zu diesem zweck bilde ich das OR-Produkt aller folgeglieder (was ohne verzweigung oder bedingtes geht) und prüfe erst nach dem durchlauf, welches das höchste gesetzte bit ist. Damit erziele ich nochmal so an die 10%.

so und damit teil 2:

record candidate mittels or, und
prüfen auf stoppwert.
an letzterem kaue ich noch, das ist teuer wie es da steht.
x86 asm
// Record Candidate updaten
  "OR %r13,%r15 \n\t"
  "OR %r9,%r11 \n\t"
// Stoppwert erreicht? kleiner 64bit stoppwert vorausgesetzt
  "CMP $0,%r13 \n\t"
  "JNZ collatz_start \n\t"
  "CMP %r8,%r9 \n\t"
  "JA    collatz_start \n\t"
// habe fertig: record candidate ins RAM kopieren.
  "MOV %r11, record(%rip) \n\t"
  "MOV %r15, record+8(%rip) \n\t"
 



In Summe bin ich mit der Asm Version jetzt soweit, dass ich auf einem Server (der mit 12 Kernen) das L&V Programm, also bis zur #63 nach Roosendaal, in 1/2 Stunde gerechnet bekomme. Eventuell baue ich wenn mir nichts weiteres mehr dazu einfällt nochmal eine "Schmuckversion", bei der ein Thread nachgeschaltet die zu viel ausgeworfenen Candidate Records aussortieren, und die nen bissl besser dokumentiert ist und bzgl. der anzahl der zur Verfügung stehenden Kerne konfigurierbar... Sozusagen "L&V kompakt".

Soooooo und nun...
sollte ich mal was sinnvolles tun sprich - die Arbeit ruft.

einen schönen Tag wünscht
gonz

PS.: Und damit zum Zeithorizont. Zwischen L&V und dem Ende des bei Roosendaal dokumentierten liegt ein Faktor von 2^17. Da ich mit Hilfe von Zusatzkernen aus dem Astrid Pool (Faktor 5) und von 1/2 auf Stunde nochmal Faktor 2 erreiche, und der tag 24 stunden hat, bin ich bei 2^17/10/24 = 546 tagen, also mehr (aber nicht grössenordnungen mehr) als das was in Variante a) obigen posts passiert.  

PPS.: Und da die zu bearbeitenden Reste eh im C Programm aus der Tabelle gegriffen werden, und es damit nicht wirklich zählt wie gross diese Tabelle ist, könnte man dort noch einen Faktor von zB 3/5 herausknautschen indem man einfach von 2^10 auf 2^15 geht... damit wäre man wahrscheinlich unter einem jahr rechenzeit. was... wiederum zu hoch ist um es "einfach mal zu tun".



-----------------
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: 2441
Aus: Oberharz
Zum letzten BeitragZum nächsten BeitragZum vorigen BeitragZum erstem Beitrag  Beitrag No.158, vom Themenstarter, eingetragen 2016-12-22 19:15


guten abend miteinander,

Hmpf ich habe diese vorstellung davon im Kopf, wie eine "Collatz-1bit-unit" aussehen müsste und poste das einfach mal. bitte um kritik, die sicher angebracht ist.



jedes bit besteht im prinzip nur aus einem addierer (klaro) und einer AND Verknüpfung, die bewirkt, dass im "odd" Fall x+x/2+1 gerechnet wird und sonst nur x/2. das odd signal wird aus dem untersten bit gewonnen, man wird es puffern müssen, da man es für den ganzen durchlauf der kette braucht. alle addierer sind wie üblich über ihre carries verbunden. die eingänge der addierer sind einmal mit dem data des nächsthöheren bits verbunden (was dem x/2 bzw. einem shr entspricht) und der andere eingang, wenn odd gesetzt ist, mit dem eigenen output entsprechend dem "x". das +1 kann einfach erreicht werden, indem das odd signal auf einen eingang des untersten addierers gelegt wird.

wenn ein path candidate erreicht wird, entspricht das dem erreichen einer bestimmten bitlänge, dh dem erstmaligen auftreten des carry des vorhergehenden bits. dass der stopwert noch nicht erreicht wurde, wird vereinfacht daran erkannt, dass die oberen bits nicht alle nicht gesetzt sind, dazu werden sie nochmal verodert.

man muss das ganze konstrukt am anfang mit dem startwert laden können. das ist hier nicht mit dargestellt.

ich meine, dass man so etwas auf einem FPGA viel einfacher (also platzsparend => also mehr einheiten auf einem FPGA plazierbar) aufbauen kann als eine komplette ALU. Fast hätt ich Lust mal ein paar 1-bit Collatz Units diskret aufzubauen ggg

Es grüsst
und würde sich über jegliche art von kommentaren freuen

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.159, eingetragen 2016-12-22 23:07


2016-12-22 19:15 - gonz in Beitrag No. 158 schreibt:

Es grüsst
und würde sich über jegliche art von kommentaren freuen

gonz

Der Schaltung fehlt vor allen Dingen ein getaktetes Register!

Eine Collatz-Maschine auf einem FPGA könnte in etwa so aus sehen:




Ein Zähler würde die Maschinen durch die Zyklen führen.
Bei Zählerstand ZERO würde das Register auf "2 * MaschinenOffset"
 initialsiert und mit der nächsten Clock-Flanke "Startbase + MaschinenOffset" berechnet.
Startbase kommt von einem 56-bittigen Zähler (für alle Maschinen),
der im Laufe des Zykluses 12 mal getakte wird und dadurch
nächsteStartbase = Startbase + 12 * 256, also
nächsteStartbase = Startbase + 3072 generiert.

Da vor dem Register so oder so eine LUT sitzt, wird man diese für einen Multiplexer nutzen
und der Maschine auch R/4, R/8 und R/16 zur Verfügung stellen.

Falls sich ein Collatz-Algorithmus effektiv auf GPUs realisieren läßt,
dürften weitere FPGA-Betrachtungen überflüssig sein, da sich zum gleichen Preis
sicherlich wesentlich mehr GPU-Maschinen realisieren lassen als FPGA-Maschinen.

Edit: LOAD (Base + 2 * REGZERO) im Bild ist nat. falsch, es müsste (Base +  REGZERO /2) heißen, da REGZERO = 2 * Maschinenoffset ist.



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