none
想要運算超過100位數的正整數值ulong型別的變數不夠用,怎辦 RRS feed

  • 問題

  • 想要運算超過100位數的正整數值ulong型別的變數只有8byte  20個位數 非常不夠用,怎辦
    用Double雖然可以到300多位,但我要的是精確值
    我去問老師
    他給我的答案是用陣列把每個位數個別裝進每個元素裡
    再寫處理加減乘除的方法
     
    有沒有辦法自定義資料型別可以達到128bytes的空間可以用
    2007年11月23日 上午 10:25

解答

所有回覆

  • 你的老師沒說錯啊,這種類型的問題被稱為 "大數問題",你可以參考:http://dhcp.tcgs.tc.edu.tw/c/p018.htm

     

    基本上就是要把每個數字都切成單一字元放到陣列中,然後撰寫運算的程式碼,如此就可以不受位數的限制。

    你可以把它集合成一個類別,以後直接由類別取用即可。

    2007年11月23日 上午 10:56
    版主
  • 你可以參考 C# BigInteger Class 的實作方法...

    2007年11月23日 上午 11:26
  • 這是我寫出來的大數運算
    我只要用到加法和乘法
    a+b是plus(a,b)
    a*b是cross(a,b)
    運算的輸出結果都沒問題
    可是運作效率很差
    會不會是整數和字串間的轉換太頻繁阿
    我要計算3240次乘法運算
    要20秒左右才能完成
    要算到上萬次等個10分鐘也不會好
    考試的要求是要在10秒鐘內完成輸出
    希望我設的變數名稱不會太糟
       
    程式碼區塊
    class BigInt
        {
            public string plus(string a, string b)
            {
                List<string> la = new List<string>();
                List<string> lb = new List<string>();
                string oout = "";
                if (a.Length > b.Length)
                {
                    string c = a;
                    a = b;
                    b = c;
                }
                for (int i = a.Length - 1; i >= 0; i--)
                {
                    la.Add(a.Substring(i, 1));
                }
                for (int i = b.Length - 1; i >= 0; i--)
                {
                    lb.Add(b.Substring(i, 1));
                }
                for (int i = 0; i <= la.Count - 1; i++)
                {
                    int temp = int.Parse(la[i]) + int.Parse(lb[i]);
                    lb[i] = temp.ToString();
                }
                for (int d = 0; d <= lb.Count - 2; d++)
                {
                    if (lb[d].Length == 2)
                    {
                        lb[d] = Convert.ToString(int.Parse(lb[d]) - 10);
                        lb[d + 1] = Convert.ToString(int.Parse(lb[d + 1]) + 1);
                    }
                }
                if (lb[lb.Count - 1].Length == 2)
                {
                    lb[lb.Count - 1] = lb[lb.Count - 1].Remove(0, 1);
                    lb.Add("1");
                }
                for (int i = lb.Count - 1; i >= 0; i--)
                {
                    oout += lb[i];
                }
                return oout;
            }
            public string cross(string a, int b)
            {
                BigInt c = new BigInt();
                string o = a;
                for (int i = 0; i <= b - 2; i++)
                {
                    o = c.plus(a, o);
                }
                return o;
            }
        }

     

     

    2007年11月23日 下午 02:43
  • 經過改良
    運算速度變很快了
    感謝各位高手提供的資料
    BigInt.iTOl(整數)  將整數放入不定長度的byte陣列
    BigInt.StrTOl(字串)  將字串放入不定長度的byte陣列
    BigInt.plus(不定長度的byte陣列,不定長度的byte陣列)  將2個不定長度的byte陣列相加
    BigInt.cross(不定長度的byte陣列,不定長度的byte陣列)  將2個不定長度的byte陣列相乘
    BigInt.outStr(不定長度的byte陣列)  將不定長度的byte陣列轉成字串
    程式碼區塊
        class BigInt
        {
            public static List<byte> iTOl(int d)
            {
                List<byte> o = new List<byte>();
                string temp = d.ToString();
                for (int i = temp.Length - 1; i >= 0; i--)
                {
                    o.Add(byte.Parse(temp.Substring(i, 1)));
                }
                return o;
            }
            public static List<byte> StrTOl(string d)
            {
                List<byte> o = new List<byte>();
                for (int i = d.Length - 1; i >= 0; i--)
                {
                    o.Add(byte.Parse(d.Substring(i, 1)));
                }
                return o;
            }
            public static List<byte> plus(List<byte> a, List<byte> b)
            {
                if (a.Count < b.Count)
                {
                    List<byte> c = a;
                    a = b;
                    b = c;
                }
                for (int i = 0; i <= b.Count - 1; i++)
                {
                    a[i] += b[i];
                }
                for (int i = 0; i <= a.Count - 2; i++)
                {
                    if (a[i] >= 10)
                    {
                        a[i] -= 10;
                        a[i + 1] += 1;
                    }
                }
                if (a[a.Count - 1] >= 10)
                {
                    a[a.Count - 1] -= 10;
                    a.Add(1);
                }
                return a;
            }
            public static List<byte> cross(List<byte> a, List<byte> b)
            {
                byte[] t = new byte[3000];\\乘法時的位數上限下面的2999為同一東西
                List<byte> o = new List<byte>();
                if (a.Count < b.Count)
                {
                    List<byte> c = a;
                    a = b;
                    b = c;
                }
                for (int i = 0; i <= a.Count - 1; i++)
                {
                    for (int c = 0; c <= b.Count - 1; c++)
                    {
                        t[i + c] += (byte)(a[i] * b[c]);
                    }
                }
                for (int i = 0; i <= 2999; i++)
                {
                    if (t[i] >= 10)
                    {
                        t[i + 1] += (byte)(t[i] / 10);
                        t[i] %= 10;
                    }
                }
                int index = 0;
                for (int i = 2999; i >= 0; i--)
                {
                    if (t[i] != 0)
                    {
                        index = i;
                        break;
                    }
                }
                for (int i = 0; i <= index; i++)
                {
                    o.Add(t[i]);
                }
                return o;
            }
            public static string outStr(List<byte> a)
            {
                string o = "";
                for (int i = a.Count - 1; i >= 0; i--)
                {
                    o += a[i].ToString();
                }
                return o;
            }
        }

     

     

    2007年11月24日 下午 05:28