質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

88.03%

多倍長演算の理論

解決済

回答 5

投稿

  • 評価
  • クリップ 2
  • VIEW 8,295

score 1873

お世話になっております。
「多倍長演算」の理論について詳しく知りたいです。

現在、(Double型でも)桁あふれが起こっており、多倍長演算なるものを利用しないといけない状況になっておりますが、いろいろ検索をかけてもよく分かりません。

まず言われているのが、
配列を使って、一桁ずつ計算する
というものを多く見かけました。

そのやり方を詳しく探そうとしていたところ、以下のサイト様を発見しました。
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q1082763270

そこを見ると、C言語で
void Mul(int x[],int y[],int z[]){
    int i,a,b,c;
    a=10000;
    for(i=N-1;i >= 0;--i){
        b=a+x[i]*y[i];
        z[i] = b % 10000;
        a=b / 10000;
    }
}
と、あります。(理論は一切書かれていません)

これが多倍長演算というものなのでしょうが、どのような定理、理論を利用しているのでしょうか?

また、
*何故引数は配列であるか
*10000のあまりを利用したり、10000で割っているのは何故か
*(おそらく)2つの値の計算なのに、何故引数が3つ用意されているのか
などもご教授いただけると幸いです。

よろしくお願いいたします。
  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 過去に投稿した質問と同じ内容の質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 5

checkベストアンサー

+5

ボールドテキスト多倍長演算の実装の基本は、筆算での計算方法です。
一桁同士の足し算、引き算、掛け算(九九の表) があれば、筆算でいくらでも大きな数での計算が
紙の上で行えますよね。
その方法を 配列をつかって行うのです。

筆算では、1桁を 0...9 の範囲の 10 進として処理します。
多倍長演算の実装の場合は、0...999 として処理するといった工夫をします。
(1バイトは 1024 まであらわせるので)

- 大きな整数の四則演算 http://www.macs123.dtdns.net/algo/cpp/cpp071.html

掛け算や割り算では、筆算の方法より計算量が少なくできる方法があります。
Karatsuba, FFT, ニュートン法 ...

円周率の計算、暗号処理では、多倍長の演算が必要になります。

コンパクトに多倍長処理について説明されているページを web 上ではみつけられませんでした。
(多倍長処理についてはたくさんのページがみつかるのですが...)
自分の理解、疑問のレベルにあったページを探してみることをお勧めします。

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/04/21 13:36

    ご回答有難うございます.
    >一桁同士の足し算、引き算、掛け算(九九の表) があれば、筆算でいくらでも大きな数での計算が紙の上で行えますよね。
    なるほど,この理論でやっているわけですね.

    >コンパクトに多倍長処理について説明されているページを web 上ではみつけられませんでした。
    >自分の理解、疑問のレベルにあったページを探してみることをお勧めします
    ありがとうございます,探してみます

    キャンセル

+2

http://fussy.web.fc2.com/algo/algo10-2.htm

ここが分かりやすいかなと思います。
10000で割ったり余りを求めたりしているのは、おそらく10000進数を使っているためだと思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/04/21 13:38

    ご回答有難うございます.

    なるほど,進数を利用して桁数を下げるという考え方…盲点でした.

    キャンセル

0

参考に挙げられているサイトを見るとニュートン法を使う、と明記されています。ニュートン法についてgoogleで調べてみると、理論や計算機の数値計算に使用する例がいくつもヒットします。理論については私も説明できるほど詳しくないのでご自身で調べて理解された方がよいと思います。

>*何故引数は配列であるか 
>*10000のあまりを利用したり、10000で割っているのは何故か 
私も詳しいわけではないのでちゃんとした説明はできませんが、これらはニュートン法の理論に従って反復計算をするためのものだと思います。

>*(おそらく)2つの値の計算なのに、何故引数が3つ用意されているのか 
3つ目の引数は結果を入れるものです。

あと、引用されているコードは演算の一部のみで、それだけでは答えは求められないと思います。参考サイトのコード全体をメイン関数から追ってみた方が理解が深まると思います。

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/04/19 03:19

    ご回答有難うございます。

    申し訳ありません、記載し忘れていました。
    今のところ、まず乗算を利用したいと思い、
    おそらく乗算の多倍長演算であろうMul関数を引用させていただきました。

    >私も詳しいわけではないのでちゃんとした説明はできませんが、これらはニュートン法の理論に従って反復計算をするためのものだと思います。
    申し訳ありません、見落としておりました。
    なるほどこれがニュートン法なのでしょうか……

    キャンセル

0

コンパイルしていませんが、yahoo知恵袋のプログラム、正しく動かない気がします。

katoyさん、naga3さんの張っているリンクではどちらも乗算時にループ文がネストしています。
以下はkatoyさんの方のリンクから乗算部分だけを抜き出しています。

    for ( int v = 0; v < fig2; v++ )
    {
        for ( int u = 0; u < fig1; u++ )
        {
            ans[u + v] += x[u] * y[v];
            // 結果が2桁以上あれば,繰り上がり
            if ( ans[u + v] >= 10 )
            {
                ans[u + v + 1] += ans[u + v] / 10;  // 繰上がり
                ans[u + v] %= 10;                   // 残り
            }
        }
    }

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

  • 2015/04/21 13:38

    ご回答有難うございます.

    抜き出しありがとうございます.
    なんとなく見えてきました.

    キャンセル

-1

誤送信

投稿

編集

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 88.03%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る