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.
