# Greatest common divisor

If we have already implemented adding, substracting etc. big numbers we can easily count their greatest common divisor by using Euclid's algorithm. However, its simple version cannot be applied, because if we simply use equation gcd(a,b)=gcd(b,a-b), then in case when a>>b result will be processed much longer, than we would like. Due to this problem in this implementation I used a simple trick: if both numbers a,b are even then their gcd=2*(gcd(a/2,b/2)). Moreover, if one is even and second is odd, gcd won't be even so we can divide even one by 2. Only, when both numbers are odd situation is more complicated and in this case we use equation gcd(a,b)=gcd(b,a-b). It can be easily seen, that at least in one step out of two we shorten one number by one digit, so the whole algorithm has complexity o(log a + log b).

The whole algorithm is implemented in bignumber unit. Here you can see a simple program, which just reads two number and using nwduj from bignumber unit computes their greatest common divisor.

To see that it really works, use below:

MAIN