XProfan

Deutsch

p.specht

Einer der ersten bekannten Algorithmen überhaupt stammt von EUKLID (360 - 280 v. Chr). Damals ging es um das größtmögliche Kürzen von Brüchen. Erst viel später, A.D. 1967 erkannte man weitere Verbesserungsmöglichkeiten, so z.B. den Algorithmus von Josef Stein (D), der OHNE DIVISIONEN auskommt: Einfaches Rechtsverschieben der Binärzahl reicht vollkommen aus, was die Sache ungemein beschleunigt. Anbei dieser Algorithmus (Quelle: Symbolisches Programm von Prof.em. Donald Knuth, dem Algorithmenpapst)

Kompilieren Markieren Separieren

WindowStyle 1048
WindowTitle "Stein´scher GGT-Algorithmus"
' (CL) Copyleft 2012-09 P. Specht, Wien
Declare w$,a&,b&
Loop:
Cls : print
print " Ganzzahliger Divisor: "; : input w$

if (right$("0000000000"+w$,10)>"2147483647")

    print "Zu groß, max: 2147483647"
    waitinput
    goto "Loop"

endif

a& = val(w$)
print " Ganzzahliger Dividend: "; : input w$

if (right$("0000000000"+w$,10)>"2147483647")

    print "Zu groß, max: 2147483647"
    waitinput
    goto "Loop"

endif

b& = val(w$)
print
print " Größter gemeinsamer Teiler (GGT) nach Stein: ";stein(a&,b&)
waitinput
Goto "Loop"

Proc Stein

    parameters a&,b&
    declare k&,erg&,t&

    if a&=0:erg&=0:goto "jump":endif

        WhileNot ((a& mod 2) or (b& mod 2))

            a&=a&\2
            b&=b&\2
            inc k&

        endwhile

        if (a& mod 2)

            t&= -1*b&

        else

            t&= a&

        endif

        while t&

            whilenot t& mod 2

                t&=t&\2

            endwhile

            if t&>0

                a&=t&

            else

                b&= -1*t&

            endif

            t&= a&-b&

        endwhile

        erg&=a& * 2^k&
        jump:
        return erg&

    EndProc