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

Ruby は 64-bit より大きい整数値をどう扱っているか? - ユユユユユ (https://jnsato.hateblo.jp/entry/2020/06/04/230000)

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

 Project Euler にて 21000 を求める問いを与えられた。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

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

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

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