Square and multiply

16.03.2005, 13:12

Bernd1983

Square and multiply

Hab da so ein bsp zum ausprogrammieren:

Es soll ein effizienter Algorithmus (square and multiply) für das Auspotenzieren gefunden werden.

als bei 2hoch10 mach ich ja 2*2*2*2

bei square and multiply soll das in 5 schritten erledigt sein. hab im internet gesucht, finde aber kein system heraus wie ich das auf beliebige Zahlen anwende.

Vielleicht weiss jemand was darüber

16.03.2005, 16:26

Denjell

Auf diesen Beitrag antworten »

ohne eine ahnung zu haben

$\begin{eqnarray*} 2^8=((2^2)^2)^2 \end{eqnarray*}$ (3 mal quadrieren)
$\begin{eqnarray*} 2^2=2^2 \end{eqnarray*}$ (1mal quadrieren)
$\begin{eqnarray*} 2^{10}=2^8*2^2 \end{eqnarray*}$ (1mal multipllizieren)

am ende noch einmal multiplizieren... 5 schritte und du hast das ergebnis

kann das so stimmen?

16.03.2005, 16:41

Auf diesen Beitrag antworten »

Ohne es zu merken, hat Denjell nur 4 Multiplikationen benötigt:

Zitat:

Original von Denjell
$\begin{eqnarray*} 2^8=((2^2)^2)^2 \end{eqnarray*}$ (3 mal quadrieren)
$\begin{eqnarray*} 2^2=2^2 \end{eqnarray*}$ (1mal quadrieren) <-- fällt bereits als Zwischenergebnis in der ersten Zeile an (muss nur gespeichert werden)
$\begin{eqnarray*} 2^{10}=2^8*2^2 \end{eqnarray*}$ (1mal multipllizieren)

16.03.2005, 20:44

carsten

Auf diesen Beitrag antworten »

Wie man sieht, zerlegt man dabei den Exponenten in eine Summe von 2er Potenzen. Grob gesagt: um so groessere Potenzen enthalten sind, um so weniger Rechenschritte werden benoetigt.

Gruesse
Carsten

Neue Frage »

Antworten »

Square and multiply

Verwandte Themen