多倍長整数
出典: フリー百科事典『ウィキペディア(Wikipedia)』
多倍長整数(たばいちょうせいすう)は整数を扱うデータ型の一種。通常の整数型はCPUによって桁数の制限を受けるが、多倍長整数はその制限を越えた値の表現が可能である。
[編集] 概要
通常の整数型が32ビットや64ビットの限定された範囲のCPUが直接扱うデータをそのまま提供するだけなのに対し、多倍長整数はその範囲を超えた整数を扱うために一般的にはハードウェアでなくソフトウェアで実現する。実装方法には、大きいとはいえ扱える限界をあらかじめ定めてある固定多倍長整数と、メモリの許されるかぎり大きな整数まで扱える無限多倍長整数とがある。
[編集] アルゴリズム
加減算は桁数の増加に対し線形に計算量が増大するが、乗算は素朴な方法では2乗に比例して増大する。 このため、大きな桁では乗算の高速なアルゴリズムが必要とされる。 Karatsuba法([1])や高速フーリエ変換などが代表的である。