GCD(Greatest Common Divisor)

Finding GCD is a good start to study algorithm due to its calculation simplicity.

 

What people commonly use for figuring out GCD is prime factorization.

 

Let's say we have two numbers, 720 and 12.

 

** image from - https://en.wikipedia.org/wiki/Greatest_common_divisor 

It is a good method for human who can figure out common divisors without inputting numbers from 1 to increasingly. However, a computer should go through that process.

 

Thus, our task is to find a good algorithm for computer to calculate GCD.

 

Let's use some 'MATH' here. =_=

 

We have numbers A, B. These two numbers are not same and bigger than 1.

 

If they have a GCD, we can write as below.

** G = GCD

A = a * G

B = b * G

 

Let's subtract them.

 

A - B = a * G - b * G

= (a - b) G

 

So, we can know that A - B also have the same GCD. We can manipulate it.

 

The GCD of A or B and A - B is same. So that we can subtract a greater number to the rest number until one of these number is zero. When one of number is 0, the rest number is GCD.

 

GCD(X, 0) = X

 

** This is because zero is always zero with any number multiplied.

ex) 0 * 1 = 0, 0 * 24098209384 = 0

 

Let's prove with practical numbers.

 

GCD(54, 18) = GCD(36, 18)

= GCD(18, 18)

= GCD(18, 0)

 

Thus, GCD(54, 18) = 18

 

 

Examine the calculation. We can notice

 

-> Subtraction goes on until a greater number becomes less than a smaller number, which is same arithmetic of "%". YEAH!

 

GCD(54, 18) = GCD(18, 54%18)

= GCD(18, 0)

 

Now, we have prepared a GCD algorithm for computer.

 

Let's make functions when inputting numbers vary from 2 to 5.

 

What we should keep in mind.

 

1. Find smallest number as divisor

2. Loop should go on until input number -1 are zero

ex) 4 numbers input for GCD, loop should go on until 3 numbers are 0

 

3. If all input numbers become 0 by divisor, divisor should be GCD.

Below is code of GCD function for 5 arguments(numbers)

int GCD5(unsigned int uiNum1, unsigned int uiNum2, unsigned int uiNum3, unsigned int uiNum4, unsigned int uiNum5)
{
  unsigned int uiCnt;  //counter for loop
  unsigned int uiDiv;  //divisor for finding GCD
  unsigned int uiNum[5];  
  unsigned int uiZero;

  //putting numbers intto array  
  uiNum[0] = uiNum1;
  uiNum[1] = uiNum2;
  uiNum[2] = uiNum3;
  uiNum[3] = uiNum4;
  uiNum[4] = uiNum5;

  //finding GCD(Greatest Common Divisor)
  uiDiv = uiNum1;
  while(1)
  {
    //finding divisor
    for(uiCnt = 0; 5 > uiCnt; ++uiCnt)
    {
      if(uiDiv > uiNum[uiCnt] && uiNum[uiCnt] != 0)
      {
        uiDiv = uiNum[uiCnt];
      }
    }
    printf("Divisor is [%d]\n", uiDiv);
    uiZero = 0;
    for(uiCnt = 0; 5 > uiCnt; ++uiCnt)
    {
      uiNum[uiCnt] = uiNum[uiCnt] % uiDiv;
      if(0 == (uiNum[uiCnt] = uiNum[uiCnt] % uiDiv))
      {
        ++uiZero;
      }      
    }
    if(4 <= uiZero)
    {
      break;
    }    
  }
  if(uiZero == 5)
  {
    return uiDiv;
  }    
  return uiNum[0] + uiNum[1] + uiNum[2] + uiNum[3] + uiNum[4];
}