2012/04/01(日)C# で BigInteger

はてブ数 2012/04/01 07:37 プログラミング::C#つーさ

とりあえず10進数で2300桁ぐらい扱える全然BigじゃないBigInt。負の値は扱えない。
256のとこを大きくしたら扱える桁数が増える。

割り算と剰余演算子作るのめんどくさくて作ってないけど、
たいてい必要になるのってその辺なんだよなー。もじゅろ10億7とかさー。
というわけで、longのもじゅろだけはとれるよーにしといた。

実戦で使える速度が出るかどうかは未検証。
まぁでもそういう問題は、たぶん、計算量的に無理なようにできてるでしょうね。

public class BigInt : IComparable<BigInt>, IEquatable<BigInt> {
    long[] value = new long[256];
    const long M = 1000000000L;
    const int K = 9; // Mの0が9個ある
    public BigInt() { }
    public BigInt(long l) { value[0] = l; value = (One * this).value; }

    public static BigInt Parse(string s) {
        BigInt ret = new BigInt();
        for (int i = 0; i < (s.Length + K - 1) / K; i++)
            ret.value[i] = long.Parse(s.Substring(Math.Max(0, s.Length - (i + 1) * K), Math.Min(K, s.Length - i * K)));
        return ret;
    }

    public override string ToString() {
        Array.Reverse(value);
        string s = string.Join("", Array.ConvertAll(value, delegate(long l) { return l.ToString("000000000"); }));
        int i = s.IndexOfAny(new char[] { '1', '2', '3', '4', '5', '6', '7', '8', '9', });
        Array.Reverse(value);
        return i != -1 ? s.Remove(0, i) : "0";
    }

    public static BigInt operator +(BigInt a, BigInt b) {
        BigInt ret = new BigInt();
        long carry = 0;
        for (int i = 0; i < ret.value.Length; i++) {
            long t = a.value[i] + b.value[i] + carry;
            if (t >= M) { ret.value[i] = t - M; carry = 1; }
            else { ret.value[i] = t; carry = 0; }
        }
        return ret;
    }

    public static BigInt operator -(BigInt a, BigInt b) {
        BigInt ret = new BigInt();
        long carry = 1;
        for (int i = 0; i < ret.value.Length; i++) {
            long t = a.value[i] - b.value[i] - 1 + carry + M;
            if (t >= M) { ret.value[i] = t - M; carry = 1; }
            else { ret.value[i] = t; carry = 0; }
        }
        return ret;
    }

    public static BigInt operator *(BigInt a, BigInt b) {
        BigInt ret = new BigInt();
        for (int j = 0; j < b.value.Length; j++) {
            if (b.value[j] == 0) continue; // たいていbのがちっさいはず
            for (int i = 0; i < a.value.Length; i++) {
            long carry = 0;
                if (i + j >= ret.value.Length) continue;
                long t = ret.value[i + j] + a.value[i] * b.value[j] + carry;
                ret.value[i + j] = t % M;
                carry = t / M;
            }
        }
        return ret;
    }

    //public static BigInt operator /(BigInt a, BigInt b) { throw new NotImplementedException(/*_*/); }
    //public static BigInt operator %(BigInt a, BigInt b) { throw new NotImplementedException(/*_*/); }

    public static BigInt operator /(BigInt a, long b) {
        BigInt ret = new BigInt();
        long carry = 0;
        for (int i = a.value.Length - 1; i >= 0; i--) {
            long t = carry * M + a.value[i];
            ret.value[i] = t / b;
            carry = t % b;
        }
        return ret;
    }

    public static long operator %(BigInt a, long b) {
        long ret = 0;
        for (int i = a.value.Length - 1; i >= 0; i--)
            ret = (ret * M + a.value[i]) % b;
        return ret;
    }

    public static bool operator ==(BigInt a, BigInt b) { return a.CompareTo(b) == 0; }
    public static bool operator !=(BigInt a, BigInt b) { return a.CompareTo(b) != 0; }
    public static bool operator <(BigInt a, BigInt b) { return a.CompareTo(b) < 0; }
    public static bool operator >(BigInt a, BigInt b) { return a.CompareTo(b) > 0; }
    public static bool operator <=(BigInt a, BigInt b) { return a.CompareTo(b) <= 0; }
    public static bool operator >=(BigInt a, BigInt b) { return a.CompareTo(b) >= 0; }

    public static readonly BigInt Zero = BigInt.Parse("0");
    public static readonly BigInt One = BigInt.Parse("1");

    public int CompareTo(BigInt other) {
        for (int i = value.Length - 1; i >= 0; i--) {
            int r = value[i].CompareTo(other.value[i]);
            if (r != 0) return r;
        }
        return 0;
    }

    public override bool Equals(object obj) { if (obj is BigInt) return Equals((BigInt)obj); else return false; }
    public override int GetHashCode() { long r = 0; for (int i = 0; i < value.Length; i++) r ^= value[i]; return (int)(r >> 32 ^ r); }
    public bool Equals(BigInt other) { return this == other; }
}


public class Program {
    static void Main() {
        BigInt a = BigInt.Parse("12345678987654321");
        BigInt b = BigInt.Parse("12345678987654321");
        Console.WriteLine(a.ToString());
        Console.WriteLine((a + b).ToString());
        Console.WriteLine((a - b).ToString());
        Console.WriteLine((a * b).ToString());
        Console.WriteLine((a == b).ToString());
        Console.WriteLine((a % 9).ToString());


    }
}

.NET 4が使えるなら、標準のBigIntegerを使いたまえ
っていうか実装されるのおせーよ