任意の累乗数をみちびくアルゴリズム

　例えば Ruby はユーザーが特に意識せずとも無限に大きな整数値を扱うことができる。

jnsato.hateblo.jp

　C++では long long 型を利用してもたかだか 64-bit までしか扱うことができない。ビルトイン型として提供されているのはこれが最大となるから、それより大きな値を扱うには工夫が必要である。

■

　Project Euler にて 2¹⁰⁰⁰ を求める問いを与えられた。Ruby なり Python なりを使えばたやすい問題である。しかしこういった便利な言語に甘えずにアルゴリズムを組むならどうするのがよいか、考えてみた。

　で、書いたのが次のコード。std::deque を利用して、下の桁から各桁の積と繰り上がりを順繰りに計算するアルゴリズムである。

#include <cstdio>
#include <deque>

int main()
{
  int c = 2;
  int e = 1000;
  std::deque<int> p; p.push_front(c);

  for (int i = 1; i < e; ++i)
  {
    int carry = 0;
    std::deque<int> n;
    for (int j = p.size() - 1; 0 <= j; --j)
    {
      int s = p[j] * c + carry;
      n.push_front(s % 10);
      carry = s / 10;
    }
    if (carry != 0) n.push_front(carry);
    p = n;
  }

  std::printf("%d^%d = ", c, e);
  for (auto i : p) std::printf("%d", i);
  std::printf("\n");

  return 0;
}

# 実行結果
2^1000 = 10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376

　n^m (n < 10) を想定して書いたコードであって、 10 <= n のケースについてはよく考えていない。 n = 10 においては偶然にしてうまく動いてしまうが、それ以上の場合、指数を十分に大きく取るとところどころの桁でオーバーフローが起きるのか、負に転じる桁が発生する。

# 実行結果
11^178 = -196205743-935628574771553105603298049722910150779438188710688145549549083518975740480663061638639633476100897013485981010563604515686537966613714558926634949087465684780460966676028753081

■

　不完全なコードを掲載するのは気が引ける反面、いまの時点での限界として自分自身のために記録することにする。実際、 2¹⁰⁰⁰ を求めるという当初の目標は達成できているので、そのことにまずは満足しておく。