MLA2.h



// DIVの改良 2017/2/18 
// 多倍長剰余MMOD(int n, int *a_num. int *b_num, int *z_num); を作成 2017/2/18
// ユークリッド互除法 GCM(int n, int *a_num, int *b_num, int *z_num); を作成 2017/2/18
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

// MLA.h
int Radix = 10000;


int CLEAR(int n, int *a_num, int a)   {
int i;
for ( i = 0; i < n; i++ )  {
    a_num[i] = 0;	
}
a_num[0] = a;
return 1;
}

int COPY(int n, int *a_num, int *b_num)  {
int i;
for ( i = 0; i < n; i++ )  {
    a_num[i] = b_num[i];	
}
return 1;
}

int DISP(int n, int *a_num)   {

int i;
int disp = 0;
int first = 1;

for ( i = n - 1; i >= 0; i-- )     {
 if ( a_num[i] != 0 )  disp = 1;
 if ( disp == 1 )     {
	if ( first == 1 )  {
		printf("%d",a_num[i]);
		first = 0;
    } else             {
		printf("%04d",a_num[i]);
	}
  }
}

if ( disp == 0 ) printf("0");

printf("\n");	
return 1;
}

int MUL(int n, int *a_num, int a)     {
int i,j;
	
  for ( i = 0; i < n; i++ )
   a_num[i] = (a * a_num[i]);  // a倍する
  // 桁揃え
  for ( j = 0; j < n - 1; j++ )  {
	a_num[j+1] += (a_num[j] / Radix); // 桁上がり
	a_num[j] = (a_num[j] % Radix);  // 1万進法	
  }	

return 1;

}

int MOD(int n, int *a_num, int a)     {
int i,r;
 for ( i = n-1; i >= 0; i-- )   {
    if ( i == n-1 )       {
	 r = (a_num[i]%a);
	} else                {
	 r = r * Radix + a_num[i];
	 r = (r%a);
	}
 }
return r;
}

int DIV(int n, int *a_num, int a)     {

int i,j,r;

 for ( i = n-1; i >= 0; i-- )   {
    if ( i == n-1 )       {
	 r = (a_num[i]%a);
	} else                {
	 r = r * Radix + a_num[i];
	 r = (r%a);
	}
 }

   for ( i = n-1; i >= 0; i-- )     {
	 if ( i >= 1 )
	  a_num[i-1] += (a_num[i]%a)*Radix;
	  a_num[i] = a_num[i]/a;   // aで割る
   }
  // 桁揃え
  for ( j = 0; j < n - 1; j++ )  {
	a_num[j+1] += (a_num[j] / Radix); // 桁上がり
	a_num[j] = (a_num[j] % Radix);  // 1万進法	
  }
 
 return r;
}

int ADD(int n, int *a_num, int a)      {
int j;

a_num[0] += a;

  // 桁揃え
  for ( j = 0; j < n - 1; j++ )  {
	a_num[j+1] += (a_num[j] / Radix); // 桁上がり
	a_num[j] = (a_num[j] % Radix);  // 1万進法	
  }	

return 1;
}

int SUB(int n, int *a_num, int a)      {
int i,j;

a_num[0] -= a;

 for (i = 0; i < n-1; i++ )  {
   if ( a_num[i] < 0 )        {
	a_num[i+1]--;
	a_num[i] += Radix;
   }
 }

  // 桁揃え
  for ( j = 0; j < n - 1; j++ )  {
	a_num[j+1] += (a_num[j] / Radix); // 桁上がり
	a_num[j] = (a_num[j] % Radix);  // 1万進法	
  }

return 1;
}

int ISN(int n, int *a_num, int a)      {
int i;

for (i = n-1; i > 0; i-- )   {
  if ( a_num[i] != 0 ) return 0; 
}

 if ( a_num[0] == a ) return 1;
 else return 0;
 
}

int CSET(int *a_num,char *i_num)  {
int i,j,k,d,L;
char buff[5];
L = strlen(i_num);

d = L%4;
j = 0;
if ( d == 0 )      {
 k = L/4 - 1;
 for ( i = 0; i < (int) strlen(i_num); i++ )  {
	buff[j++] = i_num[i];
	if ( j > 3 )       {
	  buff[j] = 0;
	  j = 0;
	 a_num[k--] = atoi(buff);
    }
 }
} else               {
 k = L/4;
 i = 0;
 while ( i < d )   {
	buff[j++] = i_num[i++];
 }
  buff[j] = 0;
  j = 0;
  a_num[k--] = atoi(buff);
 for ( i = d; i < (int) strlen(i_num); i++ )  {
	buff[j++] = i_num[i];
	if ( j > 3 )       {
	  buff[j] = 0;
	  j = 0;
	 a_num[k--] = atoi(buff);
    }
 }
}

return 1;
}


int MADD(int n, int *a_num, int *b_num)  {
int i,j;

 for (i = 0; i < n-1; i++ )  {
   a_num[i] += b_num[i];
 }
 
  // 桁揃え
  for ( j = 0; j < n - 1; j++ )  {
	a_num[j+1] += (a_num[j] / Radix); // 桁上がり
	a_num[j] = (a_num[j] % Radix);  // 1万進法	
  }

return 1;
}


int MSUB(int n, int *a_num, int *b_num)  {
int i,j;

 for (i = 0; i < n-1; i++ )  {
   a_num[i] -= b_num[i];
   if ( a_num[i] < 0 )        {
	a_num[i+1]--;
	a_num[i] += Radix;
   }
 }

  // 桁揃え
  for ( j = 0; j < n - 1; j++ )  {
	a_num[j+1] += (a_num[j] / Radix); // 桁上がり
	a_num[j] = (a_num[j] % Radix);  // 1万進法	
  }

return 1;
}

int Collatz(int n, int *a_num)    {
int j = 1;

 while ( ISN(n, a_num,1) != 1 )    { // 1になったら停止
  if (( a_num[0] % 2) == 0 )   {  // 偶数か
    DIV(n, a_num, 2);   // 2で割る
  } else                       {  // そうでないなら
	MUL(n, a_num, 3); ADD(n, a_num, 1);    // 3倍して1を足す
  }
   j++;
 }
 return j;
}

int DGN(int n, int *a_num)      {
int i = n - 1;
int L = 0;

while ( a_num[i] == 0 ) {
 i--;
 if ( i == 0 ) break;
} 
 if ( a_num[i] >= 1000 ) L = 4;
 else if ( a_num[i] >= 100 ) L = 3;
 else if ( a_num[i] >= 10 ) L = 2;
 else if ( a_num[i] >= 1 ) L = 1;

 L += i*4;

return L;

}

int CMP(int n, int *a_num, int *b_num)   {
int i = n;

while ( i >= 0 )     {
 if ( a_num[i] != 0 || b_num[i] != 0 )  {
   if ( a_num[i] > b_num[i] )
    return 1;
   
   if ( a_num[i] < b_num[i] )
    return -1;   
 }
 i--;
}

 return 0;
}

int MMUL(int n, int *a_num, int *b_num, int *c_num)         {
int i, j,k;
int a_top, b_top;

CLEAR(n,c_num,0);
// 非ゼロの最大値を確認
a_top = 0;
for ( i = n; i >= 0; i-- )  {
  if ( a_num[i] != 0 ) {
     a_top = i;
     break;
 }
}

b_top = 0;
for ( i = n; i >= 0; i-- )  {
  if ( b_num[i] != 0 ) {
     b_top = i;
     break;
 }
}


 for ( i = 0; i <= a_top; i++ )      {
    for ( j = 0; j <=  b_top; j++ )      {
      c_num[i+j] += a_num[i]*b_num[j];
    }
    for ( k = 0; k < n - 1; k++ )  {
	c_num[k+1] += (c_num[k] / Radix); 
	c_num[k] = (c_num[k] % Radix);	
    }
  }

return 1;

}

int MDIV(int n,int *a_num, int *b_num, int *c_num, int *z_num )   {
int i,k,s,t;
int *y_num; // 値保持用変数
int *u_num; // ダミー変数

// メモリ領域の確保
y_num = new int[n];
u_num = new int[n];

if ( ISN(n,b_num,0) == 1 )  {  // 割る数が0か
  delete[] y_num;
  delete[] u_num;
  return -1;
}

// 割る数のコピー
COPY(n, y_num, b_num);

if ( CMP(n,b_num,a_num) > 0 )  {
  CLEAR(n,c_num,0);
  COPY(n,z_num,a_num);
  delete[] y_num;
  delete[] u_num;
  return 0;
}

//その他変数の初期化
CLEAR(n, c_num, 0);
CLEAR(n, z_num, 0);

// 割る数の桁シフト
k = 0;
while ( CMP(n, a_num, b_num) > 0 ) {
 MUL(n, b_num, 10);
 k++;
}
DIV(n, b_num, 10);

while (1)                                 {
  t = 0;
  while ( CMP(n, a_num, b_num) < 0 )  {
    DIV(n, b_num, 10);
    k--;  t++;
    if ( t > 1 )  MUL(n, c_num, 10);
  }
  
  s = 1;
  while ( s <= 9 )                    {
    COPY(n, z_num, a_num);
    COPY(n, u_num, b_num);
    MUL(n, u_num, s);
    MSUB(n, z_num, u_num);
    if ( CMP(n,z_num,y_num) < 0 )  {
	 MUL(n,c_num,10);
	 ADD(n,c_num,s);
	 while ( k > 1 )   {
	   MUL(n,c_num,10);
	   k--;
	 }
	 goto EZ;
	} else if ( CMP(n, z_num, b_num) < 0 )  {
	  break;
	}
	s++;
  }
 MUL(n,c_num,10);  ADD(n,c_num,s);
 COPY(n,a_num,z_num);
 if ( k <= 1 ) break;
}
EZ:

COPY(n,b_num, y_num);  // b_numを書き戻す

// メモリの解放
delete[] y_num;
delete[] u_num;
return 1;
}

int MMOD(int n,int *a_num, int *b_num, int *z_num )   {
int i,k,s,t;
int *y_num; // 値保持用変数
int *u_num; // ダミー変数

// メモリ領域の確保
y_num = new int[n];
u_num = new int[n];

if ( ISN(n,b_num,0) == 1 )  {  // 割る数が0か
  delete[] y_num;
  delete[] u_num;
  return -1;
}

// 割る数のコピー
COPY(n, y_num, b_num);

if ( CMP(n,b_num,a_num) > 0 )  {
  COPY(n,z_num,a_num);
  delete[] y_num;
  delete[] u_num;
  return 0;
}

//その他変数の初期化
CLEAR(n, z_num, 0);

// 割る数の桁シフト
k = 0;
while ( CMP(n, a_num, b_num) > 0 ) {
 MUL(n, b_num, 10);
 k++;
}
DIV(n, b_num, 10);

while (1)                                 {
  t = 0;
  while ( CMP(n, a_num, b_num) < 0 )  {
    DIV(n, b_num, 10);
    k--;  t++;
  }
  
  s = 1;
  while ( s <= 9 )                    {
    COPY(n, z_num, a_num);
    COPY(n, u_num, b_num);
    MUL(n, u_num, s);
    MSUB(n, z_num, u_num);
    if ( CMP(n,z_num,y_num) < 0 )  {
	 while ( k > 1 )   {
	   k--;
	 }
	 goto EZ;
	} else if ( CMP(n, z_num, b_num) < 0 )  {
	  break;
	}
	s++;
  }
 COPY(n,a_num,z_num);
 if ( k <= 1 ) break;
}
EZ:

COPY(n,b_num, y_num);  // b_numを書き戻す

// メモリの解放
delete[] y_num;
delete[] u_num;
return 1;
}

int GCM(int n, int *a_num, int *b_num, int *z_num)       {
while ( ISN(n,a_num,0) != 1 && ISN(n,b_num,0) != 1 )  {

 if ( CMP(n,a_num,b_num) > 0 )    {
	MMOD(n,a_num,b_num,z_num);
	COPY(n,a_num,z_num);
 } else                           {
	MMOD(n,b_num,a_num,z_num);
	COPY(n,b_num,z_num);
 }
}

if ( ISN(n,a_num,0) == 1 )    {
    COPY(n,z_num,b_num);
} else                        {
    COPY(n,z_num,a_num);
}
 return 1;
}