円周率.jp > 多数桁計算 > 多倍長加減算

多倍長加減算

多倍長の加減算については,基本的に筆算と同様のことをすればよい. 本ページではプログラムを実現する上での注意点をいくつか書き留める. 多倍長整数多倍長浮動小数とがあり, 処理を分ける必要がある.

多倍長整数

多倍長整数での加減算はそれこそ筆算通りの計算でできる. 気持ち程度の選択肢として,計算途中に正規化するものと最後に正規化するものとがある. また,符号を別に持つ形で処理を行う場合は両者の符号関係や絶対値の大きさを比較して処理する必要がある一方, 符号を持たない,非負整数を扱う場合には減算結果が負になった場合にどうするか決めておくか, 必ず負にならないように演算を適用させる必要がある.

AA[A.size-1] A[A.size-2] … A[2] A[1] A[0]
BB[B.size-1] B[B.size-2] … B[2] B[1] B[0]
CA ± BC[C.size-1] C[C.size-2] … C[2] C[1] C[0]

上記のような計算モデルで計算を行う.

(1-A) 後で正規化を行う

3141592653
589793
 
3141117123146 正規化処理
3142182446

まずは後で正規化を行うバージョンから. 以下の計算イメージのように,とりあえず要素ごとの和を求め, 後で正規化を行う. この方式では複数の正規化ルールを取り換える場合に加算ルーチンが 1 つで済む. また,本来やりたいことだけ記述するのでコードの可読性が高い.

2 つの多倍長数 A と B の和を C に代入する擬似プログラムを書く.

C.size = max(A.size, B.size); // C の桁数は A と B の大きい方に合わせる
for( i = 0 ; i < C.size ; ++i ) {
  a_digit = (i >= A.size) ? 0 : A[i]; // 桁数を超えると 0 にする
  b_digit = (i >= B.size) ? 0 : B[i];
  C[i] = a_digit ± b_digit;
}
C.normalize(); // C を正規化

(1-B) 計算中に正規化を行う

続いて,計算途中で正規化を行うバージョン. こちらはキャッシュ系マシンでキャッシュ外のメモリを舐める回数が少なくなるため, 若干ではあるが高速になる(と思う).

3141592653
589793
 
(1)46
3141592653
589793
 
(1)2446
3141592653
589793
 
(1)182446
3141592653
589793
 
3142182446

擬似プログラムは以下の通り.

C.size = max(A.size, B.size); // C の桁数は A と B の大きい方に合わせる
carry = 0;            // 繰り上がり
for( i = 0 ; i < C.size ; ++i ) {
  a_digit = (i >= A.size) ? 0 : A[i];   // 桁数を超えると 0 にする
  b_digit = (i >= B.size) ? 0 : B[i];
  c_digit = a_digit ± b_digit + carry; // 繰り上がりも加える
  carry = Math::floor(c_digit / BASE);  // BASE は基底.除算結果の小数点以下を切り捨てる
  C[i] = c_digit - carry * BASE;        // c_digit を BASE で割った剰余を取っている.
}

(2) 符号を考慮した処理

符号のデータを別に持っている場合,加算と減算の処理を符号だけではなく分ける必要がある. 下記のプログラムは記述量が少なくなる書き方なのであまり処理速度は求めてない.

function add(A, B, C)
{
  // 符号が違う場合は符号を合わせて減算
  if( A.sign() != B.sign() ) { subtract(A, -B, C); }
  // |A| < |B| では左右逆転して演算
  else if( |A| < |B| ) { add(B, A, C); }
  // |A| >= |B| かつ同符号なので演算
  else {
    C = A;
    for( i = 0 ; i < B.size ; ++i ) { C[i] += B[i]; }
    C.normalize(); // C を正規化
  }
}

function subtract(A, B, C)
{
  // 符号が違う場合は符号を合わせて加算
  if( A.sign() != B.sign() ) { add(A, -B, C); }
  // |B| > |A| では C = A - B = -(B - A) に変形して演算
  else if( |A| > |B| ) { subtract(-B, -A, C); }
  // |A|>=|B| かつ同符号という前提になるので絶対値レベルでの減算
  else {
    C = A;
    for( i = 0 ; i < B.size ; ++i ) { C[i] -= B[i]; }
    C.normalize();
  }
}

多倍長浮動小数

浮動小数では仮数部の有効桁数と指数部との関係で足し合わせるインデックスにズレが出てくるが, 基本的には整数と違いが無い. 指数が異なる場合には片方の数値の末尾が端数となるが,好きな方法で丸めると良い.

AA[0].A[1]A[2] … A[A.size-2]A[A.size-1] × BaseA.ex
BB[0].B[1]B[2] … B[B.size-2]B[B.size-1] × BaseB.ex
CA ± BC[0].C[1]C[2] … C[C.size-2]C[C.size-1] × BaseC.ex

以下は上記の計算モデルで計算する.整数とインデックスの貼り方が逆順になっているので注意していただきたい.

// 有効桁数は全て同じ size = A.size = B.size = C.size とする.
if( A.ex >= B.ex ) {
  C = A;
  for( ci = C.ex - B.ex, bi = 0 ; ci < size ; ++ci, ++bi ) {
    C[ci] = C[ci] ± B[bi];
  }
  // 端数の丸め処理
  if( B[bi] > Base / 2 ) {
    C[size - 1] = C[size - 1] ± 1;
  }
} else {
  C = ±B;
  for( ci = C.ex - A.ex, ai = 0 ; ci < size ; ++ci, ++ai ) {
    C[ci] = C[ci] + A[ai];
  }
  // 端数の丸め処理
  if( A[ai] > Base / 2 ) {
    C[size - 1] = C[size - 1] + 1;
  }
}
C.normalize();