円周率.jp (http://xn--w6q13e505b.jp/method/store.html)

多倍長数格納方法

この格納方法をどのようにするかによって各演算の詳細に違いが出てくるため,演算を実装する前に決める必要がある.

以下の例示では,多倍長数の各桁を表す数列 a[] と基底 B を用いるが,プログラムの変数のまま表現するとオーバーフローなどで混乱が起きるかもしれないので表現形式を変更する.

\[ {\tt a[i]}\ {\rm (プログラム的)} \rightarrow a_i\ {\rm (ここでの表現)} \] \[ {\tt B}\ {\rm (プログラム的)} \rightarrow B\ {\rm (ここでの表現)} \]

で多倍長数の表現の仕方を例示する.

多倍長整数

いろいろな点で選択肢があるので,それぞれその選択肢を表す.

桁の配置

  • $a_{n-1}B^{n-1} + a_{n-2}B^{n-2} + \cdots + a_1B + a_0$
  • $a_0B^{n-1} + a_1B^{n-2} + \cdots + a_{n-2}B + a_{n-1}$

後者は人間の記述的にはわかりやすい一方、 前者はメモリ領域の追加をするだけで繰り上がり処理が楽になるというように 処理が簡単になりやすい。

各桁の表現範囲

  • $0\leq a_i \lt B$
  • $-\dfrac{B}{2} \leq a_i \dfrac{B}{2}$

前者は直感的に分かりやすい。また、符号なし変数でも処理が可能である。 一方で後者は正規化の処理が若干複雑になるものの、FFT を使った乗算での計算誤差が小さくなるメリットがある。

負の数の表現

  • $a_{\rm 最上位} \lt 0$ で表現
  • 符号変数を持つ
  • 桁数を表現する $n$ に負の数を使う

多倍長浮動小数

基本的には多倍長整数に加えて,指数を表す変数 e を持てばよい. ただ,その際に仮数部の小数点をどこに置くか,という程度の選択肢がある.

\[ (-1)^s\times(a_0B^{n-1}+a_1B^{n^2}+\cdots+a_{n-2}B+a_{n-1}) \times B^e \]