ggT und kgT in Assember Code?
Wir sollen im Assembler Code 2 Programme erstellen, mit welchen man von zwei Zahlen in den Registern R1 und R2 den ggT und zwei Brüche errechnet und in R3 speichert.
Mir fehlt jeglicher Ansatz zu beiden.
Es wäre sehr hifreich, wenn mir jemand einen Ansatz geben könnte bzw. sagen, mit welcher vorgehensweise es am Sinnvollsten wäre.
5 Antworten
Assembler ist gay shit.
0. Herangehensweise siehe regex9
1. Mathematische Formeln siehe Felix
2. Bestimme die Primzahlen
2.1. mathematische/informative Formel zum bestimmen der Primzahlen
2.2 finde heraus, wie du das in Assembler umsetzen kannst
2.3 setze es um.
3. Übersetze den Rest in Assembler.
Ich denke 3. ist trivial. Die eigentliche Aufgabe ist also: Wie findest du die Primzahlen. Denk Mal darüber nach.
Was benutzt ihr denn?
assembler mag uncool sein, aber falsche Algorithmen (Primzahlen bestimmen) sind es auch...
// Liefert den ggT für a>b
L1: if b = 0 goto L2
quot := a DIV b
rest := a - quot*b
a := b
b := rest
goto L1
L2: return a
Ich würde nicht den Umweg über die Primfaktorzerlegung machen. Wenn es in Assembler keine mod Funktion gibt, machst du eine ganzzahlige Division, nimmst den Quotienten von a/b wieder mit b mal und ziehst das von a ab.
Goto ist zwar in Hochsprachen verboten, in Assembler aber üblich. Zumindest war das vor 35 Jahren so ;-) Das oben entspricht einer kopfgesteuerten while-Schleife. Die 4 Variablen kann man sich in Registern halten. Müsste einigermaßen schnell sein.
zum größten gemeinsamen Teiler, siehe Euklids Algorithmus in wikipedia (ist ein 3-Zeiler).
das kleinste gemeinsame Vielfache lässt sich dann mit:
kgV(a,b) = abs(a*b) / ggT(a,b)
berechnen.
Der kgt von zwei Zahlen ist immer 1, Du meinst vermutlich den ggT und das kgV, den größten gemeinsamen Teiler und das kleinste gemeinsame Vielfache.
Zerlege die Zahlen in ihre Primfaktoren. Der ggT ist das Produkt aller gemeinsamen Primfaktoren beider Zahlen in der jeweils kleinsten Potenz. Das kgV ist das Produkt aller Primfaktoren in der jeweils größten Potenz.
Beispiel: ggT und kgV von 12 und 30
12=2² * 3 und 30=2 * 3 * 5
ggT 2 * 3=6
kgV 2² * 3 * 5=60
ggT(100160063,50065021)
Viel Spass bei der Primfaktorenzerlegung!
Mit Euklid:
100160063 : 50065021 = 2 Rest 30021
50065021 : 30021 = 1667 Rest 20014
30021 : 20014 = 1 Rest 10007
20014 : 10007 = 2 Rest 0
return 10007
Stelle zunächst eine mathematische Formel / einen mathematischen Lösungsweg auf, mit dem sich der ggT / kgT berechnen lässt. Diesen Lösungsweg solltest du in viele Teilschritte aufteilen, die sich schlussendlich Zeile für Zeile in Assembler umwandeln lassen.
Dann führe doch die Division durch und subtrahiere den Dividend mit dem Quotient. Das Ergebnis lässt sich ebenso mit 0 vergleichen.
dan multipliziere wieder und subtrahiere; das ergibt den rest.
Zum Rest: bei vielen Maschinen (die mir untergekommen sind) liefert der DIV Befehl in einem 2. Register den Rest.
Z.B. in x86:
DIV r/m32
Unsigned divide EDX:EAX by r/m32, with result stored in EAX = Quotient, EDX = Remainder.
Quelle: https://c9x.me/x86/html/file_module_x86_id_72.html
Danke erstmals, Ich habe versucht, den ggT nsch Euklid zu berechnen. In unserem Glossar mit erlaubten Befehlen gibt es nur DIV als Befehl, der aber kein Rest erlaubt.