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

多倍長数格納方法

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

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

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

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

多倍長整数

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

桁の配置

  • $a_{n-1}R^{n-1} + a_{n-2}R^{n-2} + \cdots + a_1R + a_0$
  • $a_0R^{n-1} + a_1R^{n-2} + \cdots + a_{n-2}R + a_{n-1}$

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

負の数の表現

  • 符号変数を持つ
  • 桁数を表現する $n$ に負の数を使う

符号変数を持つと処理の分岐が楽になるが、$n$ に負の数を使うと使うメモリ量が少しだけ節約できるメリットがある。

多倍長浮動小数

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

\[ (-1)^s\times(a_0R^{n-1}+a_1R^{n^2}+\cdots+a_{n-2}R+a_{n-1}) \times R^e \]