XProfan

Español

p.specht

Einer el ersten bekannten Algorithmen überhaupt stammt de EUKLID (360 - 280 v. Chr). Damals ging lo en el größtmögliche Kürzen de Brüchen. Erst viel später, A.D. 1967 erkannte uno weitere Verbesserungsmöglichkeiten, así z.B. el Algorithmus de Josef Stein (D), el OHNE DIVISIONEN auskommt: Einfaches Rechtsverschieben el Binärzahl reicht vollkommen de, lo que el Sache ungemein beschleunigt. Anbei dieser Algorithmus (Quelle: Symbolisches Programa de Prof.em. Donald Knuth, el Algorithmenpapst)

Kompilieren Marca Separación

Ventana de Estilo 1048
Título de la ventana "Stein´scher GGT-Algorithmus"
' (CL) Copyleft 2012-09 P. Pájaro carpintero, Wien
Declarar w$,a&,b&
Loop:
Cls : imprimir
imprimir " Ganzzahliger Divisor: "; : input w$

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

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

endif

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

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

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

endif

b& = val(w$)
imprimir
imprimir " Größter gemeinsamer Teiler (GGT) después de Stein: ";stein(a&,b&)
waitinput
Goto "Loop"

Proc Stein

    parámetros a&,b&
    declarar k&,erg&,t&

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

        Sinestar encargado ((a& mod 2) or (b& mod 2))

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

        endwhile

        if (a& mod 2)

            t&= -1*b&

        más

            t&= a&

        endif

        mientras que t&

            whilenot t& mod 2

                t&=t&\2

            endwhile

            if t&>0

                a&=t&

            más

                b&= -1*t&

            endif

            t&= a&-b&

        endwhile

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

    ENDPROC