Operationen zählen < Numerik < Hochschule < Mathe < Vorhilfe
|
| Aufgabe | Wir wollen die Kosten der Potenzbildung [mm] x^n
[/mm]
bestimmen:
[mm] x^n= [/mm] x*x [mm] \ldots [/mm] x |
hallo,
ich habe folgende Lösung dazu:
Wenn wir zur Berechnung eine Schleife einsetzen, sind n - 1 Multiplikationen durchzuführen.
Wir untersuchen am Beispiel n = 13, ob die Potenzbildung mit weniger als 12 Multiplikationen
erreicht werden kann.
x^13 = x*x^12= x [mm] (x^6)^2 [/mm] = x ( ( x *x [mm] ^2)^2)^2
[/mm]
das ergibt insgesamt 5 Multiplikationen.
meine Frage wäre dazu, waarum man 2er Potenzen betrachten und nicht nur [mm] x*x^{12}. [/mm] dann wäre es doch nur 1 Multiplikation, oder?
bzw. [mm] x(x*x*x)^4. [/mm] In dem Fall ergibt es 4 Operationen.
|
|
| |
|
Hallo,
leider gibt es gerade wieder immense technische Probleme hier im Forum, daher eine kruze Antwort ohne Zitat:
Warum nicht x^12? Ganz einfach, das muss ja auch irgendwie berechnet werden. Die Klammerung bei der Vorgehensweise mit Quadraten ( nicht mit Zweierpotenzen!) ist ja selbsterklärend, da jedes Quadrieren natürlich auch für eine Multiplikaton steht.
Deine Idee am Ende, also
[mm] x^13=x*(x^4)^3
[/mm]
mit 4 Multiplikationen ist jedoch korrekt und somit etwas besser.
Verallgemeinern wird man das nicht können, da steckt recht anspruchsvolle Kombinatorik dahinter und die optimale Lösung zu finden wird schon für unterschiedliche Potenzen zu unterschiedlichen Strategien führen.
Gruß, Diophant
|
|
|
| |
|
Potenzen sind Produkte.
Multiplizieren kann man in einem Schritt immer nur 2 Zahlen miteinander.
Deswegen versucht man, so wenig Faktoren wie möglich zu benutzen.
Das erreicht man durch sinnvolle Zusammenfassungen.
Beispiele:
[mm] 3^4 [/mm] =3*3(=99)*3(=27)*3=81 3 Operationen
[mm] 3^4 [/mm] = [mm] (3^2)^2 [/mm] = 3*3(=9)*9(schon berechnet)=81 2 Operationen
[mm] 2^{16} [/mm] hat im "Einzelfall" 15 Operationen, es geht auch mit 4 Operationen:
[mm] 2^2=2*2=4
[/mm]
[mm] 2^4=(2^2)^2=4^2=16
[/mm]
[mm] 2^8=(2^4)^2=16^2=256
[/mm]
[mm] 2^{16}=(2^8)^2=256^2=65536
[/mm]
(Leider hat der Formelgenerator einen Knall, ich hoffe, du kannst trotzdem lesen, was ich meine.)
|
|
|
|
