Informatiker Board | Druckvorschau: Abfolge von Addition und Multiplikation

Geschrieben von DrInf am 19.10.2015 um 11:24:

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]x*x \rightarrow[/latex]$ 1 Multiplikation. $[latex]2*x\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!

Geschrieben von eulerscheZahl am 19.10.2015 um 13:09:

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 [latex]y = a^n[/latex]

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
[latex]a = a + a[/latex]

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 smile

Geschrieben von DrInf am 19.10.2015 um 21:23:

Erst einmal vielen lieben Dank für die Antwort! smile

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? smile