Библиотека для работы с большими числами c#

109
14 апреля 2021, 08:20

Я очень сильно хочу сделать свою библиотеку для работы с большими числами. Я начал ее делать. И понял что не знаю как ее сделать.

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);
    }
}

Выше весь код до которого я додумался. И я уверен в том что этот код максимально плох.

Я хочу узнать чего нужно придерживаться когда пишешь такую библиотеку. (Например в чем хранить данные чтобы памяти меньше требовало или какие алгоритмы использовать для увеличения скорости работы) Желательно еще пару примеров. (Можно на любых языках) Ну и литературу какую-нибудь чтобы потом вопросов меньше задавать.

Answer 1

Я сам писал такое, могу дать следующие советы:

  1. Не используйте десятичную систему для хранения данных, это очень далеко от оптимального. Нужно использовать 2^32 систему. Вместо массива байт число будет хранится в массиве uint. При этом вы оптимально используете память, и все операции операции в этой системе счисления будут очень быстрыми. При этом парсинг строк и метод ToString значительно усложнятся.
  2. У вашем коде при перегрузке операторов вы возвращаете строки. Это неправильно. При длинной цепочке вызовов у вас постоянно будет число превращаться в строку и обратно. Если вы будете возвращать BigInt, тогда этого превращения не будет.
  3. Для некоторых операций существуют неочевидные алгоритмы, которые работают быстрее. Например, стандартное умножение работает за O(n^2), умножение по алгоритму Карацубы работает за O(n^1.58). Вам нужно экспериментальным путем определить, при каких значениях длины умножаемых чисел следует использовать один алгоритм, а при каких другой.
  4. Нужно сократить операции выделения памяти к минимуму. Например, в умножении вы используете массив списков. Это очень много объектов в памяти, которые потом сборщик мусора будет очищать. Если вы умножаете число длиной n на число длиной m, то результат будет не длиннее чем n + m. Вы можете создать один массив такой длины и больше не создавать никаких объектов.
  5. Изучайте код других библиотек, там всегда можно подсмотреть интересные идеи для оптимизаций. Сравнивайте быстродействие, ищите узкие места.

Мой BigInteger: https://github.com/Zergatul/ZergatulLib/blob/master/Zergatul/Math/BigInteger.cs

Answer 2

Как-то мне тоже понадобилась длинная арифметика. Но использовать GMP было нельзя, так как длинная арифметика нужна была для микроконтроллеров без операционной системы и кучи. Пришлось написать свою библиотеку С++ шаблонов для работы с длинными целыми числами. Вот ссылка:

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

Там в архиве есть и описание на русском языке.

READ ALSO
Cannot insert explicit value for identity column in table &#39;Devices&#39; when IDENTITY_INSERT is set to OFF – ASP.NET Core

Cannot insert explicit value for identity column in table 'Devices' when IDENTITY_INSERT is set to OFF – ASP.NET Core

Сразу внесу ясность: добавление строки contextDatabase

109
Поменять местами соседние слова

Поменять местами соседние слова

С таким кодом возникает проблема с последним словом:

133
Downcast ComboBox в Win Forms

Downcast ComboBox в Win Forms

У меня есть класс FurnitureComboBox, который является наследником ComboBoxПытаюсь привести ComboBox к FurnitureComboBox (от базового к производному) и чего-то не понимаю

67
ReCaptcha в Selenium WebDriver C#

ReCaptcha в Selenium WebDriver C#

Пытаюсь авторизоваться на сайте, но при решении ReCaptcha руками(ставиться пауза в скрипте), выводится ошибка "Повторите попытку"

82