C# BigInteger計算量

の計算時間(ms)を測定

環境

Windows 8.1
Core i5-4670K 3.40GHz
メモリ16G
.Net Core2.1、コードの最適化あり

結果

C＼n	10	102	103	104	105	106
10	0	0	0	9	899	117362
102	0	0	0	18	1878	244316
103	0	0	0	30	2828	410290
104	0	0	0	36	3950	612554
105	0	0	0	40	4585	765774
106	0	0	0	51	5774	1069028

コード

static void Main(string[] args)
{
    for (var mg = 10L; mg <= (long)1e6; mg *= 10)
    {
        WriteLine($"倍率:{mg}");
        for (var rep = 10; rep <= (long)1e6; rep *= 10)
        {
            WriteLine($"繰り返し:{rep}");
            var sw = new System.Diagnostics.Stopwatch();
            sw.Start();
            BigInteger c = 1;
            BigInteger bMag = (BigInteger)mg;
            for (var i = 0; i < rep; ++i)
                c *= bMag;
            sw.Stop();
            WriteLine($"time:{sw.ElapsedMilliseconds}");
        }
    }
}

背景

先日E - Flattenを解きました。LCMを計算する必要があるのですが、通常の方法(GCD求めてうんぬんかんぬん)だとオーバーフロー、回避のため素因数分解やらなんやらかんやらでごちゃりました。

他の人の提出見るとBigInteger+通常の方法でACしていたのですね。BigInteger使うと時間かかるというイメージがありましたが案外行ける*1？ということで調べてみました。

なおAtCoder上だとで8504ms、使用メモリは50MB以下。上記結果より3倍くらいの時間を見込んどいたほうがよさそうです。

BigIntegerの実装見て計算しろ？誰か強い人に任せる。

*1:上記問題だと最大程度