How to make a MDC algorithm with just sum and subtraction?

Question

How do I make an algorithm that calculates the MDC of two numbers only using sum and subtraction operations? It is prohibited to use operators other than those requested.

Answer 1

Without comparison operations, there is no way to stop the algorithm, so I assume that other arithmetic operations are prohibited, not prohibiting comparison operations. OK?

To begin with, we normally use positive integers, so I will consider this condition and in case of arguments outside these conditions we must make the appropriate adaptations.

Second, if one could use calculation of rest of Euclidean division (usually the symbol is used %) could be calculated using the recursion sequence: mdc(a,b)=( b=0 ? a : mdc(b,a%b) ).

There is an algorithm for dividing rest of positive integers that follows recursion a%b=( a<b ? a : (a-b)%b ). It can also be implemented without recursion, thus.

resto( a , b )
    enquanto( a>=b )faça
        a <--- a-b
    retorna a

This means that one can calculate division remainder only with subtraction loop, not using the division operator. Thus, the calculation of mdc can swap the division for loop subtractions.

With this, the recursion of mdc becomes mdc(a,b)=( b=0 ? a : mdc(b,resto(a,b)) ). Refine the mdc algorithm, it gets like this.

mdc( a , b )
    enquanto( b>0 )faça
        enquanto( a>b )faça
            a <--- a-b
        b <-> a
    retorna( a )

Have any questions?