多倍長整数

出典: フリー百科事典『ウィキペディア（Wikipedia）』

多倍長整数(たばいちょうせいすう)はコンピュータでCPUによって決まる通常の整数型の語長を超えた整数を扱うデータ型の一種である。

[編集] 概要

通常の整数型が32ビットや64ビットの限定された範囲のCPUが直接扱うデータをそのまま提供するだけなのに対し、多倍長整数はその範囲を超えた整数を扱うために一般的にはソフトウェアで実現する。 実装方法には、大きいとはいえ扱える限界をあらかじめ定めてある固定多倍長整数と、許されるかぎり大きな整数まで扱える無限多倍長整数とがある。

[編集] アルゴリズム

加減算は桁数の増加に対し線形に計算量が増大するが、乗算は素朴な方法では2乗に比例して増大する。 このため、大きな桁では乗算の高速なアルゴリズムが必要とされる。 カラツバ法や高速フーリエ変換などが代表的である。