Informatiker Board | Informatik in der Schule | Abfolge von Addition und Multiplikation

Informatiker Board » Themengebiete » Informatik in der Schule » Abfolge von Addition und Multiplikation

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Abfolge von Addition und Multiplikation

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

DrInf
unregistriert

Abfolge von Addition und Multiplikation

Zitatantwort auf diesen Beitrag erstellen

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!

19.10.2015 11:24

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

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

__________________
Syntax Highlighting fürs Board (Link)

Dieser Beitrag wurde 1 mal editiert, zum letzten Mal von eulerscheZahl: 19.10.2015 13:10.

19.10.2015 13:09

Nehmen Sie eulerscheZahl in Ihre Freundesliste auf

DrInf
unregistriert

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

19.10.2015 21:23

eulerscheZahl eulerscheZahl ist männlich

Foren Gott

Dabei seit: 04.01.2013
Beiträge: 2.859

Guter Punkt. Die binomische Formel hatte ich übersehen.

__________________
Syntax Highlighting fürs Board (Link)

20.10.2015 17:41

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Informatik in der Schule » Abfolge von Addition und Multiplikation