[Delphi] BigInteger を作った話

多倍長整数型

型があるプログラミング言語は、概ね整数型や数値型があります。
そして、それらの型は 32bit だったり 64bit などの決まった bit 数で値を格納しています。
そのため、例えば Int32 型だと、-2147483648..2147483647 までしか数を表現できません。
Int64 等も同様である決まった範囲の数しか表現できません。

しかし、それだと 4096 bit を要する計算などができません。

そこで、Delphi 以外のプログラミング言語には概ね標準ライブラリとして多倍長整数型（巨大整数型）が実装されています。
例えば C# なら BigInteger、Java も同じく BigInteger, JavaScript なら BigInt, そして Python ならそもそもの基本型に制限がない、などです。

これらのライブラリや言語を使うとメモリの許す限りどんな大きさの数も表せ、計算できるのです。

しかし、我らが Delphi には未だに標準で多倍長整数型が存在しないのです。
もちろん有志による BigInteger ライブラリは色々存在しています。
たとえば、Delphi For Fun にある DFF Library などです。

でも！僕が多倍長整数型のライブラリを欲したのは 2005 年、弊社のプロダクト (fla:ver) で暗号化ライブラリを実装する必要に迫られたためです。
まだ世の中にこれらのライブラリが存在しない（存在していても見つからなかった）時代だったわけです。

無いなら作るの精神

ということで、2005 年に TBigInteger を作りました。
愚直に作って有るので速度は遅いでしょう。

原理を簡単に説明すると、動的配列を使って１桁に１つの値を格納する様になっています。
↓イメージにすると、このような。

そして、計算は配列の１要素毎に計算して繰り上がりを上の桁に加算していく、というようになっています。

例えば加算なら

procedure TBigInteger.InternalAdd(const iNum: TBigInteger);
var
  Value: Cardinal;
begin
  var Num := NewSameBase(iNum);   // 基数を合せる
  var Len := Length(Num.FDigits); // 加算する桁数
  var SrcLen := Length(FDigits);  // 自分の桁数

  if (Len > SrcLen) then
    Len := Expand(Len - SrcLen);

  var Carry: Cardinal := 0; // 繰り上がる数を格納する変数
  for var i := 0 to Len - 1 do
  begin
    Value := FDigits[i] + Num.FDigits[i] + Carry; // 普通に加算

    Carry := Value div FBase; // 基数で割って次に繰り上がる数を格納しておく
    FDigits[i] := Value mod FBase; // 剰余を値として格納する
  end;

  if (Carry > 0) then // 繰り上がりの数がまだあるなら、再帰で同じ処理をする
  begin
    Expand(1);

    var CarryNum := TBigInteger.Create(FBase);
    CarryNum.Expand(Len + 1);
    CarryNum.FDigits[Len] := Carry;

    InternalAdd(CarryNum);
  end;

  Adjust; // 無駄な配列を削除する
end;

なお、ソースコードにあるように 10 進以外の基数も利用できるようになっています。

このタイミングで公開したのは？

Adobe Flash が終了するため、fla:ver も終了したので、そろそろ公開してもいいかなあとなりました。

なお、暗号用に作ったため実装が必須である ModPow にも対応しています。
ついでに、class で実装されていた物を record に修正してあります。
ただ、これのおかげでさらに計算速度は遅くなっています（record の代入はメモリのコピーになるため）
また、演算子オーバーロードにも対応しているので、普通の数値演算のように使えます。

ソース

ソースは下記に。
クソアプリ Advent Calendar で作ったアプリの一部です。

TBigInteger
https://bitbucket.org/freeonterminate/filpunko/src/master/PK.Math.BigInteger.pas

まとめ

今は、BigInteger ライブラリは色々あるのでお好みの物を使うといいでしょう。
もちろん作ってもいいと思います！！