C# 實現無限位數十進制大整數：支援加法、乘法與隱含轉換

設計目標

突破 int/long 範圍限制，實現任意位數的非負整數運算（加法、乘法），並提供直觀的運算子多載與字串/整數隱含轉換。

核心資料結構

• 以 List<byte> 儲存每一位數字（0-9），低位在前（Index 0 = 個位），便於進位處理。
• 建構子接受 byte[]、List<byte>、string、int。

關鍵演算法

1. 單位數乘大整數（含位移）

private static List<byte> Multiply(List<byte> s, byte d, int power)
{
    var result = new List<byte>();
    // 位移：在低位補 power 個 0
    for (int i = 0; i < power; i++) result.Add(0);

    byte carry = 0;
    foreach (byte si in s)
    {
        byte r = (byte)(si * d + carry);
        result.Add((byte)(r % 10));
        carry = (byte)(r / 10);
    }
    if (carry > 0) result.Add(carry);
    return result;
}

2. 大整數加法

private static List<byte> Plus(List<byte> s1, List<byte> s2)
{
    // 補齊長度
    if (s1.Count > s2.Count) s2.AddRange(new byte[s1.Count - s2.Count]);
    else if (s2.Count > s1.Count) s1.AddRange(new byte[s2.Count - s1.Count]);

    var result = new List<byte>();
    byte carry = 0;
    for (int i = 0; i < s1.Count; i++)
    {
        byte r = (byte)(s1[i] + s2[i] + carry);
        result.Add((byte)(r % 10));
        carry = (byte)(r / 10);
    }
    if (carry > 0) result.Add(carry);
    return result;
}

運算子多載與轉換

// 字串 → DecimalNumber（反序儲存）
public static implicit operator DecimalNumber(string value)
{
    var data = new List<byte>();
    for (int i = value.Length - 1; i >= 0; i--)
        data.Add(byte.Parse(value[i].ToString()));
    return new DecimalNumber(data);
}

// int → DecimalNumber
public static implicit operator DecimalNumber(int value) => value.ToString();

// 遞增
public static DecimalNumber operator ++(DecimalNumber d) => d + new DecimalNumber(new byte[] { 1 });

// 加法：DecimalNumber + int/DecimalNumber
public static DecimalNumber operator +(DecimalNumber d1, int d2) => d1 + d2.ToString();
public static DecimalNumber operator +(DecimalNumber d1, DecimalNumber d2) => new DecimalNumber(Plus(d1.Data, d2.Data));

// 乘法：模擬手算豎式乘法
public static DecimalNumber operator *(DecimalNumber d1, DecimalNumber d2)
{
    var partials = new List<List<byte>>();
    for (int i = 0; i < d1.Data.Count; i++)
        partials.Add(Multiply(d2.Data, d1.Data[i], i));

    var result = new List<byte>();
    foreach (var p in partials) result = Plus(p, result);
    return new DecimalNumber(result);
}

// 輸出：高位在前
public override string ToString()
{
    var sb = new StringBuilder();
    for (int i = _Data.Count - 1; i >= 0; i--) sb.Append(_Data[i]);
    return sb.ToString();
}

應用示範：尋找最小階乘位數 ≥ 3

int d = 1;
DecimalNumber factorial = 1;
while (factorial.Length < 3)
{
    d++;
    factorial = factorial * d;
}
Console.WriteLine(d); // 輸出 7 (7! = 5040)

擴充方向

• 減法、除法、模運算
• 比較運算子 (<, >, ==)
• 支援負數（加入正負號旗標）
• 優化乘法：Karatsuba、FFT 乘法（百萬位數以上）
• 實作 IComparable, IEquatable<T>, ISpanFormattable

結語

大整數實作是理解任意精度運算原理的最佳練習。雖然 .NET 內建 System.Numerics.BigInteger 已極度優化，但手寫一遍能深入掌握進位、位移、豎式乘法等核心邏輯，為密碼學、區塊鏈、科學計算打下堅實基礎。