Diskussion:Additionskette

Warum?

• Wer braucht das, in welchem Gebiet werden sie betrachtet? (Ich tippe mal auf Kombinatorik/Diskrete Math/Zahlentheorie)
• Welche interessanten Eigenschaften haben sie?
• Wer hat zum erstenmal etwas Interessantes über sie herausgefunden?

Kurz: definieren kann man viel, aber warum?--Gunther 15:02, 26. Apr 2005 (CEST)

verwendet werden die Ketten in der Informatik und algorithmischen Mathematik, sie sind nützlich in manchen Kryptografieverfahren und haben Bedeutung in der Komplexitätstheorie (theoretische Informatik). Ich werde dazu etwas schreiben, wenn ich mehr präzise und interessante Sachen weiß, aber wie immer sind alle Wikipedianer eingeladen einfach etwas zu ergänzen--Xr 15:42, 26. Apr 2005 (CEST)

Siehe z.B. TAoCP, Vol. 2: Schnelles Exponenzieren (Um a^n auszurechnen: Bekannt ist a^1; für jedes Element k_i der Additionskette speichere a^{k_i}; berechne a^{k_{i+1}} = a^{k_x}*a^{k_y} = a^{k_x + k_y} --> Additionskette). Problem: Die kürzeste Additionstabelle auszurechnen, hat eine hohe Komplexität.

wenn du genaueres weißt, schreib es bitte in den Artikel, davon lebt wikipedia--Xr 13:01, 30. Mai 2005 (CEST)

Additionsketten werden in "The Art of Computer Programing" (vol. 2; Donald E. Knuth) Kapitel 4.6.3 im Detail behandelt ISBN: 0-201-89684-2. Genau für das erwähnte "Schnelle Exponenzieren" für kleine Exponenten (sagen wir < 1000) können diese Additionsketten vorab berechnet werden. Um dann z. B. x⁵⁴ zu berechnen, kann die Additionskette 1, 2, 3, 6, 12, 15, 27, 54 verwendet werden. Somit kann x⁵⁴ mit 7 Multiplikationen berechnet werden, wohingegen die biäre Methode für schnelles Exopnenzieren 8 Multiplikationen verwendet. Im Compilerbau können dann diese Additionketten zu effektiverem Code führen. Phiki 29. Nov. 2008

Einleitungssatz, Erklärung, Beispiel

Ich finde diese drei Punkte nicht sonderlich übersichtlich. Der Einleitungssatz überfällt einen mit einer Formel, die der mathematisch weniger Geübte erst verdauen muss. Dann kommt eine „Erklärung“, die dasselbe auf Deutsch zu sagen versucht, aber überhaupt nichts Neues bringt, und als letztes ein sehr dürres Beispiel. Das ist schade, denn Additionsketten gehören zu den schwierigen mathematischen Problemstellungen, wo auch ein interessierter Laie das Problem verstehen und sich sogar Gedanken zur Lösung machen kann, auch wenn er dabei nicht den heutigen Stand der Kunst erreichen wird.

Ich fände eine andere Reihenfolge besser: zuerst einen Einleitungssatz auf Deutsch ohne oder fast ohne Formel, so dass man ihn unmittelbar sprachlich verstehen kann – das geht. Dann, am besten noch im Einleitungsabschnitt, eine oder zwei formale Formulierungen desselben Sachverhalts, also nachdem man schon die Chance hatte, zur Kenntnis zu nehmen, was eine Additionskette ist. Schließlich Beispiele, an denen man prüfen kann, ob die bis dahin erlangte Vorstellung richtig ist und wo man auch grundlegende Eigenschaften von Additionsketten kennenlernt, z.B. die Multiplikativität (aus einer Kette der Länge r für a und einer Kette der Länge s für b kann man eine Kette der Länge r+s für ab machen; leider nicht immer eine kürzeste).--Lantani (Diskussion) 09:38, 6. Apr. 2016 (CEST)

Den Einleitungsabschnitt habe ich auf Deutsch übersetzt. Meiner Ansicht nach können das sowohl Nichtmathematiker als auch Mathematiker leichter verstehen, ohne dass die Stringenz leidet. Vom ursprünglichen Plan, eine formalere Definition folgen zu lassen, zum Beispiel die alte, bin ich abgerückt: ich sehe nicht, wieso die fehlen würde. Wem sie sehr fehlt, der kann sie ja wieder hineinsetzen. Die bisherige „Erklärung“ ist jetzt echt überflüssig, ebenso das bisherige „Beispiel“ (das so ähnlich im Einleitungsabschnitt gelandet ist). Dafür müsste man neue, nichttriviale Erklärungen und Beispiele schreiben – die würden dann auch den großen weißen Raum füllen.

Ein bisschen schlechtes Gewissen habe ich, weil jetzt fast alles von mir stammt. Aber ich halte es wirklich für lesbarer als das Bisherige.--Lantani (Diskussion) 14:17, 6. Apr. 2016 (CEST)

Inkonsistenz mit englisch-sprachiger Wikipedia

Die deutsche Version verlangt, dass Additionsketten monoton sind. Die englische Version verlangt das nicht. Am Ende ist beides wohl aequivalent, aber man koennte es trotzdem vereinheitlichen... (nicht signierter Beitrag von 83.150.56.211 (Diskussion) 15:08, 12. Jun. 2020 (CEST))

Es gibt zwei Entscheidungen, die man bei der Definition treffen muss.

Die erste Entscheidung ist, ob und wie die Glieder der Kette geordnet sind. Meiner Ansicht nach sollten sie ganz geordnet sein oder gar nicht:

• Ganz geordnet: sie bilden eine streng monoton steigende Folge, die mit 1 beginnt und bei der jedes spätere Element Summe von zwei früheren ist, wie im Artikel.
• Gar nicht geordnet: sie bilden eine Menge, die die 1 enthält und bei der jedes andere Element Summe von zwei beliebigen Elementen ist.

Diese beiden sind ganz offensichtlich äquivalent. Jede endliche Menge natürlicher Zahlen lässt sich ordnen, und dabei liegen die Summanden einer Zahl vor der Zahl selbst. Und jede geordnete Folge lässt sich in eine ungeordnete Menge verwandeln, wobei die Summenbedingung erhalten bleibt.

Der englische WP-Artikel und Knuth haben eine teilweise Ordnung: dass die späteren Elemente die Summe von zwei früheren sind, führt zu einer gewissen Ordnung, nicht aber zur Monotonie. Beispiel: 1, 2, 4, 8, 3, 11. Jede Zahl ist Summe von zwei vorgehenden; mehr ist nicht verlangt. Das ist aber eine andere Kette als 1, 2, 3, 4, 8, 11. Sortiert als aufsteigende Folge oder unsortiert als Menge wären sie gleich. Und genau das macht diese Definition sehr unhandlich. Man hat nur einen Satz von Summen von je zwei Zahlen, aber drei verschiedene Ketten, je nachdem, wie man die Glieder sortiert. Knuth hat das gemerkt und schreibt drei Seiten nach der Definition „We may assume without any loss of generality that an addition chain is “ascending,” […] From now on we shall consider only ascending chains, without explicitly mentioning this assumption.“ (Hervorhebung im Original; S. 447 in der zitierten Auflage; vielleicht später überarbeitet). Da ist es viel einfacher, diese Komplikation gleich von Anfang an zu vermeiden.

Die zweite Entscheidung, die man treffen muss, ist ob die einzelnen Summen zur Kette gehören. Sind die Ketten 1, 2, 3, 4=2+2, 7 und 1, 2, 3, 4=3+1, 7 gleich oder verschieden? In unserem Artikel und bei Knuth sind sie gleich, weil nur verlangt ist, dass jede Zahl Summe von zwei davorstehenden ist, egal von welchen. Im englischen WP-Artikel sind sie verschieden vermöge der Funktion w, die allerdings nach der Definition nie mehr im Artikel vorkommt. Es kann Gründe geben, sie als verschieden zu behandeln, zum Beispiel, wenn man zur Graphendarstellung übergeht wie bei Knuth beschrieben. Aber das soll man dann dort machen, wo man es braucht und nicht vorher die Definition belasten.

Wie hier früher diskutiert, habe ich mich bemüht, die Definition so zu machen, dass man sie ohne weiteres versteht. Die im englischen WP-Artikel ist dagegen sehr mühsam zu verstehen und sehr unhandlich zu benutzen, und die in der Definition versteckten Tücken kommen im Rest des Artikels nicht mehr vor. --Lantani (Diskussion) 00:56, 14. Jun. 2020 (CEST)

Ich habe den Einwand jetzt doch berücksichtigt und die unterschiedlichen Definitionen explizit gemacht. --Lantani (Diskussion) 13:28, 1. Nov. 2020 (CET)