二進数の割り算について

[gray]

今二進数の割り算をするプログラムを作っているのですが割り算の商はきちんと出力されるのですが余りがきちんと出力されず、
商の値と同じ値が出力されてしまいます。
どのようにしたらいいでしょうか？

コード:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#include <math.h>


#define MAXCOEFFS 100
#define LBUFSIZE  2048
#define SBUFSIZE  256

#define TRUE      1
#define FALSE     0

#define MOD_P     2



struct poly_s {
  int coeff[MAXCOEFFS];
  int deg;
};

void setpoly_by_value(struct poly_s *a, int value)
{
  int k;

  for (k = 0; value > 0; k++) {
    if (k >= MAXCOEFFS) {
      fprintf(stderr, "error: too large degree\n");
      exit(2);
    }
    a->coeff[k] = value % MOD_P;
    value = (int)(value / MOD_P);
  }
  
  a->deg = k - 1;
}

void setpoly_by_string(struct poly_s *a, char *string)
{
  int k;
  int count, maxk;

  if (string[0] == '0') {
     int value;

     value = (int)strtoul(string + 1, NULL, 8);
     setpoly_by_value(a, value);

  } else if (strchr(string, ',') != NULL) {
    char *p;
    int tmpbuf[MAXCOEFFS];
    count = 0;
    maxk = -1;
    p = strtok(string, ",");
    while (p) {
      tmpbuf[count] = atoi(p);
      count++;
      p = strtok(NULL, ",");
    }
    for (k = 0; k < count; k++) {
      a->coeff[k] = tmpbuf[count - k -1];
      if (a->coeff[k] != 0) {
        maxk = k;
      }
    }
    a->deg = maxk;
  } else {
    count = strlen(string);
    maxk = -1;
    for (k = 0; k < count; k++) {
      if (k >= MAXCOEFFS) {
        fprintf(stderr, "error: too large degree\n");
        exit(2);
      }
      if (isdigit(string[count - k - 1])) {
        a->coeff[k] = (string[count - k -1] - '0');
        if (a->coeff[k] != 0) {
          maxk = k;
        }
      } else {
        a->coeff[k] = 0;
      }
    }
    a->deg = maxk;
  }
}

char *strpoly(struct poly_s *a)
{
  int i;
  int count;
  char tmpbuf[SBUFSIZE];
  static char localbuf[LBUFSIZE];

  count = 0;
  for (i = a->deg; i >= 0; i--){
    if (a->coeff[i] !=0){
      if (count == 0) {
        localbuf[0] = '\0';
      } else {
        strcat(localbuf, " + ");
      }
      if (a->coeff[i] == 1) {
        sprintf(tmpbuf, "x^%d", i);
      } else {
        sprintf(tmpbuf, "%d x^%d", a->coeff[i], i);
      }
      strcat(localbuf, tmpbuf);
      count++;
		}
  }
  if (count == 0) {
    strcpy(localbuf, "0");
  }
  return (localbuf);
}

void polydiv(struct poly_s *a, struct poly_s *b, struct poly_s *q, struct poly_s *r)
{
  int i, j;
	int k = 0, l = 0;
	int m = 0, n = 0;
	int o = 0, p = 0;

	q->deg = a->deg - b->deg;
	if (q->deg < 0) {
	  q->deg = -1;
	}

	for (i = 0;i <= a->deg;i++) {
		k += a->coeff[i] * (int)pow((double) MOD_P, (double) i);
	}
	for (j = 0;j <= b->deg;j++) {
		l += b->coeff[j] * (int)pow((double) MOD_P, (double) j);
	}
	
	m = k / l;
	n = k % l;

	for (i = 0;i <= 10;i++) {
		r->coeff[i] = 0;
		q->coeff[i] = 0;
	}
	
	while (m > 0) {
		q->coeff[o] = m % MOD_P;
		m = m / MOD_P;
		o++;
	}
	while (n > 0) {
		r->coeff[p] = n % MOD_P;
		n = n / MOD_P;
		p++;
	}
}


void polycalc(char *s1, char *s2)
{
  struct poly_s a, b, c, d, r, q;

  setpoly_by_string(&a, s1);
  setpoly_by_string(&b, s2);

  printf("=== Operation over GF[%d] ===\n", MOD_P);
  printf("\n");
  printf("deg a(x) = %d, a(x) = %s\n", a.deg, strpoly(&a));
  printf("deg b(x) = %d, b(x) = %s\n", b.deg, strpoly(&b));
  printf("\n");

　polydiv(&a, &b, &q, &r);

  printf("q + r = a / b\n");
  printf("deg q(x) = %d, q(x) = %s r(x) =%s\n", q.deg, strpoly(&q), strpoly(&r));
  printf("\n");
}　

int main(int argc, char **argv)
{
  if (argc != 3) {
    fprintf(stderr, "usage: polycalc <string1><string2>\n");
    fprintf(stderr, "ex. polycalc 1011001 1101\n");
    fprintf(stderr, "ex. polycalc o23 1,1,0,1\n");
    exit(2);
  }
  
  polycalc(argv[1], argv[2]);
  
  return (0);
}
 

[box]

main関数のusageに載っている2つの例では、
どのような結果を得たいのでしょうか。

特に後の方の例は、書いてあることの意味がよくわかりません。

[gray]

これはコマンド引数の書き方を示します。
1011001のように連続に書いてもいいですし、1,0,1,1,0,0,1のようにカンマで区切っても大丈夫です。
またo23のようにかいても2x^1+3x^0のようになります

main関数のusageに載っている2つの例では、
どのような結果を得たいのでしょうか。

特に後の方の例は、書いてあることの意味がよくわかりません。

[box]

usageに書いてある2つの例ではどういう結果を得たいのですか
という質問への回答はどうなっていますか？


以下、独白（無視してくださってかまいません。ひとりごとですから）
いったん10進数に変換してから
10進数で計算し、
商とあまりを2進数に変換する、
というのが簡単なように思う。

[gray]

usageの横にあるのはコマンド引数の書き方を示しただけなので
きちんとコマンド引数が入力されていない場合に出るので書き方の例です。

商は正しく出力されるのですが余りが正しく出力されません。
なぜかあまりにも商の値が出力されてしまいます。
どうしたらいいでしょうか？

[gray]

すみません解決できました。
ありがとうございました。

[かずま]

すみません解決できました。
ありがとうございました。

解決したソース、または、どこを修正したのかを明確に提示してください。

それから、

コード:

polycalc o23 1,1,0,1

と入力すると、どういう結果が表示されるのかを
次のように書いてください。

コード:

polycalc 1011101 1001

と入力すると、

コード:

=== Operation over GF[2] ===

deg a(x) = 6, a(x) = x^6 + x^4 + x^3 + x^0
deg b(x) = 3, b(x) = x^3 + x^2 + x^0

q + r = a / b
deg q(x) = 3, q(x) = x^2 + x^1 r(x) =x^3 + x^1 + x^0

という結果を得たいのに、

コード:

=== Operation over GF[2] ===

deg a(x) = 6, a(x) = x^6 + x^4 + x^3 + x^0
deg b(x) = 3, b(x) = x^3 + x^2 + x^0

q + r = a / b
deg q(x) = 3, q(x) = x^2 + x^1 r(x) =x^2 + x^1

という結果が表示されます。

[かずま]

質問です。

#define MAXCOEFFS 100
となっているのは、2進 100桁まで
計算できるという意味ですよね。

ところが、polydiv() の中で、
a と b を、int の k と l に変換し、
m = k / l; n = k % l; で商と余りを求めた後、
m と n を q と r に変換しています。

これだと int のビット数(多分 31ビット) しか
計算できないと思います。

#define MAXCOEFFS 100 の意味するところは何ですか？