Günstiges Multipliziern |
02.03.2009, 18:08 | HanzFux | Auf diesen Beitrag antworten » |
Günstiges Multipliziern 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 |
||
03.03.2009, 11:49 | 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. 1 , 2 , 4 , 5 , 9 , 14 , 23 , 46 , 92 , 184 , 368 , 382 |
|