多桁数の整数同士の掛け算についてだ。

<関数名>
  mpMul —- 多倍長整数同士の乗算

<形式>
  void mpMul(int *ret, int *a, int *b);

<引数>
  ret (出力) 多倍長整数同士の乗算の結果(a * b)
  a, b (入力) 多倍長整数

<関数値>
  なし

<注意事項>
  配列の各要素 ai(i は 1 以上)は1語を表し、1語で表し得る最大の整数は 9999 。語の長さは a0 の値で表す。すなわち、多倍長整数は

      anKn-1+an-1Kn-2+…+a2K+a1

   で表現する。ただし、K=10000、n=a0
  
用例
  本関数以外に、キー入力に 関数 mpStr2Num()数字列を多倍長整数に)、画面表示に 関数 mpNum2Str()多倍長整数を数字列に)も使う。

<関数本体>
  mpMul.c

<説明>
  乗算は加減算ほど単純でなく、いろいろ工夫の余地がある。実用上または理論上の観点から興味深い方法がいくつも考えられている。

  乗算について考えよう。a、bをそれぞれm、n語とすると、積c=a*bはm+n 語以下となる。通常の筆算と同様の方法で、乗数bの1語ごとをaに掛け、それらの和は積cとなる。

  この方法では、bのn語をそれぞれaのm語に掛けるので、m*n回の繰り返しとなる。したがって、計算に必要な時間はO(mn)。

Comments are closed.

Post Navigation