XProfan

Français

p.specht

Einer qui ersten bekannten Algorithmen überhaupt stammt de EUKLID (360 - 280 v. Chr). autrefois ging es um cela größtmögliche Kürzen de Brüchen. seulement viel später, A.D. 1967 erkannte on weitere Verbesserungsmöglichkeiten, so z.B. den Algorithmus de Josef Stein (D), qui OHNE DIVISIONEN auskommt: Einfaches Rechtsverschieben qui Binärzahl reicht vollkommen aus, quoi qui l'affaire ungemein beschleunigt. Anbei cette Algorithmus (source: Symbolisches Programme de Prof.em. Donald Knuth, dem Algorithmenpapst)

Kompilieren Marque Séparation

Fenêtre Style 1048
Titre de la fenêtre "Stein´scher GGT-Algorithmus"
' (CL) Copyleft 2012-09 P. Specht, vienne
Déclarer w$,a&,b&
Boucle:
Cls : imprimer
imprimer " Ganzzahliger Divisor: "; : input w$

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

    imprimer "Zu grand, max: 2147483647"
    waitinput
    goto "Loop"

endif

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

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

    imprimer "Zu grand, max: 2147483647"
    waitinput
    goto "Loop"

endif

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

Proc Stein

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

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

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

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

        endwhile

        si (a& mod 2)

            t&= -1*b&

        d'autre

            t&= a&

        endif

        tandis que t&

            whilenot t& mod 2

                t&=t&\2

            endwhile

            si t&>0

                a&=t&

            d'autre

                b&= -1*t&

            endif

            t&= a&-b&

        endwhile

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

    ENDPROC