CodeIQ 巨大な整数の演算に挑戦！の解答（TBcd の紹介）

Delphi / Appmethod Advent Calendar 2014 12/26 の記事です

CodeIQ 巨大な整数の演算に挑戦！の僕の解答です！

本来は、ちゃんと Advent Calendar 開催中に公開する予定でしたが、この問題の締め切りが 12/21 まで延びたので公開を延期していました。


問題の本文は

コラッツの問題が巨大な正の整数でも成り立つことを実証しましょう。

コラッツの問題が「9が50個連続する巨大な50桁の整数」でも成り立つこと(最終的に1になること)を確認できるWindows向けコンソールプログラムを作成してください。

ソースコードは、50行以内且つ、DelphiまたはAppmethodに標準搭載されているデータ型、クラス、ライブラリのみを使用して記述してください。

※コラッツの問題・・
  自然数nに対して、nが奇数なら3をかけて1を加える。
  偶数なら2で割る。
  この処理を繰り返すとすべての自然数が1になる。
  http://ja.wikipedia.org/wiki/コラッツの問題

でした。

これに対して、僕の最初の解答がこちら。

program CollatzMin;
uses
  Data.FmtBcd;
var
  Bcd: TBcd;
  Sup: Integer;
begin
  Bcd := StrToBcd(StringOfChar('9', 50));
  while (Bcd > 1) do
  begin
    Sup := Bcd.Precision and 1;
    if
      ((Bcd.Fraction[Bcd.Precision shr 1 + Sup - 1] shr (Sup shl 2) and 1) > 0)
    then
      Bcd := Bcd * 3 + 1
    else
      Bcd := Bcd / 2;
    Writeln(BcdToStr(Bcd));
  end;
  Readln;
end.

Delphi でお手軽に巨大な整数を扱うと言えばでおなじみの Data.FmtBcd を使いました。
本来は2進化10進数を扱うためのクラスです（2進化10進数についてはリンク先でどうぞ）。
このクラスを使うと 64 桁までの数に対応できます。
問題の本文にあるように今回は 50 桁なので、TBcd で余裕です。
TBcd には operator が定義されているので普通の数のように加減乗除できます。

TBcd を使った結果、上の解答になりました。

ですが、これ 3n + 1 って「必ず偶数になるんじゃね！」→「偶数なら２で割り切れるんじゃね！」と考えて最適化した結果が次のコードです。

program CollatzBcd;
uses
  Data.FmtBcd;
var
  N: TBcd;
  Od: Integer;
begin
  N := StrToBcd(StringOfChar('9', 50));
  while (N > 1) do
  begin
    Od := BcdPrecision(N) and 1;
    Od := N.Fraction[BcdPrecision(N) shr 1 + Od - 1] shr (Od shl 2) and 1;
    N := (N * (1 + Od shl 1) + Od) / 2;
    Writeln(BcdToStr(N));
  end;
  Readln;
end.

結構スッキリしました。
ただ、こちらのコードは最初の一回目の演算結果が表示されないのですが…
とはいえ、解答としてはオッケーでした。

Data パッケージにあるからなのか、あまり知られていない TBcd クラス。
かなり簡単に使えるので、知って置いて損は無いと思います。

：
：

最後に蛇足。
自前で整数演算を実装した物も提出していました。
こちらは、普通に乗算をして繰り上がりや繰り下がりの演算をするものです。

program CollatzBytes;
uses
  System.SysUtils;
const
  COUNT = 50;
  DIGIT = 9;
var
  Bytes: TBytes;
  i, H, L: Integer;
function ToString: String;
var
  i: Integer;
begin
  Result := '';
  for i := High(Bytes) downto Low(Bytes) do
    Result := Result + Bytes[i].ToString;
  Result := Result.TrimLeft(['0']);
end;
begin
  SetLength(Bytes, COUNT * 2);
  for i := 0 to COUNT - 1 do
    Bytes[i] := DIGIT;
 
  while (ToString.Length > 1) or (Bytes[0] > 1) do
  begin
    if (Odd(Bytes[0])) then
    begin
      H := 1;
      for i := Low(Bytes) to High(Bytes) do
      begin
        L := Bytes[i] * 3 + H;
        H := L div 10;
        Bytes[i] := L - H * 10;
      end;
    end
    else begin
      L := 0;
      for i := High(Bytes) downto Low(Bytes) do
      begin
        H := Bytes[i];
        Bytes[i] := Bytes[i] shr 1 + L;
        L := (H and 1) * 5;
      end;
    end;
    Writeln(ToString);
  end;
 
  Readln;
end.

こちらは４９行でギリギリでした！
{$APPTYPE CONSOLE} を入れたら５０行ちょうどでした！あぶない！