連結リストを用いて大きな桁数の掛け算を行う方法がわからない。

Question

前提

入力で与えられる 2 つの文字列が表す正の整数に対し掛け算を行う問題を解いています。入力の長さは限定されていないため、節点の要素として各桁の数を含む連結リストを用いて表す必要があります。私は掛け算の筆算のやり方しか思い浮かばず、それぞれの桁の数を掛け合わせた後にどのようにすれば良いのかが分かりません。連結リストをどのように使えば掛け算をすることができるのか教えてください。ちなみに連結リストを用いた足し算や配列を用いた掛け算は出来ました。

Comments

[jimbe]

足し算が出来て掛け算が出来ないのはどういうことでしょう。
足し算のコードを提示してみては如何ですか。

>掛け算の筆算のやり方しか思い浮かばず、それぞれの桁の数を掛け合わせた後にどのようにすれば良いのか

筆算ではどのような手順だったか、もう当然過ぎて意識しなくなっているものと思います。意識して確認しては如何でしょうか。(『それぞれの桁の数を掛け合わせ』?)
https://sugaku.fun/longhand-of-multiplication/

[Zuishin]

足し算は順に足していくだけですが、掛け算は桁ごとに掛け算したものを足さなければいけないので少し難易度が上がります。
と言っても、足し算と同じ手順で一桁目をかけたものと、同じ手順で二桁目をかけたものを桁を変えて足し算し、それを繰り返せばいいので、足し算ができるならそう難しくはありません。
作るべき関数は、足し算関数と、大きな数値に一桁の数値を掛ける関数です。
複数桁に対応した関数は、それらを呼び出すことで実現できます。
配列を使ったものが作れるなら、これが作れない理由はないので、頑張ってみてください。

[sawaawa]

了解です。やってみます。

Answer 1

scanf の時点で長さに制限がかかってしまうので、 getc 使えみたいな条件があるのかもしれませんが。

#include <stdio.h>
#include <stdlib.h>

typedef struct node {
  struct node *next, *prev;
  int value;
} NODE;

/** 新たな NODE を返す. node が NULL で無ければその node の後にリンクし、 NULL なら自身にリンクする */
NODE *create_node(NODE *node, int value) {
  NODE *p = malloc(sizeof(NODE));
  p->value = value;
  if(node) {
    p->next = node->next;
    p->prev = node;
    p->next->prev = p;
    p->prev->next = p;
  } else {
    p->next = p->prev = p;
  }
  return p;
}

//正規化. head を返す
NODE *normalize_list(NODE *head) {
  if(head->next == head) {
    create_node(head, 0);
  } else {
    //ゼロサプレス
    for(NODE *p=head->next, *next; p->value==0 && p->next!=head; p=next) {
      next = p->next;
      p->next->prev = p->prev;
      p->prev->next = p->next;
      free(p);
    }
  }
  return head;
}

/** 数字列から、桁毎を NODE としたリストを返す */
NODE *create_list(char *str) {
  NODE *head = create_node(NULL, 0);
  for(char c; (c=*str++); ) create_node(head->prev, c-'0');
  return normalize_list(head);
}

/** node を含めた全 NODE 解放 */
void free_list(NODE *node) {
  for(NODE *p=node->next, *next; p!=node; p=next) {
    next = p->next;
    free(p);
  }
  free(node);
}

/** 加算して新たなリストを返す */
NODE *addition_list(NODE *augend, NODE *addend) {
  NODE *answer = create_node(NULL, 0);
  int carry = 0;
  for(NODE *p1=augend->prev, *p2=addend->prev; p1!=augend || p2!=addend || carry; ) {
    int v1 = p1 != augend ? p1->value : 0;
    int v2 = p2 != addend ? p2->value : 0;
    int a = v1 + v2 + carry;
    carry = a / 10;
    create_node(answer, a % 10);
    if(p1 != augend) p1 = p1->prev;
    if(p2 != addend) p2 = p2->prev;
  }
  return normalize_list(answer);
}

/** リストに 1 桁値を乗算して新たなリストを返す. multiplier: 0 ～ 9 */
NODE *multiplication_list_sub(NODE *multiplicand, int multiplier) {
  NODE *answer = create_node(NULL, 0);
  int carry = 0;
  for(NODE *p=multiplicand->prev; p!=multiplicand || carry; ) {
    int a = p->value * multiplier + carry;
    carry = a / 10;
    create_node(answer, a % 10);
    if(p != multiplicand) p = p->prev;
  }
  return normalize_list(answer);
}

/** 乗算して新たなリストを返す */
NODE *multiplication_list(NODE *multiplicand, NODE *multiplier) {
  NODE *answer = create_node(NULL, 0);
  int digits = 0;
  for(NODE *p=multiplier->prev; p!=multiplier; p=p->prev, digits++) {
    NODE *sub = multiplication_list_sub(multiplicand, p->value);
    for(int i=0; i<digits; i++) create_node(sub->prev, 0); //桁合わせ
    NODE *a = addition_list(answer, sub);
    free_list(answer);
    free_list(sub);
    answer = a;
  }
  return normalize_list(answer);
}

/** リストを表示する(テキスト・改行付き) */
void print_list(NODE *head, char *pretext) {
  if(pretext != NULL) printf(pretext);
  for(NODE *p=head->next; p!=head; p=p->next) printf("%d", p->value);
  printf("\n");
}

char buf[2][1024]; //スタックフレームサイズに制限されないようグローバル

int main(int argc, char *argv[]) {
  scanf("%s %s", buf[0], buf[1]);

  NODE *list1 = create_list(buf[0]);
  print_list(list1, "list1: ");
  NODE *list2 = create_list(buf[1]);
  print_list(list2, "list2: ");

  NODE *add = addition_list(list1, list2);
  print_list(add, "add: ");
  free_list(add);

  NODE *multi = multiplication_list(list1, list2);
  print_list(multi, "multi: ");
  free_list(multi);

  free_list(list1);
  free_list(list2);

  return 0;
}

123456789
9876543210
list1: 123456789
list2: 9876543210
add: 9999999999
multi: 1219326311126352690

---

scanf で無く getc でちゃんと(?)制限無しにするなら

/** file から(数字で無い文字をスキップ後、数字で無い文字が現れるまでの)数字列を読み込み、桁毎を NODE としたリストを返す */
NODE *create_list_from_file(FILE *file) {
  NODE *head = create_node(NULL, 0);
  for(int c; (c=getc(file)) != EOF; ) {
    if(c < '0' || '9' < c) {
      if(head->next == head) continue;
      break;
    }
    create_node(head->prev, c-'0');
  }
  if(head->next == head && feof(file)) return NULL; //何も無いまま EOF は許さない
  return normalize_list(head);
}

を追加して main を

//char buf[2][1024]; //不要

int main(int argc, char *argv[]) {
  NODE *list1 = create_list_from_file(stdin);
  if(list1 == NULL) { fprintf(stderr, "error: list1 が見つからない."); return -1; }
  NODE *list2 = create_list_from_file(stdin);
  if(list2 == NULL) { fprintf(stderr, "error: list2 が見つからない."); return -1; }

  print_list(list1, "list1: ");
  print_list(list2, "list2: ");

  NODE *add = addition_list(list1, list2);
  print_list(add, "add: ");
  free_list(add);

  NODE *multi = multiplication_list(list1, list2);
  print_list(multi, "multi: ");
  free_list(multi);

  free_list(list1);
  free_list(list2);

  return 0;
}

とすれば同じ結果になります。

Comments

[sawaawa]

確かにgetcの指示ですね。
双方向リストの発想はありませんでした。
ありがとうございます。

[jimbe]

計算は下位桁から、表示は上位桁からですので、双方向が無難と考えました。
「やってみます」とのことでしたが、ご自身のコードはどう出来ましたでしょうか。

Answer 2

各桁の値を要素に持つ連結リストを用いて掛け算をするのであれば、下記の記事が参考になりそうです。本題の掛け算は「2-5. 大きな数の掛け算」で説明されていますが、それより前で説明されている加減算と繰り上げ·繰り下げ処理も重要なので、見たほうが良いと思います。

超高速！多倍長整数の計算手法【前編：大きな数の四則計算を圧倒的な速度で！】 - Qiita
https://qiita.com/square1001/items/1aa12e04934b6e749962

Comments

[jimbe]

リンク先、長そうなので最後までは見ていないのですが、質問の課題は連結リストを使うことが主題(の1つ)で、大きな数の演算が出来れば良いというのでは無いように思います。

[luuguas]

ご指摘ありがとうございます。連結リストを使うという条件をすっかり忘れていました。連結リストを使うのであれば、リンク先の記事の 「2-5. 大きな数の掛け算」の図のように、2重ループを使って各桁の九九を計算·合計した後、1重ループで繰り上がり処理をすれば良さそうです。

[jimbe]

>2重ループを使って各桁の九九を計算·合計した後、1重ループで繰り上がり処理

本当に長大な桁同士の掛け算だった場合、"各桁の九九を計算·合計" の合計の段階でノードの保持可能値の範囲を超える可能性があり、繰り上がりを最後に1回だけでというのは危なそうです。 (実質は問題無いかもしれませんが。)

[luuguas]

2重ループ内で、九九を合計する毎にオーバーフロー(あるいは予め設定した上限値を超えないか)のチェックを行い、超えそうなら繰り上がり処理をするという風にすれば良さそうですね。