東大の演習問題に挑戦(4) - 多倍長演算編
次は多倍長演算です。
課題5-A:無限多倍長整数を連結リストで実現し、四則演算を実装せよ。但し、数を表示するときには10進表記にすること。レポートには、プログラムの簡単な説明と実装上の工夫(乗法演算の高速化など)に関する言及を含めよ。
出ましたリスト!!
「それSchemeで」とか言いたい所ですが、頑張ってCで実装していきます。
多倍長演算は結構面倒そうっすね・・・。
方針
とりあえず簡単に実装出来そうな方針を練ります。
- 一桁を10進数で表す。
- わかりやすさ優先で。
- 後で増やせばいいかなぁと思う。
- 構造体は2個使います。
- 符号とリストを格納するbignum
- 数値の実体を格納するbignum_list
- -1234を格納するときは、 '-' > 4 > 3 > 2 > 1というリストを作ります。
- 符号付きは難しそうなので止めちゃうかも。
とりあえず、目標は1個足す所まで実装出来ればいいかなぁと思います。
実装
リストといえば再帰。再帰と反復をしっかり使い分ける所が重要ポイント。
もう慣れたもんですよ。
#include <stdio.h> #include <stdlib.h> typedef struct _bignum_list { unsigned int n; struct _bignum_list *next; } bignum_list; typedef struct { int sign; bignum_list *list; } bignum; bignum_list *new_bignum_list(char *s) { bignum_list *l = NULL; bignum_list *new; for (;*s != '\0'; s++) { new = (bignum_list *) malloc(sizeof (bignum_list)); new->n = *s - '0'; new->next = l; l = new; } return l; } void free_bignum_list(bignum_list *l) { if (l == NULL) return; free_bignum_list(l->next); free(l); } bignum *new_bignum(char *s) { bignum *b = (bignum *) malloc(sizeof (bignum)); /* 符号の決定 */ if (*s == '-') { b->sign = -1; s++; } else b->sign = 1; b->list = new_bignum_list(s); return b; } void free_bignum(bignum *b) { free_bignum_list(b->list); free(b); } void display_bignum_list(bignum_list *l) { if (l == NULL) return; display_bignum_list(l->next); printf("%d", l->n); } void display_bignum(bignum *b) { printf("%s", (b->sign == 1) ? "": "-"); display_bignum_list(b->list); printf("\n"); } void inc_bignum(bignum *b) { int carry = 1; bignum_list *l = b->list; for (;;) { l->n += carry; carry = l->n / 10; l->n %= 10; if (carry) { if (l->next == NULL) l->next = new_bignum_list("0"); l = l->next; } else break; } } int main(void) { bignum *b = new_bignum("999999999999999999"); display_bignum(b); inc_bignum(b); display_bignum(b); free_bignum(b); return EXIT_SUCCESS; }
長いけど出来ることは少ない・・・。
テスト
999999999999999999 + 1をやってみます。
% ./bignum 999999999999999999 1000000000000000000
おぉぉぉぉ。スゲー。
桁あがりが実装出来ました。
むぅ。マイナスの実装方法がイマイチ不明なので、とりあえず正の整数のみで考えよう。多倍長演算は大変そうだ・・・。
足し算
もうちょっと頑張ります。
正の整数だけ考えよう。
bignum *add_bignum(bignum *a, bignum *b) { bignum *c = new_bignum("0"); bignum_list *al = a->list; bignum_list *bl = b->list; bignum_list *cl = c->list; int carry = 0; for (;;) { cl->n += carry; if (al != NULL) { cl->n += al->n; al = al->next; } if (bl != NULL) { cl->n += bl->n; bl = bl->next; } carry = cl->n / 10; cl->n %= 10; if (al != NULL || bl != NULL || carry) { cl->next = new_bignum_list("0"); cl = cl->next; } else break; } return c; }
incの応用でいけました。
両方終わるまで下桁から足し続けます。
引き算
むじぃ。
/* 0001234 -> 1234 */ int chop_bibnum_list(bignum_list *l) { if (l == NULL) return 1; else if (chop_bibnum_list(l->next)) { if (l->n == 0) return 1; else { free_bignum_list(l->next); l->next = NULL; return 0; } } else return 0; } bignum *sub_bignum(bignum *a, bignum *b) { bignum *c = new_bignum("0"); bignum_list *al = a->list; bignum_list *bl = b->list; bignum_list *cl = c->list; int tmp = 0; int carry = 0; for (;;) { tmp = carry; if (al != NULL) { tmp += al->n; al = al->next; } if (bl != NULL) { tmp -= bl->n; bl = bl->next; } if (tmp < 0) { carry = -1; tmp += 10; } else carry = 0; cl->n = tmp; if (al != NULL || bl != NULL) { cl->next = new_bignum_list("0"); cl = cl->next; } else break; } chop_bibnum_list(c->list); if (carry) { fprintf(stderr, "マイナスは未実装。"); exit(EXIT_FAILURE); } return c; }
引き算の場合は桁数が減るのですげー大変。そうfreeしなきゃいけないことを忘れてた。実装してみないとわからないことって色々あるね。
なので、chop_bibnum_listはちょっと変態気味。0001234となってしまった場合は、ゼロ部分だけfreeします。0だとNULLになってしまうので、もうちょっと工夫したほうがいいかな・・・。
うぅん。イマイチです。(後で共通化します)
マイナスの実装方法
もしかすると、-1234を,-4 > -3 > -2 > -1として実装した方がいいかも。そうすれば足し算と引き算を共通化出来る。しかし、マイナスとプラスが混在してしまう・・・むぅぅぅぅ。
もしくは、今の実装で、符号処理を付け加える。
a + -b -> a - b -a + -b -> -(a + b) a - b(a < b) -> -(b - a)
こっちのほうがシンプルそうだ。あ、比較演算子がいるな。
おおっと。よい情報発見
クヌース先生のアルゴリズム本のVolume2に多倍長演算に関する文献が載っているらしい。が、もってな〜い。アレ、ムズいんだよね・・・買うべきか・・・。
Amazon.co.jp: The Art of Computer Programming (2) 日本語版
うは。いちまんえん・・・たけぇ。
比較を実装
比較が必要だとわかってきたので、比較を実装します。
上の桁から見ていくので、再帰です。
/* a > b -> 1, a == b -> 0, a < b -> -1 */ int cmp_bignum_list(bignum_list *a, bignum_list *b) { int res; if (a == NULL && b == NULL) return 0; else if (a == NULL) return -1; else if (b == NULL) return 1; else if (res = cmp_bignum_list(a->next, b->next)) return res; else { if (a->n > b->n) return 1; if (a->n < b->n) return -1; else return 0; } } int cmp_bignum(bignum *a, bignum *b) { if (a->sign > b->sign) return 1; else if (a->sign < b->sign) return -1; else return cmp_bignum_list(a->list, b->list); }
上の桁から見ていって、大小を比較すると。無限リストだと案外大変な事がわかってきた。
ゼロのfreeと同じような感じです。Schemeやってなかったら絶対解けてないな・・・。
反復に直すと早くなりそうです。
おし、これでマイナスの足し算、引き算が実装出来そうだ。
符合つき足し算と引き算を実装
では、比較を利用して、符合つき足し算、引き算を実装します。
bignum_list *add_bignum_list(bignum_list *a, bignum_list *b, int sign) { int carry = 0; int tmp; bignum_list *c = new_bignum_list("0"); bignum_list *head = c; for (;;) { tmp = carry; if (a != NULL) { tmp += a->n; a = a->next; } if (b != NULL) { tmp += b->n * sign; b = b->next; } /* 桁あがりの処理 */ if (tmp < 0) { /* マイナスになったら上の桁から借りる(比較してるので上の桁は必ずあるハズ) */ carry = -1; tmp += 10; } else { carry = tmp / 10; tmp %= 10; } c->n = tmp; /* 次の桁へ */ if (a != NULL || b != NULL || carry == 1) { c->next = new_bignum_list("0"); c = c->next; } else break; } return head; } bignum *add_bignum(bignum *a, bignum *b) { bignum *c = (bignum *) malloc(sizeof (bignum)); int cmp; if (a->sign == b->sign) { /* 符号が同じ */ c->sign = a->sign; c->list = add_bignum_list(a->list, b->list, 1); } else { /* 符号が違う */ if (a->sign == -1) { bignum *tmp = a; a = b; b = tmp; /* swap */ } /* +a, -b */ cmp = cmp_bignum_list(a->list, b->list); /* 符号なし比較 */ if (cmp == 0) { c->sign = 1; c->list = new_bignum_list("0"); } else { if (cmp == 1) { /* 123 - 12 */ c->sign = 1; c->list = add_bignum_list(a->list, b->list, -1); } else { /* 12 - 123 */ c->sign = -1; c->list = add_bignum_list(b->list, a->list, -1); } chop_bibnum_list(c->list); /* 00123 -> 123 */ } } return c; } bignum *sub_bignum(bignum *a, bignum *b) { b->sign *= -1; return add_bignum(a, b); }
わぁ〜い。出来ました〜!!
addとsubを共通化してスッキリです。
長いエントリになってきましたが、まだ掛け算と割り算があるんだな・・・まだまだ続きます。えへへ。