C言語関係掲示板

過去ログ

No690 多倍長の掛け算

[戻る] [ホームページ]
No.8031

すいません、教えてください。
投稿者---ゆか(2003/07/05 20:42:12)


多倍長を使っての掛け算なのですがどうも上手くいきません。間違えてる部分が私もよくわかりません。


#include <stdio.h>
#include <string.h>

#define MAX 72			
#define N ((MAX-1)/4+1)		


void input_num(int D[]);	

void display(int D[]);		
void add(int A[], int B[], int C[]);
				
int main(void) {
  /
  int A[N], B[N], C[N];			
  input_num(A);
  input_num(B);
  add(A, B, C);
  printf("\n   "); display(A);
  printf("\n * "); display(B);
  printf("\n = "); display(C);

  return(0);
}

void add(int A[], int B[], int C[]) {
  int i, carry;


  for (i=0; i<=N-1; i++) {
    C[i]=0;
  }

 
  for (i=0,carry=0; i<=N/2-1; i++) {
    if (i==0) {
    
      C[i] = A[i] *B[i]; 
      carry = C[i]/10000;
      C[i] %= 10000;		

    }
     
      else {
     
      C[i] =( A[i]*B[i]) + carry;
      carry = C[i]/10000;
      C[i] %= 10000;		
    }
  }
  C[i] = carry;		
	
void input_num(int D[]) {
  char line[MAX];
  int	 last;
  int	 i,j,digit;

  printf(" %d 桁以下の整数を入力して下さい:", MAX/2);
  fgets(line, sizeof(line), stdin);
 
 for (i=0; i<=N-1; i++) {
    D[i] = 0;
  } 

  last= strlen(line)-2;

  for (i=0; last >=0; i++) {
    for (j=1,digit=1; j<=4 && digit<=1000 && last>=0; j++, digit*=10, last--) {
      D[i] += (line[last]-'0')*digit;
    }
  }
  return;
}


void display(int D[]) {
  int i,digit,temp,flag=1;

  for (i=N-1; i>=0; i--) {
    if (D[i]==0) printf("    ");
    else break;
  }
 
  printf("%4d",D[i]);

  for (i-- ; i>=0; i--) {
    for(digit=1000, temp=D[i]; digit>=1; digit/=10) {
      printf("%d", temp/digit);
      temp%=digit;		
    }
  }

  return;
}


No.8039

Re:すいません、教えてください。
投稿者---もぐりん(2003/07/05 22:52:44)


ソースはコンパイルしてみましたか?
Borland C++ Compiler 5.5.1でコンパイルしてみましたが、
8個のコンパイルエラーが出ましたよ。
まず、14行目の/は不要でしょう。
16行目の配列A,B,Cの要素数Nは、どこで定義していますか?
17,18行目も16行目が解決しないとエラーになります。
関数addについて括弧の閉じがないようです。
コンパイルエラーを修正してからコンパイルして実行してみると
4桁x4桁までは正しく計算しているようですが、最初に入力する数字が
5桁以上になると計算結果がおかしくなります。
デバックしてみてください。



No.8042

Re:すいません、教えてください。
投稿者---たいちう(2003/07/06 01:11:36)


ソースをざっとみたところ、多倍長の足し算のソースを参考に、
かけ算の関数を作ってるんですね。

まず、エラーとは関係ないですが、関数名addというのは致命的な間違いです。
元々の足し算用の関数名を使っているだけでしょうが、
関数名や変数名は適切に命名してください。

次が本題。
足し算とかけ算は計算のアルゴリズムがまったく違いますので、
関数内の"+"を"*"に変えただけでは正しく計算されるはずがありません。

足し算の筆算を思い出してください。
足し算は各桁を小さい方から足し合わせ、10を超えると繰り上がります。
123+789の場合、3+9、20+80、100+700を繰り上がりに
注意しながら計算して合計していきます。

この方法で10000進法で計算をしていたのが、元々のaddだったはずです。
多倍長を表す配列の各要素は、普通の数字の1桁に対応するので、
各要素は対応する要素とだけ足し算をします。
A[0]+B[0],A[1]+B[1],,,というように。
繰り上がりはcarryが表します。

ゆかさんの間違えは、
A[0]*B[0],A[1]*B[1],,,と計算したものの合計を積としていることです。
123×789の場合だと、
123*789 = 100*700 + 20*80 + 3*9 という計算方法です。

頭を整理して正しく直してください。
当然forループは2重になります。

No.8043

Re:すいません、教えてください。
投稿者---ゆか(2003/07/06 13:23:38)


私もあれから考えているんですがここまでで限界です。本当にごめんなさい。


#include <stdio.h>
#include <string.h>

#define MAX 72			
#define N ((MAX-1)/4+1)		


void input_num(int D[]);	

void display(int D[]);		
void sqr(int A[], int B[], int C[]);
				
int main(void) {
  
  int A[N], B[N], C[N];			
  input_num(A);
  input_num(B);

  printf("\n   "); display(A);
  printf("\n * "); display(B); 
  sqr(A, B, C);


  printf("\n = "); display(C);

  return(0);
}

void sqr(int A[], int B[], int C[]) {
  int i, carry,k=0,j;


  for (i=0; i<=N-1; i++) {
    C[i]=0;
  }

   for(i=0;i<=N/2-1;i++){
     for(j=0,carry=0;j<=i;j++,k++){    
	 C[k]=(A[i]*B[j])+carry;
         C[k]%=10000;	
         carry=C[k]/10000;
    }
     C[k]=carry;
   }
}

void input_num(int D[]) {
  char line[MAX];
  int	 last;
  int	 i,j,digit;

  printf(" %d 桁以下の整数を入力して下さい:", MAX/2);
  fgets(line, sizeof(line), stdin);
 
 for (i=0; i<=N-1; i++) {
    D[i] = 0;
  } 

  last= strlen(line)-2;

  for (i=0; last >=0; i++) {
    for (j=1,digit=1; j<=4 && digit<=1000 && last>=0; j++, digit*=10, last--) {
      D[i] += (line[last]-'0')*digit;
    }
  }
  return;
}


void display(int D[]) {
  int i,digit,temp,flag=1;

  for (i=N-1; i>=0; i--) {
    if (D[i]==0) printf("    ");
    else break;
  }
 
  printf("%4d",D[i]);

  for (i-- ; i>=0; i--) {
    for(digit=1000, temp=D[i]; digit>=1; digit/=10) {
      printf("%d", temp/digit);
      temp%=digit;		
    }
  }

  return;
}



No.8044

Re:すいません、教えてください。
投稿者---かずま(2003/07/06 14:45:54)


>      for(j=0,carry=0;j<=i;j++,k++){    
>           C[k]=(A[i]*B[j])+carry;
>          C[k]%=10000;
>          carry=C[k]/10000;
>     }

        for (carry = j = 0, k = i; j < N/2; j++, k++) {    
            C[k] += A[i] * B[j] + carry;
            carry = C[k] / 10000;
            C[k] %= 10000;    
        }

割り算は効率が悪いので、次のように書いたほうがよいかも。

            C[k] += A[i] * B[j] + carry;
            if (C[k] < 10000)
                carry = 0;
            else {
                carry = C[k] / 10000;
                C[k] %= 10000;
            }


No.8047

Re:すいません、教えてください。
投稿者---ゆか(2003/07/06 18:59:44)


助かりました。ありがとうございます。

No.8051

Re:すいません、教えてください。
投稿者---たいちう(2003/07/06 19:38:12)


addよりはましですがsqrも誤解を招きます。