多倍長整数

平成21年秋季基本情報技術者試験の午後問題9では，多倍長整数の問題が出題されています。大学1年の頃のレポートの課題(言語はPascalだったと思う)であったなぁと懐かしくなったので，やってみました。というか，そのまま入力しました。

• 平成21年秋季基本情報技術者試験の午後問題9

h21a_fe_pm9.c

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

#define ARRAY_MAX 100
#define NUM_DIGIT 9
#define NUM_DIGIT_TH_POWER_OF_TEN 1000000000

typedef struct {
  int length;
  long data[ARRAY_MAX];
} MP;

void setup(MP*, const char[]);
void print(const MP*);
void add(const MP*, const MP*, MP*);

/* 文字列から多倍長整数を扱う構造体に変換 */
void set(MP *num, const char str[])
{
  int str_idx = strlen(str) - 1;
  int num_idx = 0;
  int i;
  long mul;

  while (str_idx >= 0) {
    num->data[num_idx] = 0;
    mul = 1;
    for (i = 0; i < NUM_DIGIT && str_idx >= 0; i++) {
      num->data[num_idx] += mul * (str[str_idx--] - '0');
      mul *= 10;
    }
    num_idx++;
  }
  num->length = num_idx;
}

/*  多倍長整数の出力 */
void print(const MP *num)
{
  int i;

  printf("%ld", num->data[num->length - 1]);
  for (i = num->length - 2; i >= 0; i--) {
    printf("%09ld", num->data[i]);
  }
  printf("\n");
}

/* 二つの多倍長整数の加算 */
void add(const MP *a, const MP *b, MP *c)
{
  int i;
  int i_max;

  if (a->length > b->length) {
    i_max = a->length;
  }
  else {
    i_max = b->length;
  }
  c->data[0] = 0;

  for (i = 0; i < i_max; i++) {
    if (i < a->length) c->data[i] += a->data[i];
    if (i < b->length) c->data[i] += b->data[i];

    if (c->data[i] >= NUM_DIGIT_TH_POWER_OF_TEN) {
      c->data[i + 1] = 1;
      c->data[i] -= NUM_DIGIT_TH_POWER_OF_TEN;
    }
    else {
      c->data[i + 1] = 0;
    }
  }
  if (c->data[i] == 0) {
    c->length = i;
  }
  else {
    c->length = i + 1;
  }
}

int main(void)
{
  char str1[] = "231456813123456789234567890478617283";
  char str2[] = "999999999123456789009283741";
  MP a, b, ans;

  set(&a, str1);
  set(&b, str2);
  add(&a, &b, &ans);
  print(&ans);

  return 0;
}

実行

ちゃんと計算できているか，Rubyでの実行結果と比較しました。

$ gcc h21a_fe_pm9.c
$ ./a.out
231456814123456788358024679487901024
$ irb
irb(main):001:0> 231456813123456789234567890478617283 + 999999999123456789009283741
=> 231456814123456788358024679487901024