ggT und kgT in Assember Code?

5 Antworten

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.

abs kannst Du weglassen, wenn a und b positiv sind.

0

Bitte nicht verwechseln in der Frage steht kgT nicht kgV. Grüße

0
// 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.

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
1

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.

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.

0
@LegendaryBeazt

Dann führe doch die Division durch und subtrahiere den Dividend mit dem Quotient. Das Ergebnis lässt sich ebenso mit 0 vergleichen.

0

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?

Woher ich das weiß:Studium / Ausbildung – Ich studiere beides.

assembler mag uncool sein, aber falsche Algorithmen (Primzahlen bestimmen) sind es auch...

1

Was möchtest Du wissen?