Это правильная реализация алгоритма Евклида? - PullRequest
Новая
       33

Это правильная реализация алгоритма Евклида?

0 голосов
/ 04 августа 2020

Я пытался реализовать алгоритм Евклида в AE C. Одна странная проблема заключается в том, что AE C не поддерживает локальные переменные, кроме как в качестве аргументов функции. Вы можете увидеть это вживую здесь . Вот код: 

Function gcd(Integer32 a, Integer32 b) Which Returns Integer32 Does
    //So, this will be Euclid's algorithm. But, first, let's deal with
    //the edge cases.
    If a<0 Then
        a:=a*-1; //Write in such a way that it will expose as many potential
                 //bugs in the compiler as you can.
    EndIf
    If b<0 Then
        b:=b/-1;
    EndIf
    If a=0 or b=0 Then
        Return 0;
    EndIf
    //And now goes the 2'300 years-old algorithm:
    While not(b=0) Loop
        If a>b Then
            a:=mod(a,b);
        Else
            If a=0 Then
                Return b;
            EndIf
            b:=mod(b,a);
        EndIf
    EndWhile
    Return a;
EndFunction

Итак, это правильная реализация алгоритма? Насколько я тестировал, похоже, что он работает, однако я не уверен. Евклидов алгоритм, основанный на вычитании, очень медленный, а традиционный алгоритм, основанный на модуле, не может быть реализован без третьей переменной.

...