C言語の応用 - 多倍長計算

提供：MochiuWiki : SUSE, EC, PCB
ナビゲーションに移動 検索に移動

概要

ここでは、大きな桁数の計算を行うアルゴリズムを記載する。


値の表現方法

大きな桁数の計算を行うために、値を配列で持たせるとする。
1つの要素に2桁ずつ値を格納して、それを配列として持つことにより大きな桁数を扱うことができる。

  • 500を表現する場合
    ar[4]=00 ar[3]=00 ar[2]=00 ar[1]=05 ar[0]=00
    注意 : C言語において、値の前に0をつけると8進数になるので注意すること。

  • 1234567890を表現する場合
    ar[4]=12 ar[3]=34 ar[2]=56 ar[1]=78 ar[0]=90

  • -1234567890を表現する場合
    マイナス値の場合は配列の総ての要素がマイナスになると考える。
    ar[4]=-12 ar[3]=-34 ar[2]=-56 ar[1]=-78 ar[0]=-90



加算

加算の桁の繰り上がりにおいて、下図のパターンが考えられる。

  1. 99より大きな値を見つけたら現在の要素から100を減算して、上の要素に1を繰り上げる。
  2. -99より小さな値を見つけたら現在の要素から-100を減算して、上の要素に-1を繰り上げる。
  3. 全体が+であり、現在の要素が-である場合、上の要素から1を減算して、現在の要素に100を加算する。
  4. 全体が-であり、現在の要素が+である場合、上の要素から-1を減算して、現在の要素に-100を加算する。


2つの配列の要素を加算して、1〜4の処理を添え字の小さい値から順に繰り返すことで、加算が出来る。

C Multiple Length Calc 1.jpg



減算

減算は、減算する値の符号を反転させることで、加算で代用できる。

100 - 10 → 100 + (-10)



乗算

乗算は、加算を繰り返すことでできるが、時間が掛かりすぎる。
そこで、筆算で計算する手順と同じ手順で計算する。

下図において、1020×523の場合を示す。

C Multiple Length Calc 2.jpg



除算

除算は、被除数から法を繰り返して減算すれば計算できるが、時間が掛かりすぎる。
そこで、シフトを使用して計算する。

C Multiple Length Calc 3.jpg



サンプルコード

 #include <stdio.h>
 
 //  ar1 + ar2 = ar3
 void add(const short*ar,const short*ar2,short*ar3,const int size);
 
 //  ar - ar2 = ar3
 void sub(const short*ar,short*ar2,short*ar3,const int size);
 
 //  ar * ar2 = ar3
 void mul(const short*ar,const short*ar2,short*ar3,int size);
 
 //  ar / ar2 = ar3...ar
 void div(short*ar,short*ar2,short*ar3,const int size);
 
 //  printf(ar)
 void ar_print(short*ar,const int size);
 
 //  配列を固定小数点型として画面表示する
 //  ar[size-1].ar[size-2]~ar[low]
 void dp_print(short*ar,const int size,const int low);
 
 void turn(short*ar,const int size);
 int cmp(const short*ar,const short*ar1,const int size);
 int cmp0(const short*ar,const int size);
 void r_shift(short*ar,const int size);
 void l_shift(short*ar,const int size);
 
 #define SIZE 10
 
 int main()
 {
    short ar1[SIZE] = {0},
          ar2[SIZE] = {0},
          ar3[SIZE] = {0};
 
    //  ar1 = 1000000000000000 
    short ar[9] = 0, ar[8] = 0, ar[7] = 10,
          ar[6] = 0, ar[5] = 0, ar[4] = 0,
          ar[3] = 0, ar[2] = 0, ar[1] = 0,
          ar[0] = 0;
 
    //  ar2 = -1234
    short ar2[9] = 0, ar2[8] = 0, ar2[7] = 0,
          ar2[6] = 0, ar2[5] = 0, ar2[4] = 0,
          ar2[3] = 0, ar2[2] = 0, ar2[1] = -12,
          ar2[0] = -34;
 
    // 減算
    sub(ar1, ar2, ar3, SIZE);
    ar_print(ar1, SIZE);
    printf("-");
    ar_print(ar2, SIZE);
    printf("=");
    ar_print(ar3, SIZE);
    printf("\n");
 
    //  加算
    add(ar1, ar2, ar3, SIZE);
    ar_print(ar1, SIZE);printf("+");ar_print(ar2,SIZE);printf("=");ar_print(ar3,SIZE);printf("\n");

	mul(ar,ar2,ar3,SIZE);//かけ算
	ar_print(ar,SIZE);printf("*");ar_print(ar2,SIZE);printf("=");ar_print(ar3,SIZE);printf("\n");

	ar_print(ar,SIZE);printf("/");ar_print(ar2,SIZE);printf("=");
	div(ar,ar2,ar3,SIZE);//割り算
	ar_print(ar3,SIZE);printf("...");ar_print(ar,SIZE);printf("\n");
 
	return 0;
 }
 
 // 加算 : ar1 + ar2 = ar3
 void add(const short* ar1, const short* ar2, short* ar3, const int size)
 {
    int p_flag;
 
    for(int i = 0; i < size; i++)
    {
       ar3[i] = ar1[i] + ar2[i];
    }
 
    for(int i = 0; i < size; i++)
    {
       if(ar3[i] > 99)
       {
          ar3[i] -= 100;
          ar3[i + 1] += 1;
       }
       else if(ar3[i] < -99)
       {
          ar3[i] -= -100;
          ar3[i + 1] += -1;
       }
    }
 
    p_flag = cmp0(ar3, size);
 
    if(p_flag == 0)
    {
       return;
    }
 
    for(int i = 0; i < size; i++)
    {
       if(p_flag > 0)
       {
          if(0 > ar3[i])
          {
             ar3[i + 1] -= 1;
             ar3[i] += 100;
          }
       }
       else
       {
          if(0 < ar3[i])
          {
             ar3[i + 1] -= -1;
             ar3[i] += -100;
          }
       }
    }
 }
 
 //  減算 : ar1 - ar2 = ar3
 void sub(const short* ar1, short* ar2, short* ar3, const int size)
 {
    turn(ar2, size);
    add(ar1, ar2, ar3, size);
    turn(ar2, size);
 }
 
 // 乗算 : ar1 * ar2 = ar3
 void mul(const short* ar1, const short* ar2, short* ar3, const int size)
 {
    for(int i =0 ; i < size; i++)
    {
       ar3[i] = 0;
    }
 
    for(int i = 0; i < size; i++)
    {
       if(ar2[i])
       {
          for(int j = 0; j < size; j++)
          {
             ar3[j + i] += ar1[j] * ar2[i];
 
             // 3桁目を繰り上げる
             if(ar3[j + i] > 99 || ar3[j + i] < -99)
             {
                int pos = ar3[j + i] / 100;	
                ar3[j + i] -= (pos * 100);
                ar3[j + 1 + i] += pos;
             }
          }
       }
    }
 }
 
 //  除算 : ar1 / ar2 = ar3...ar1
 //  ar1は書き換えられて余りになる
 void div(short* ar1, short* ar2, short* ar3, const int size)
 {
    for(int i = 0; i < size; i++)
    {
       ar3[i]=0;
    }
 
    int div_flag;  //  被除数の符号フラグ
    int met_flag;  //  法の符号フラグ
 
    div_flag = cmp0(ar1, size);
    met_flag = cmp0(ar2, size);
 
    if(!div_flag || !met_flag)
    {  //  法または被除数が0であるため計算を中止する
       return;
    }
 
    if(-1 == div_flag)
    {  //  被除数が負であるため被除数を正の値にする
       turn(ar1, size);
    }
 
    if(-1 == met_flag)
    {  //  法が負であるため法を正の値にする
       turn(ar2, size);
    }
 
    int pos = 0;
    while(1)
    {
       if(cmp(ar1, ar2, size) ==1 && (ar2[size - 1] / 10) == 0)
       {
          pos++;
          l_shift(ar2, size);
       }
       else
       {
          break;
       }
    }
 
    while(pos >= 0)
    {
       if(cmp(ar1, ar2, size) >= 0)
       {
          sub(ar1, ar2, ar1, size);
          if(pos % 2)
          {
             ar3[pos / 2] += 10;
          }
          else
          {
             ar3[pos / 2]++;
          }
       }
       else
       {
          if(pos)
          {
             r_shift(ar2, size);
          }
          pos--;
       }
    }
 
    if(-1 == div_flag)
    {  //  被除数の符号を戻す
       turn(ar1, size);
    }
 
    if(-1 == met_flag)
    {  //  法の符号を戻す
       turn(ar2, size);
    }
 
    if(div_flag != met_flag)
    {  //  被除数と法の符号が違うため解を負の値にする
       turn(ar3, size);
    }
 }
 
 //  画面表示
 void ar_print(short* ar1, const int size)
 {
    int start_flag = 0;
    int p_flag = cmp0(ar1, size);
 
    if(p_flag == 0)
    {
       printf("0");
       return;
    }
 
    if(p_flag == -1)
    {
       printf("-");
       turn(ar1, size);
    }
 
    for(int i = size - 1; i> = 0; i--)
    {
       if(ar1[i] || start_flag)
       {
          if(!start_flag)
          {
             printf("%d", ar1[i]);
          }
          else
          {
             printf("%02d", ar1[i]);
          }
          start_flag=1;
       }
    }
 
    if(p_flag == -1)
    {
       turn(ar1, size);
    }
 }
 
 //  配列を固定小数点型として画面表示する
 // ar1[size-1].ar1[size-2]~ar1[low]
 void dp_print(short* ar1, const int size, const int low)
 {
    int p_flag = cmp0(ar1, size);
    if(p_flag == 0)
    {
        printf("0");
        return;
    }
 
    if(p_flag == -1)
    {
       printf("-");
       turn(ar1, size);
    }
 
    printf("%d.", ar1[size - 1]);
 
    int j = 0,
        k = 0;
    for(int i = size - 2; i >= low; i--)
    {
       if(j++ % 5 == 0)
       {
          printf(" ");
       }
 
       if(k++ % 25 == 0)
       {
          printf("\n");
       }
 
       printf("%02d", ar[i]);
    }
 
    if(p_flag == -1)
    {
       turn(ar1, size);
    }
 }
 
 //  符号の反転
 void turn(short* ar1, const int size)
 {
    for(int i = 0; i < size; i++)
    {
       ar1[i] =- ar1[i];
    }
 }
 
 //  ar1 < ar2の場合は-1を返す
 //  ar1 > ar2の場合は+1を返す
 //  ar1 == ar2の場合は0を返す
 int cmp(const short* ar1, const short* ar2, const int size)
 {
    for(int i = size - 1; i >= 0; i--)
    {
       if(ar1[i] < ar2[i])
       {
          return -1;
       }
 
       if(ar1[i] > ar2[i])
       {
          return 1;
       }
    }
 
    return 0;
 }
 
 //  ar1が正の場合は 1を返す
 //  ar1が負の場合は-1を返す
 //  ar1が0の場合は0を返す
 int cmp0(const short* ar1, const int size)
 {
    for(int i = size - 1; i >= 0; i--)
    {
       if(ar[i] < 0)
       {
          return -1;
       }
 
       if(ar1[i] > 0)
       {
          return 1;
       }
    }
 
    return 0;
 }
 
 //  右に1桁シフト
 void r_shift(short* ar1, const int size)
 {
    ar1[0] = ar1[0] / 10;
 
    for(int i = 1; i < size; i++)
    {
       int pos = ar1[i];
       ar1[i] = ar1[i] / 10;
       ar1[i - 1] += ((pos - (ar1[i] * 10)) * 10);
    }
 }
 
 //  左に1桁シフト
 void l_shift(short* ar1, const int size)
 {
    for(int i = size - 1; i >= 0; i--)
    {
       ar1[i] = ar1[i] * 10;
       int pos = ar1[i] / 100;
       ar1[i] -= (pos * 100);
 
       if(pos)
       {
          ar1[i + 1] += pos;
       }
    }
 }



「http://mochiuwiki.e2.valueserver.jp/index.php?title=C言語の応用_-_多倍長計算&oldid=2643」から取得