XProfan

WindowTitle "Bachet-erweiterter Euklidischer Algorithmus"
WindowStyle 24
declare a&,b&, g&,x&,y&,s$
Main:
Font 2
CLS
print "\n Der Algorithmus sucht den ggT(a,b) und begründet ihn.\n"
print " Es gilt: ggT(a,b) = a * X + b * Y   mit a,b,X,Y ganzzahlig."
print
print "\n a = ";:input a&
print   " b = ";:input b&
g&=Bachet(a&,b&)
Font 2:Print "\n\n  ggT(a,b) = ";g&,"   = ",x&,
Font 0:print "*",a&,
Font 2:print "+",y&,
Font 0:print "*",b&,"\n"
waitinput
Goto "Main"

proc Bachet :parameters a&,b&

    declare bg&,bu&,cg&,cu&,xg&,xu&,yg&,yu&
    bg&=a&
    cg&=0
    xg&=1
    yg&=0
    bu&=b&
    cu&=a&\b&
    xu&=0
    yu&=1

    while (bg&<>0) and (bu&<>0)

        xg&=xg&-cu&*xu&
        yg&=yg&-cu&*yu&
        bg&=bg& mod bu&

        if bg&=0

            g&=bu&
            x&=xu&
            y&=yu&

        else

            cg&=bu&\bg&
            xu&=xu&-cg&*xg&
            yu&=yu&-cg&*yg&
            bu&=bu& mod bg&

        endif

        if bu&=0

            g&=bg&
            x&=xg&
            y&=yg&

        else

            cu&=bg&\bu&

        endif

    endwhile

    return g&

endProc