Abfolge von Addition und Multiplikation

19.10.2015, 11:24	Auf diesen Beitrag antworten »
DrInf	Abfolge von Addition und Multiplikation Meine Frage: Hallihallo, ich bin ein wenig verzweifelt, da ich nicht genau weiß, ich diese Aufgabe anpacken soll: Gebe die Abfolge von Additionen und Multiplikationen an, um $[latex]y=(x^2-2x+1)^{10}[/latex]$ möglichst effizient zu berechnen. Verwende Variablen a,b, ... für Zwischenergebnisse. Wie viele Multiplikationen und Additionen werden benötigt und welche Ausführungszeit ergibt sich auf der CPU (pro Addition 1 ns, pro Multiplikation 6 ns)? Meine Ideen: Ich habe so viele unterschiedliche Ansätze, das ich gar nicht weiß, wo ich eigentlich anfangen soll. Rechnet das System pro Klammer? Also $[latex]xx \rightarrow[/latex]$ 1 Multiplikation. $[latex]2x\rightarrow[/latex]$ 2 Multiplikationen. Die Klammer dann aber 10 mal, also 2*10=20 Multiplikationen und dann alle 10 Klammern miteinander multipliziert ergeben dann nochmal 9 Multiplikationen? So dass insgesamt sich 29 Multiplikationen ergeben? Ich wäre sehr, sehr glücklich über jedes bisschen Hilfe!


19.10.2015, 13:09	Auf diesen Beitrag antworten »
eulerscheZahl	Vereinfachen wir zunächst den Ausdruck in der Klammer: $[latex]x^2-2x+1 = (x-2)\cdot x + 1 = a[/latex]$ , das hat 2 Additionen und 1 Multiplikation, dauert also 8ns. Für siehe wikipedia Konkret: $[latex]10_{(10)} = 1010_{(2)}[/latex]$ $[latex]a = a \cdot a[/latex]$ also a^2 $[latex]a = a \cdot a[/latex]$ also a^4 also a^5 $[latex]y = a \cdot a[/latex]$ also a^10 Das sind nochmal 3 Multiplikationen und 1 Addition (19ns), also insgesamt 27ns. Ich würde sagen, ich habe gewonnen
19.10.2015, 21:23	Auf diesen Beitrag antworten »
DrInf	Erst einmal vielen lieben Dank für die Antwort! Dann aber die Frage: Wenn du die Klammer schon so zerlegst, wäre es dann nicht auch möglich aus $[latex](x^2-2x+1)\,\,=\,\,(x-1)^2[/latex]$ zu machen?
20.10.2015, 17:41	Auf diesen Beitrag antworten »
eulerscheZahl	Guter Punkt. Die binomische Formel hatte ich übersehen.
Anzeige

Verwandte Themen

Die Beliebtesten »

Die Größten »

Die Neuesten »