Matroids Matheplanet Forum Index
Moderiert von matroid
Informatik » Algorithmen / Datenstrukturen » Binäre Multiplikation
Autor
Universität/Hochschule Binäre Multiplikation
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 400
  Themenstart: 2021-08-01

Binäre Multiplikation. Angenommen ich hätte eine RISC Maschine,die nur shl,shr,add,adc,rrc, rlc und adc zur Verfügung hat. Aufgabe ist Multiplikation 2er Zahlen zur Basis 2, also 0 oder 1 mit Berücksichtigung des Stellenwertes. Gewünscht ist die Größe der Faktoren von 32 Bit und des Ergebnisses mit maximal 64 Bit. Der Umweg über Dezimalrechnung ist bis etwa 4 mal 4 Bit hier leicht und manuell nachvollziehbar. 1.Beispiel 0111 *0101 = 5*7 = 35 =100011 2.Beispiel 6 *4 Bit: 100101 * 1001= 37*9 =333 = 1011101 kann man zur Not auch noch im Kopf. Die Umwandlung von 333 in 1011101 benötigt den (evtl. aufwendigen) euklidischen Algorithmus. 3.Beispiel : 1001001001 (=584 Dez) mal 11001001100 (= 1610 Dez) = 1100100101 bin= 940240 Dez. Letzteres ist schon ohne Taschenrechner nicht mehr ad hoc zu machen. Wie geht es aber mit einem rein binären Algorithmus? Mir ist etwas im Sinn: verschieben des Faktor 1 plus addieren des verschobenen Faktors zum anderen. Je nachdem ob an der Stelle von Faktor1 0 oder 1 steht. Aber wie genau? Wie heißt diese Methode, die sich ja für Digitalrechner anbietet. Wie gesagt: es stehen nur die Assembler Routinen schieben, addieren, Rotation zur Verfügung ohne den Umweg der Dezimalrechnung.


   Profil
ligning
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 07.12.2014
Mitteilungen: 3287
Wohnort: Berlin
  Beitrag No.1, eingetragen 2021-08-01

\quoteon Mir ist etwas im Sinn: verschieben des Faktor 1 plus addieren des verschobenen Faktors zum anderen. Je nachdem ob an der Stelle von Faktor1 0 oder 1 steht. \quoteoff Auch bekannt als Schriftliches Multiplizieren. Genau so geht es.


   Profil
pzktupel
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 02.09.2017
Mitteilungen: 2014
Wohnort: Thüringen
  Beitrag No.2, eingetragen 2021-08-01

Vorab, wie erwähnt, die Regeln sind wie beim Dezimalsystem, nur die Überträge sind schnell mehrstellig. Zur Wandlung: 1100100101 bin= 940240 Dez. Im Prinzip ist das die Rückrechnung auf binäre Umstellung. Von links nach rechts: (...(2*1+1)*2+0)*2+0)*2+1)*2+0)*2+0)*2+1)*2+0)*2+1 = 805 940240 erschliesst sich jetzt mir nicht. 11001001100 => 1612 nicht 1610 (...(2*1+1)*2+0)*2+0)*2+1)*2+0)*2+0)*2+1)*2+1)*2+0)*2+0=1612 [+0] kann man ja real einsparen LG


   Profil
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 400
  Beitrag No.3, vom Themenstarter, eingetragen 2021-08-03

Danke für die Verbesserungen! Es geht analog dem, was man schon frühzeitig so erlernen sollte.. \sourceon 7*13 = 0111 * 1101 ------------------------ 0111 0000 0111 0111 -------------------------- 101101011 =91 \sourceoff etwa so? Sei op1 der linke, ops der rechte Faktor: Es ist sinnvoll den größeren als op1 zu nehmen. Der linke (hier in bx) wird immer um 1 nach links verschoben ohne carry. Und zum 2,4,8 -fachen des op addiert. \sourceon Mob bx, op1 Mob cx ,op2 Mob dx ,1 // Stellenwert rechts xor ax // x =0 label: adc ax,cx (in A zwischenergebnis) shl cx add dx,1 //naechste Stelle des op2 jr lable // wenn das MSB des op2 erreicht ist \sourceoff Mir ist schon klar, dass das noch nicht sauber ist. Es fehlt natürlich u.a. ein Abbruchkriterium, etwa wenn eine bestimmte Anzahl vom shl ereicht ist. Das Dezimalergebnis dient mir zur Kontrolle. Wichtig ist mir der genaue Algorithmus, der ja fast nur aus shl und Add besteht. Und auch bei Operationen wie 100100101 * 100101 funktionier. Das obige Beispiel verlangt an sich nur 3 relevante Addtionen, nämlich an den Stellen des op2, wo eine 1 steht.. Im IdealFall kamm man 64 * 64 Bit Ops ausführen, wenn man den 129 Bit Überlauf fall vorhanden woanders speichert. Nach oben gibt es an sich keine Grenzen... Bsp: A010.BEFF.0976.B001 * ABDF.0976.9013 (Hier alles in Hex) Das sind 64 * 48 Bit. Wer kann die Lösung Ohne Dezialmethoden bringen mittels eines noch zu findenden Algorithmus? Leider hab ich auch keine vernünftigen Assebler für win 64 gefunden, weiß jemand was? Thx


   Profil
rlk
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.03.2007
Mitteilungen: 11110
Wohnort: Wien
  Beitrag No.4, eingetragen 2021-08-09

Hallo juergenX, auf https://nasm.us/ findest Du den Netwide Assembler (NASM) für verschiedene Betriebssysteme, auch für 64-bit Windows. Für die Verfeinerung und den Test des Algorithmus würde ich aber eine höhere Programmiersprache verwenden. Servus, Roland


   Profil
juergenX
Aktiv Letzter Besuch: in der letzten Woche
Dabei seit: 08.07.2019
Mitteilungen: 400
  Beitrag No.5, vom Themenstarter, eingetragen 2021-08-13

ja danke woanders wurde masm unter visualstudio als IDE empfohlen, etwa wie https://www.youtube.com/watch?v=rxsBghsrvpI Früher hatte ich gcc unter ubuntu mit dem etwas gewöhnungsbedürftigen inline assembler benutzt. Ich erwäge allein deswegeb linux zu installieren auf ner extra Partition.


   Profil
gonz
Senior Letzter Besuch: in der letzten Woche
Dabei seit: 16.02.2013
Mitteilungen: 3933
Wohnort: Harz
  Beitrag No.6, eingetragen 2021-08-14

\quoteon(2021-08-13 11:59 - juergenX in Beitrag No. 5) Ich erwäge allein deswegeb linux zu installieren auf ner extra Partition. \quoteoff Das klingt nach einem vernünftigen Ansatz!


   Profil
juergenX hat die Antworten auf ihre/seine Frage gesehen.

Wechsel in ein anderes Forum:
 Suchen    
 
All logos and trademarks in this site are property of their respective owner. The comments are property of their posters, all the rest © 2001-2021 by Matroids Matheplanet
This web site was originally made with PHP-Nuke, a former web portal system written in PHP that seems no longer to be maintained nor supported. PHP-Nuke is Free Software released under the GNU/GPL license.
Ich distanziere mich von rechtswidrigen oder anstößigen Inhalten, die sich trotz aufmerksamer Prüfung hinter hier verwendeten Links verbergen mögen.
Lesen Sie die Nutzungsbedingungen, die Distanzierung, die Datenschutzerklärung und das Impressum.
[Seitenanfang]