0 Daumen
31 Aufrufe

Hallo Zusammen,

Ich habe neue Übungsaufgabe bekommen bei der ich leider nicht weiterkomme.

Hierbei geht es um die Multiplikation zweier n-stelliger Binärzahlen. Es soll angenommen werden, dass n eine ganzzahlige Potenz der Zahl 3 sei. Zur Multiplikation sollen die beiden n-stelligen Binärzahlen in je drei gleich große Teile$$x = x_{2}x_{1}x_{0}  und  y = y_{2}y_{1}y_{0}$$zerlegt und dann mit folgendem Algorithmus berechnet werden:

$$r_{1} := x_{2}\cdot y_{2} \\r_{2} := (x_{2}+x_{1}) \cdot (y_{2}+y_{1}) \\r_{3} := x_{1} \cdot y_{1} \\r_{4} := (x_{2}+x_{0}) \cdot (y_{2}+y_{0}) \\r_{5} := x_{0} \cdot y_{0} \\r_{6} := (x_{1}+x_{0}) \cdot (y_{1}+y_{0}) \\z := r_{1} \cdot 2^{4n/3} + (r_{2}-r_{1}-r_{3}) \cdot 2^n + (r_{3}+r_{4}-r_{1}-r_{5}) \cdot 2^{2n/3} + (r_{6}-r_{3}-r_{5}) \cdot 2^{2n/3} + r_{5}$$

Die Aufgabe ist nun:

1: Beweise, dass der Algorithmus das gewünschte Produkt berechnet, d.h. $$z := x \cdot y$$

2: Bestimme die Laufzeit des Algorithmus

Hätte jemand eventuell einen Ansatz, Idee oder Lösung, die mir weiterhelfen kann?

Freue mich über jede Hilfe und bedanke mich im voraus.

von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community