C #3.0 で多倍長演算 (Microsoft.Dynamic.dll)

C#の多倍長整数ライブラリ

　ここ数日 IronPythonとC#の連携について調べてたんですが、IronPythonに同梱されてる DLL に多倍長整数クラス Microsoft.Scripting.Math.BigIntegerがあることに気づきました。

　C# というか .net framework 3.5 まで多倍長演算ライブラリがありませんでした。公式ライブラリでの唯一の解決方法は .net framework 2.0 で配布されてた J# の BigInteger の利用でした。
　この J#、 .net framework 3.0 でリストラされ、VS2008には入ってません。まぁ、今でも2.0時代のライブラリは使えるんですが、消えゆくJ#をいつまでも使うのはどこか抵抗がある気がします。

　その代替手段として、こんな方法もありなんじゃないかと。

サンプルコード

　VisualC# 2008 Express と IronPython 2.6.1 で動作確認。

　IronPythonは ここからダウンロードできます。
　インストーラー起動するのが嫌な人は、download の下にある 「More View all downloads」からIronPython-XXX-Bin.zip を落とすといいでしょう。必要なのはその中にある「Microsoft.Dynamic.dll」だけです。

　Consoleアプリのプロジェクトを作って参照設定でMicrosoft.Dynamic.dll を参照。プロジェクト名は SampleBigIntegerとしました。

テスト実行クラス

//////////////////////////////////////////////////////
// Program.cs
//////////////////////////////////////////////////////
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using Microsoft.Scripting.Math;

namespace SampleBigInteger
{
    class Program
    {
        static void Main(string[] args)
        {
            // 2の1000乗を求める。
            BigInteger a = 2;
            Console.WriteLine("2^1000 = {0}", a.Power(1000));

            // 1000の階乗を求める。
            Console.WriteLine("1000! = {0}", BigIntegerHelper.Factorial(1000));

            // --------------------------------------------
            // 文字列からBigIntegerを生成して計算
            // --------------------------------------------
            BigInteger n1 = BigIntegerHelper.CreateFromString("11111111111111111111111111111111111111111111111111");
            BigInteger n2 = BigIntegerHelper.CreateFromString("777777777777777777777777777777777777");

            // 和
            BigInteger n3 = n1 + n2;
            Console.WriteLine("plus  : {0}", n3);

            // 積
            BigInteger n4 = n1 * n2;
            Console.WriteLine("multi : {0}", n4);

            // 商
            BigInteger n5 = n1 / n2;
            Console.WriteLine("div   : {0}", n5);

            // 剰余
            BigInteger n6 = n1 % n2;
            Console.WriteLine("mod   : {0}", n6);

            //他にもMicrosoft.Scripting.Math.BigIntegerには、
            // Power, Square, Log などのメソッドがあります。
        }
    }
}

BigIntegerのヘルパー

//////////////////////////////////////////////////////
// BigIntegerHelper.cs
//////////////////////////////////////////////////////
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Text.RegularExpressions;
using Microsoft.Scripting.Math;

namespace Microsoft.Scripting.Math
{
    class BigIntegerHelper
    {
        /// <summary>
        /// 十進数文字列チェック用正規表現オブジェクト
        /// </summary>
        private static readonly Regex digitRegex = new Regex(@"^-?\d+$");

        /// <summary>
        /// 文字列を分割処理するときの分割長
        /// </summary>
        private static readonly int splitLength = int.MaxValue.ToString().Length - 1;

        /// <summary>
        /// 文字列を何進数として扱うか
        /// </summary>
        private static readonly int numberBase = (int)System.Math.Pow(10, splitLength);

        /// <summary>
        /// 文字列からBigIntegerのインスタンスを生成。
        /// 十進数のみサポート。radixを指定できるようにしたらもっといいかも。
        /// </summary>
        /// <param name="number">0〜9のみで構成された十進数をあらわす文字列。先頭文字に限って'-'を許容する</param>
        /// <returns>生成したBigIntegerオブジェクト</returns>
        public static BigInteger CreateFromString(string number)
        {
            if (!digitRegex.IsMatch(number))
            {
                throw new ArgumentException();
            }

            BigInteger result = 0;
            int startpos = 0;

            int sign = 1;
            if (number.StartsWith("-"))
            {
                sign = -1;
                startpos++;
            }

            int rest = number.Length % splitLength;
            if (rest != 0)
            {
                string subst = number.Substring(0, rest);
                result = uint.Parse(subst);
                startpos += rest;
            }

            for (; startpos < number.Length; startpos += splitLength)
            {
                string substr = number.Substring(startpos, splitLength);
                result = result * numberBase + uint.Parse(substr);
            }

            return result * sign;
        }

        /// <summary>
        /// 階乗計算
        /// </summary>
        /// <param name="number">階乗を求める数</param>
        /// <returns>計算結果</returns>
        public static BigInteger Factorial(uint number)
        {
            BigInteger result = 1;
            for (; number > 1; number--)
            {
                result *= number;
            }
            return result;
        }

        /// <summary>
        /// 階乗計算
        /// </summary>
        /// <param name="number">階乗を求める数</param>
        /// <returns>計算結果</returns>
        public static BigInteger Factorial(BigInteger number)
        {
            if (number.IsNegative())
            {
                throw new ArgumentException();
            }

            return Factorial((uint)number);
        }
    }
}

　J#のBigIntegerと比べると、演算子オーバーロードのおかげで四則演算が組み込み整数同様に行えます。

　ちなみに .net framework 4.0 では晴れて多倍長ライブラリが標準に入ってくるらしいです。そうなったらこんなことする必要もなくなります。