Erw. euklidischer Alg. - Binär < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
|
Hallo,
ich will den euklidischen Algorithmus (für ggT(a,b) = as + tb) auf Binärzahlen anwenden.
Wenn ich ihn mit Dezimalzahlen wie bei Wikipedia ausführe, dann läuft es:
extended_euclid(a,b)
wenn b = 0
dann return (a,1,0)
(d',s',t') = extended_euclid(b, a mod b)
(d,s,t) = (d',t',s' - floor(a/b)t')
return (d,s,t)
Wenn ich den Algorithmus auf Binärzahlen übertragen bekomme ich ein falsches Ergebnis.
Die Subtraktion habe ich als Addition mit dem additiv-binär-Inversen berechnet.
Hat einer von euch eine Idee / Algorithmus, wie man das programmieren kann?
Vielen Dank und viele Grüße
|
|
| |
|
Hallo [mm] Master_X,
[/mm]
eine gute Gelegenheit für den Informatik-Konjunktiv: das müsste aber funktionieren...
> ich will den euklidischen Algorithmus (für ggT(a,b) = as
> + tb) auf Binärzahlen anwenden.
Dagegen ist nichts einzuwenden. 
> Wenn ich ihn mit Dezimalzahlen wie bei Wikipedia ausführe,
> dann läuft es:
>
> extended_euclid(a,b)
> wenn b = 0
> dann return (a,1,0)
> (d',s',t') = extended_euclid(b, a mod b)
> (d,s,t) = (d',t',s' - floor(a/b)t')
> return (d,s,t)
Hm. Vielleicht verstehe ich da etwas nicht. Das sollte auch mit Dezimalzahlen nicht funktionieren... In der Zeile (d',s',t')... fehlt doch etwas, oder nicht?
> Wenn ich den Algorithmus auf Binärzahlen übertragen
> bekomme ich ein falsches Ergebnis.
Eigenartig.
> Die Subtraktion habe ich als Addition mit dem
> additiv-binär-Inversen berechnet.
Das sollte ja funktionieren, sofern Deine Variablen wirklich als Binärvariablen deklariert sind (!).
> Hat einer von euch eine Idee / Algorithmus, wie man das
> programmieren kann?
Ich würde mal die floor-Funktion in Verbindung mit einem dividierten Arument einzeln überprüfen. Ich könnte mir vorstellen, dass es da hakt. Dann findest Du aber leicht eine binäre Ersatzprogrammierung.
Ich lasse die Frage halboffen, weil ich selbst noch im Dunklen tappe.
Grüße
reverend
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 17:20 Sa 12.01.2013 | | Autor: | felixf |
Moin!
> ich will den euklidischen Algorithmus (für ggT(a,b) = as
> + tb) auf Binärzahlen anwenden.
geht es evtl. um den sog. ![[]](/images/popup.gif) binaeren euklidischen Algorithmus? Das ist ein leicht anderer Algorithmus.
> Wenn ich ihn mit Dezimalzahlen wie bei Wikipedia ausführe,
> dann läuft es:
>
> extended_euclid(a,b)
> wenn b = 0
> dann return (a,1,0)
> (d',s',t') = extended_euclid(b, a mod b)
> (d,s,t) = (d',t',s' - floor(a/b)t')
> return (d,s,t)
Der Algorithmus ist voellig unabhaengig von der gewaehlten Darstellung der Zahlen. Dein Problem liegt wohl eher in der Implementation der Arithmetik?
> Wenn ich den Algorithmus auf Binärzahlen übertragen
> bekomme ich ein falsches Ergebnis.
>
> Die Subtraktion habe ich als Addition mit dem
> additiv-binär-Inversen berechnet.
Wie genau behandelst du denn das Vorzeichen? Und wie stellst du Zahlen dar?
LG Felix
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 18:20 So 13.01.2013 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
