東大の演習問題に挑戦(4) - 多倍長演算編

次は多倍長演算です。

アルゴリズムとデータ構造演習 - C第1回

課題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を共通化してスッキリです。

長いエントリになってきましたが、まだ掛け算と割り算があるんだな・・・まだまだ続きます。えへへ。