www.vorhilfe.de
- Förderverein -
Der Förderverein.

Gemeinnütziger Verein zur Finanzierung des Projekts Vorhilfe.de.
Hallo Gast!einloggen | registrieren ]
Startseite · Mitglieder · Impressum
Forenbaum
^ Forenbaum
Status VH e.V.
  Status Vereinsforum

Gezeigt werden alle Foren bis zur Tiefe 2

Navigation
 Startseite...
 Suchen
 Impressum
Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
Forum "Zahlentheorie" - Erw. euklidischer Alg. - Binär
Erw. euklidischer Alg. - Binär < Zahlentheorie < Algebra+Zahlentheo. < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Erw. euklidischer Alg. - Binär: Binärzahlen
Status: (Frage) überfällig Status 
Datum: 18:08 Fr 11.01.2013
Autor: Master_X


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


        
Bezug
Erw. euklidischer Alg. - Binär: Antwort
Status: (Antwort) fertig Status 
Datum: 18:26 Fr 11.01.2013
Autor: reverend

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


Bezug
        
Bezug
Erw. euklidischer Alg. - Binär: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
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. []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


Bezug
        
Bezug
Erw. euklidischer Alg. - Binär: Fälligkeit abgelaufen
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 18:20 So 13.01.2013
Autor: matux

$MATUXTEXT(ueberfaellige_frage)
Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Zahlentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


^ Seitenanfang ^
ev.vorhilfe.de
[ Startseite | Mitglieder | Impressum ]