Erstellen Sie eine Turing Maschine, die zwei binäre Zahlen multipliziert.
Ausgangslage
Die beiden zu multiplizierenden Zahlen sind in binärer Darstellung gegeben. Wo die beiden Zahlen in der Welt plaziert werden, kann von Ihrer Lösung abhängig gemacht werden.
Hinweis
Die beiden Zahlen können mit Hilfe der ”Zigeunermultiplikation”
multipliziert werden. Bei der Zigeunermultiplikation wird die eine Zahl
jeweils halbiert, während die andere verdoppelt wird. Ist die zu halbierende Zahl
ungerade, so wird die zu verdoppelnde zum Resultat addiert (gelb markierte Zeilen).
Beispiel 9 * 5:
1. Zahl (halbieren) |
2. Zahl (verdoppeln) |
Resultat |
|
|
|
|
0 |
[0] |
9 |
[1001] |
5 |
[101] |
5 |
[101] |
4 |
[100] |
10 |
[1010] |
5 |
[101] |
2 |
[10] |
20 |
[10100] |
5 |
[101] |
1 |
[1] |
40 |
[101000] |
45 |
[101101] |
Um eine binäre Zahl zu verdoppeln, können alle Bits der Zahl um eins nach links verschoben werden. Um eine binäre Zahl zu halbieren, können die Bits nach rechts verschoben werden, wobei die Stelle ganz rechts gelöscht wird.