Günstiges Multipliziern

Neue Frage »

HanzFux Auf diesen Beitrag antworten »
Günstiges Multipliziern
Hi,
ich hab hier folgende aufgabe die ich berhaupt nicht verstehe:

[attach]9929[/attach]

Also mas ich machen soll ist klar....x^382 mit 14 Multplikationen darstellen.
Aber wie geht man da vor ?

Laut dem Hinweis in der letzten Zeile zerlegt man die 382...in Faktoren/Summanden. Aber wie genau ?

EDIT von Calvin
Bilder bitte direkt im Board hochladen. Danke
AD Auf diesen Beitrag antworten »

Eine gängige Methode: Den Exponenten in Binärdarstellung überführen

,

steht ja auch schon im Hinweis. Dann ein Algorithmus zur Berechnung der Potenzen mit Zweierpotenzexponent:

mit Startwert ergibt nämlich .

Das muss hier bis ausgeführt werden, ergibt genau 8 Multiplikationen. Es verbleibt der "Zusammenbau"



mit 6 weiteren Multiplikationen. Also 14 Multiplikationen, das wäre (i).


Für (ii) musst du dann probieren, ob es nicht auch mit Dreier- statt Zweierpotenzen, oder gemischt, oder ... günstiger (d.h. mit weniger Multiplikationen) geht.

EDIT: Die (iii) hat's in sich. Augenzwinkern 1 , 2 , 4 , 5 , 9 , 14 , 23 , 46 , 92 , 184 , 368 , 382
 
 
Neue Frage »
Antworten »



Verwandte Themen