RError.com

RError.com Logo RError.com Logo

RError.com Navigation

  • 主页

Mobile menu

Close
  • 主页
  • 系统&网络
    • 热门问题
    • 最新问题
    • 标签
  • Ubuntu
    • 热门问题
    • 最新问题
    • 标签
  • 帮助
主页 / 问题 / 1004643
Accepted
Павел Ериков
Павел Ериков
Asked:2020-07-19 19:12:59 +0000 UTC2020-07-19 19:12:59 +0000 UTC 2020-07-19 19:12:59 +0000 UTC

用于处理大量数字的库 c#

  • 772

我真的很想制作自己的库来处理大量数据。我开始做。我意识到我不知道该怎么做。

public struct BigInt
{
    private byte[] Value { get; set; }

    public BigInt(string value)
    {
        if (value.Length != 0)
            Value = new byte[value.Length];
        else
        {
            Value = null;
            return;
        }
        for (int i = value.Length - 1; i >= 0; i--)
            Value[i] = (byte)value[i];
    }

    public BigInt(byte[] value) { this.Value = value; }

    public override string ToString() => Encoding.Default.GetString(Value);

    public static implicit operator BigInt(string num) => new BigInt(num);

    public static implicit operator string(BigInt num) => Encoding.Default.GetString(num.Value);

    public static string operator +(BigInt c1, BigInt c2) => Addition(c1.Value, c2.Value);

    public static string operator +(BigInt c1, string c2) => Addition(c1.Value, Encoding.Default.GetBytes(c2));

    public static string operator *(BigInt c1, BigInt c2) => Multiplication(c1.Value, c2.Value);

    public static string operator *(BigInt c1, string c2) => Multiplication(c1.Value, Encoding.Default.GetBytes(c2));

    public static string Addition(byte[] x, byte[] y)
    {
        List<byte> result = new List<byte>();
        int c = 0, d = 0;
        List<byte> z = new List<byte>();
        if(x.Length > y.Length)
        {
            z.InsertRange(0, Encoding.Default.GetBytes(new String('0', x.Length - y.Length).ToCharArray()));
            z.AddRange(y);
            y = z.ToArray();
        }
        else
        {
            z.InsertRange(0, Encoding.Default.GetBytes(new String('0', y.Length - x.Length).ToCharArray()));
            z.AddRange(x);
            x = z.ToArray();
        }
        for(int i = x.Length-1; i>=0; i--)
        {
            byte a = x[i];
            byte b = y[i];
            c = (d + (a % 48) + (b % 48)) % 10;
            result.Add((byte)c);
            d = (d + a % 48 + b % 48) / 10;
        }
        if (d != 0)
            result.Add((byte)d);
        result.Reverse();
        return string.Join("", result);
    }

    public static string Multiplication(byte[] x, byte[] y)
    {
        List<byte>[] result = new List<byte>[y.Length];
        for (int i = 0; i < y.Length; i++)
        {
            int c = 0;
            int d = 0;
            List<byte> array = new List<byte>();
            for (int j = 0; j < x.Length; j++)
            {
                byte a = x[x.Length - 1 - j];
                byte b = y[y.Length - 1 - i];
                c = (d + (a % 48) * (b % 48)) % 10;
                array.Add((byte)c);
                d = (d + (a % 48) * (b % 48)) / 10;
            }
            if (d > 0)
                array.Add((byte)d);
            result[i] = array;
        }

        for (int i = 0; i < result.Length; i++)
            for (int j = 0; j < result[i].Count / 2; j++)
            {
                byte temp = result[i][j];
                result[i][j] = result[i][result[i].Count - 1 - j];
                result[i][result[i].Count - 1 - j] = temp;
            }

        if (result.Length > 1)
            for (int i = 1; i < result.Length; i++)
                for (int j = 0; j < result.Length - i; j++)
                    result[j + i].Add((byte)0);

        if (result.Length > 1)
        {
            for (int i = 0; i < result.Length - 1; i++)
            {
                List<byte> z = result[0];
                for (int j = 0; j < z.Count; j++)
                    z[j] += 48;
                result[0] = new List<byte>(Encoding.Default.GetBytes(Addition(z.ToArray(), result[i + 1].ToArray())));
            }
            return Encoding.Default.GetString(result[0].ToArray());
        }
        return String.Join("", result[0]);
    }

    public static string Pow(string x, int degrees)
    {
        if (degrees == 0) return "1";
        if (degrees == 1) return x;
        byte[] result = Encoding.Default.GetBytes(x);
        byte[] num = result;
        for (int i = 2; i <= degrees; i++)
            result = Encoding.Default.GetBytes(Multiplication(result, num));
        return Encoding.Default.GetString(result);
    }

    public static string Factorial(int number)
    {
        if (number == 0) return "1";
        if (number <= 2) return number.ToString();
        byte[] result = Encoding.Default.GetBytes((6).ToString());
        for (int i = 4; i <= number; i++)
            result = Encoding.Default.GetBytes(Multiplication(result, Encoding.Default.GetBytes(i.ToString())));
        return Encoding.Default.GetString(result);
    }
}

以上是我想出的所有代码。而且我确信这段代码是尽可能糟糕的。

我想知道在编写这样的库时要遵循什么。(例如,将数据存储在哪里以便它需要更少的内存或使用什么算法来提高工作速度)更多的例子是可取的。(任何语言都可以)嗯,一些文学作品,这样你以后就不必问问题了。

c#
  • 2 2 个回答
  • 10 Views

2 个回答

  • Voted
  1. Best Answer
    Zergatul
    2020-07-19T20:12:36Z2020-07-19T20:12:36Z

    我自己写了这个,我可以给出以下建议:

    1. 不要使用十进制系统进行数据存储,它远非最佳。您需要使用2^32该系统。该数字将存储在数组中,而不是字节数组uint。这样一来,您就可以优化使用内存,并且这个数字系统中的所有操作操作都会非常快。在这种情况下,字符串解析和方法会ToString变得复杂得多。
    2. 在您的代码中,当您重载运算符时,您将返回字符串。这是不对的。通过一长串的调用,你会不断地将一个数字变成一个字符串,反之亦然。如果您返回BigInt,则不会发生这种转变。
    3. 对于某些操作,有一些非显而易见的算法可以更快地工作。例如,标准乘法适用于O(n^2),根据 Karatsuba 算法的乘法适用于O(n^1.58)。您需要通过实验确定一种算法应该使用的乘数长度,以及另一种算法。
    4. 有必要将内存分配操作减少到最低限度。例如,在乘法中,您使用列表数组。这是内存中的大量对象,然后垃圾收集器将对其进行清理。如果将长度数乘以长度n数m,结果将不会超过n + m。您可以创建一个该长度的数组,而不再创建任何对象。
    5. 研究其他库的代码,你总能从中窥探到有趣的优化想法。比较性能,寻找瓶颈。

    我的大整数:https ://github.com/Zergatul/ZergatulLib/blob/master/Zergatul/Math/BigInteger.cs

    • 2
  2. pepsicoca1
    2020-07-19T22:36:49Z2020-07-19T22:36:49Z

    不知何故,我还需要长算术。但是使用 GMP 是不可能的,因为没有操作系统和堆的微控制器需要很长的算法。我必须编写自己的 C++ 模板库来处理长整数。链接在这里:

    https://sourceforge.net/projects/muntl/?source=frontpage&position=5

    档案中还有俄语的描述。

    • 1

相关问题

Sidebar

Stats

  • 问题 10021
  • Answers 30001
  • 最佳答案 8000
  • 用户 6900
  • 常问
  • 回答
  • Marko Smith

    根据浏览器窗口的大小调整背景图案的大小

    • 2 个回答
  • Marko Smith

    理解for循环的执行逻辑

    • 1 个回答
  • Marko Smith

    复制动态数组时出错(C++)

    • 1 个回答
  • Marko Smith

    Or and If,elif,else 构造[重复]

    • 1 个回答
  • Marko Smith

    如何构建支持 x64 的 APK

    • 1 个回答
  • Marko Smith

    如何使按钮的输入宽度?

    • 2 个回答
  • Marko Smith

    如何显示对象变量的名称?

    • 3 个回答
  • Marko Smith

    如何循环一个函数?

    • 1 个回答
  • Marko Smith

    LOWORD 宏有什么作用?

    • 2 个回答
  • Marko Smith

    从字符串的开头删除直到并包括一个字符

    • 2 个回答
  • Martin Hope
    Alexandr_TT 2020年新年大赛! 2020-12-20 18:20:21 +0000 UTC
  • Martin Hope
    Alexandr_TT 圣诞树动画 2020-12-23 00:38:08 +0000 UTC
  • Martin Hope
    Air 究竟是什么标识了网站访问者? 2020-11-03 15:49:20 +0000 UTC
  • Martin Hope
    Qwertiy 号码显示 9223372036854775807 2020-07-11 18:16:49 +0000 UTC
  • Martin Hope
    user216109 如何为黑客设下陷阱,或充分击退攻击? 2020-05-10 02:22:52 +0000 UTC
  • Martin Hope
    Qwertiy 并变成3个无穷大 2020-11-06 07:15:57 +0000 UTC
  • Martin Hope
    koks_rs 什么是样板代码? 2020-10-27 15:43:19 +0000 UTC
  • Martin Hope
    Sirop4ik 向 git 提交发布的正确方法是什么? 2020-10-05 00:02:00 +0000 UTC
  • Martin Hope
    faoxis 为什么在这么多示例中函数都称为 foo? 2020-08-15 04:42:49 +0000 UTC
  • Martin Hope
    Pavel Mayorov 如何从事件或回调函数中返回值?或者至少等他们完成。 2020-08-11 16:49:28 +0000 UTC

热门标签

javascript python java php c# c++ html android jquery mysql

Explore

  • 主页
  • 问题
    • 热门问题
    • 最新问题
  • 标签
  • 帮助

Footer

RError.com

关于我们

  • 关于我们
  • 联系我们

Legal Stuff

  • Privacy Policy

帮助

© 2023 RError.com All Rights Reserve   沪ICP备12040472号-5