/**********************************************
* Section : 10
* Roll No. : 20CS10000 / 20CS30000
* Name : Aritra Hazra
* Assignment No : 4b
* Description : GCD Computation of Big Numbers
* Date : 27-Apr-2021
**********************************************/

#include <stdio.h>

#define MAX 1000000

int main()
{
  unsigned int n1, n2, t, swapFlag, carry;
  int i, count;
  char A[MAX], B[MAX], T[MAX];
  
  printf("++ Enter Length of First Number: ");
  scanf("%u", &n1);
  printf("++ Enter First Number: ");
  scanf(" %[^\n]", A);
  printf("++ Enter Length of Second Number: ");
  scanf("%u", &n2);
  printf("++ Enter Second Number: ");
  scanf(" %[^\n]", B);
  
  while(n1 > 0) { // loop till B[] perfectly divides A[]
    carry = 0; swapFlag = 0;
    // determining bigger number 
    if(n1 < n2) { // indication using number of digits
      swapFlag = 1;
    }
    if(n1 == n2) { // indication by MSB search
      for(i=0; i<n1; i++) {
        if(A[i] > B[i]) {
          swapFlag = 0;
          break;
        }
        else if(A[i] < B[i]){
          swapFlag = 1;
          break;
        }
        else {
          ; // do nothing
        }
      }
    }
    if(swapFlag) {
      // put bigger number in A[] and smaller into B[]
      for(i=0; i<n1; i++) {
        T[i] = A[i];
      }
      for(i=0; i<n2; i++) {
        A[i] = B[i];
      }
      for(i=0; i<n1; i++) {
        B[i] = T[i];
      }
      // swapping number of digits
      t = n1;
      n1 = n2;
      n2 = t;
    }
    
    if(n1==n2) {
      for(i=n2-1; i>=0; i--) { // subtracting B from A's MSB positions assuming B's LSB padded as 0s
        if(A[i] >= (B[i]+carry)) { // subtraction yields no carry
          A[i] = '0' + (A[i] - B[i] - carry);
          carry = 0;
        }
        else { // subtraction yields carry
          A[i] = '0' + (10 + A[i] - B[i] - carry);
          carry = 1;
        }
      }
    }
    else{
      if(A[0] > B[0]) { // B can be pushed to leftmost digit of A
        for(i=n2-1; i>=0; i--) { // subtracting B from A's MSB positions assuming B's LSB padded as 0s
          if(A[i] >= (B[i]+carry)) { // subtraction yields no carry
            A[i] = '0' + (A[i] - B[i] - carry);
            carry = 0;
          }
          else { // subtraction yields carry
            A[i] = '0' + (10 + A[i] - B[i] - carry);
            carry = 1;
          }
        }
      }
      else { // B can be pushed to one less than leftmost digit of A
        for(i=n2; i>=1; i--) { // subtracting B from A's MSB positions assuming B's LSB padded as 0s
          if(A[i] >= (B[i-1]+carry)) { // subtraction yields no carry
            A[i] = '0' + (A[i] - B[i-1] - carry);
            carry = 0;
          }
          else { // subtraction yields carry
            A[i] = '0' + (10 + A[i] - B[i-1] - carry);
            carry = 1;
          }
        }
        if(carry) { // carry reduction from A
          A[0] = A[0] - carry;
          carry = 0;
        }
      }
    }
    for(count=0; (count<n1) && (A[count]=='0'); count++) ; // leading zero count in A
    for(i=0; i<n1-count; i++) { // leading zero reduction
      A[i] = A[i+count];
    }
    // reducing length of A
    n1 = n1 - count;
  }
  
  printf("\n** The GCD is: ");
  for(i=0; i<n2; i++) { // The GCD stays in B[]
    printf("%c", B[i]);
  }
  printf("\n");

  return 0;
}