多倍長演算の理論

Question

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

現在、（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つ用意されているのか
などもご教授いただけると幸いです。

よろしくお願いいたします。

Answer 1

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

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

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

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

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

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

Comments

[nnahito]

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

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

Answer 2

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

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

Comments

[nnahito]

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

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

Answer 3

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

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

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

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

Comments

[nnahito]

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

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

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

Answer 4

コンパイルしていませんが、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];
            // 結果が２桁以上あれば，繰り上がり
            if ( ans[u + v] >= 10 )
            {
                ans[u + v + 1] += ans[u + v] / 10;  // 繰上がり
                ans[u + v] %= 10;                   // 残り
            }
        }
    }

Comments

[nnahito]

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

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

Answer 5

誤送信