Erweiterter Euklidischer Algo

[Pat90]

moin,
Benötige eine Umsetzung des erweiterten euklidischen algos in VB.
Habe dazu zuerst einen Pseudocode aus einem Buch umgesetzt und danach eine Java Version:

class GcdRepresentation {

        public int g, u, v;

        public GcdRepresentation(int a, int b)
        {
          extendedGcd(a, b);
          Out.println("ggT(a,b)= " + g);
          Out.println("u= " +u);
          Out.println("v= " +v);
        }


        public void extendedGcd(int a, int b)
        {
            if (b==0)
            {
                g=a;
                u=1;
                v=0;
            }
            else
            {
                extendedGcd(b, a%b);
                int x=u;
                u=v;
                v=x-a/b*v;
             }


        }

}

Das wäre meine VB Version davon

 Function Erweiterter_Euklidischer_Algo(ByVal ee, ByVal phi) As String
        Dim rueckgabe As String

      
        If phi = 0 Then

            g = ee
            u = 1
            v = 0

        Else
            Erweiterter_Euklidischer_Algo(phi, (ee Mod phi))
            Dim x As Integer
            x = u
            u = v
            v = x - ee / phi * v
        End If
        rueckgabe = u & "      " & v
        Return (rueckgabe)



    End Function

Leider wird immer falsch gerechnet.
Vielleicht findet ja hier jemand den Fehler,

mfg

 

[Elderan]

Hallo,
ich kann:
http://de.wikipedia.org/wiki/Erweiterter_euklidischer_Algorithmus

empfehlen. Dort einfach mal den Pseudo Code in VB programmieren und dann ggf. debuggen. Beispiele sind auch gegeben.

 

[Pat90]

Ich habe in meinem Buch auch noch einen Pseudocode zum Programm gefunden.
Dieser lautet wie folgt

xeuclid(int a, int b, int gcd, int x, int y) {
begin
int q, r, xx, yy, sign
int xs[2], ys[2]

//Koeffizienten werden initialisiert
xs[0] = 1 xs[1] = 0
ys[0] = 0 ys[1] = 1
sign = 1

//Solange b !=0 ist,, wird a durch b und b durch a%b ersetzt
//Ausserdem erden die Koeffizienten neu berechnet

while (b!= 0)
r = a%b
q = a/b
a = b
b = r
xx = xs[1]
yy = ys[1]
xs[1] = q*xs[1] + xs[0]
ys[1] = q*ys[1] + ys[0]
xs[0] = xx
ys[0] = yy
sign = -sign
end while

//Die Koeffizienten werden endgültig berechnet
x = sign*xs[0]
y = sign*ys[0]

gcd = a
end

Ich habe diesen Code dann folgendermaßen in VB umgesetzt

Function Erweiterter_Euklidischer_Algo(ByVal a, ByVal b) As String
        Dim q, r, xx, yy, x, y, sign, gcd As Integer
        Dim xs(2), ys(2) As Integer

        xs(0) = 1
        xs(1) = 0
        ys(0) = 0
        ys(1) = 1
        sign = 1

        Do While (b <> 0)
            r = a Mod b
            q = a / b
            a = b
            b = r
            xx = xs(1)
            yy = ys(1)
            xs(1) = q * xs(1) + xs(0)
            ys(1) = q * ys(1) + ys(0)
            xs(0) = xx
            ys(0) = yy
            sign = -sign

        Loop

        x = sign * xs(0)
        y = sign * ys(0)

        gcd = a

Ich erhalte bei a = 100 und b = 35 -1 und 4 als koeffizienten.
Es müsste jedoch -1 und 3 sein.

//WICHTIG//
Habe den Pseudocode in C umgesetzt (dafür musste ja nicht wirklichw as verändert werden)
Und dort rechnet er richtig!
Es muss also irgend eine VB Eigenheit sein wieso er bei mir nicht will.

 

[odigo]

Das Problem liegt bei

q = a / b

q ist ein int. VB rundet ab ,5 auf. Die meisten anderen Programmiersprachen würden das beim Casten einfach abschneiden. Man muss statt nem / einen \ nehmen.
Also:

q = a \ b

Siehe auch http://de.wikibooks.org/wiki/Visual_Basic_6:_Operatoren#Grundrechenarten

Gruß odigo

Edit: VB ist nicht vBulletin sondern VisualBasic

 

[Elderan]

Oh ein Grund mehr warum ich VisualBasic nicht mag. Kann nur empfehlen auf C# umzusteigen, empfinde ich deutlich angenehmer in der Entwicklung.

VB hat einfach einige Eigenheiten, die man so nicht erwarten würde.
Mit 'Dim array(5) As Int' wird ein Array mit 6 Elemente z.B. erstellt.