Длинная арифметика

Обновлено: 28.09.2019

Длинная арифметика – это набор арифметических операций и операций сравнения, которые выполняются над большими числами, разрядность которых превышает длину стандартных типов данных, при этом длина чисел ограничивается только объемом доступной оперативной памяти. Операции реализуются программно, с использованием средств работы с числами меньших порядков.

Класс BigNumber

Рассмотрим реализацию арифметических операций и операций сравнения для знаковых больших чисел. Для хранения знака числа будем использовать перечисление:

public enum Sign
{
    Minus = -1,
    Plus = 1
}

Для простоты будем разбивать длинное число на отдельные цифры, которые будут хранится в списке:

public class BigNumber
{
    private readonly List<byte> digits = new List<byte>();
}

Создадим набор конструкторов для инициализации больших чисел:

public BigNumber(List<byte> bytes)
{
    digits = bytes.ToList();
    RemoveNulls();
}

public BigNumber(Sign sign, List<byte> bytes)
{
    Sign = sign;
    digits = bytes;
    RemoveNulls();
}

public BigNumber(string s)
{
    if (s.StartsWith("-"))
    {
        Sign = Sign.Minus;
        s = s.Substring(1);
    }

    foreach (var c in s.Reverse())
    {
        digits.Add(Convert.ToByte(c.ToString()));
    }

    RemoveNulls();
}

public BigNumber(uint x) => digits.AddRange(GetBytes(x));

public BigNumber(int x)
{
    if (x < 0)
    {
        Sign = Sign.Minus;
    }

    digits.AddRange(GetBytes((uint)Math.Abs(x)));
}

/// <summary>
/// метод для получения списка цифр из целого беззнакового числа
/// </summary>
/// <param name="num"></param>
/// <returns></returns>
private List<byte> GetBytes(uint num)
{
    var bytes = new List<byte>();
    while (num > 0)
    {
        bytes.Add((byte)(num % 10));
        num /= 10;
    }

    return bytes;
}

/// <summary>
/// метод для удаления лидирующих нулей длинного числа
/// </summary>
private void RemoveNulls()
{
    for (var i = digits.Count - 1; i > 0; i--)
    {
        if (digits[i] == 0)
        {
            digits.RemoveAt(i);
        }
        else
        {
            break;
        }
    }
}

public static BigNumber Zero => new BigNumber(0);

public static BigNumber One => new BigNumber(1);  

Как видно из кода, мы также добавили дополнительные методы для обработки значений, а также наиболее часто используемые значения.

Также в класс необходимо добавить методы:

//длина числа
public int Size => digits.Count;

//знак числа
public Sign Sign { get; private set; } = Sign.Plus;

//получение цифры по индексу
//если индекс больше длины возвращает 0
public byte GetByte(int i) => i < Size ? digits[i] : (byte)0;

//установка цифры по индексу
public void SetByte(int i, byte b)
{
    while (digits.Count <= i)
    {
        digits.Add(0);
    }

    digits[i] = b;
}

/// <summary>
/// метод для получения больших чисел формата valEexp(пример 1E3 = 1000, 5E2 = 500)
/// </summary>
/// <param name="val">значение числа</param>
/// <param name="exp">экспонента(количество нулей после значения val)</param>
/// <returns></returns>
public static BigNumber Exp(byte val, int exp)
{
    var bigInt = Zero;
    bigInt.SetByte(exp, val);
    bigInt.RemoveNulls();
    return bigInt;
}

//преобразование длинного числа в строку
public override string ToString()
{
    var s = new StringBuilder(Sign == Sign.Plus ? "" : "-");

    for (var i = digits.Count - 1; i >= 0; i--)
    {
        s.Append(Convert.ToString(digits[i]));
    }

    return s.ToString();          
}

Сравнение больших чисел

Сравнение длинных чисел производится в три этапа:

  • по знаку;
  • по длине;
  • сравнение цифр числа.

Метод Comparison возвращает:

  • -1 – если a < b;
  • 0 – если числа равны;
  • 1 – если a > b;
private static int Comparison(BigNumber a, BigNumber b, bool ignoreSign = false)
{
    return CompareSign(a, b, ignoreSign);
}

private static int CompareSign(BigNumber a, BigNumber b, bool ignoreSign = false)
{
    if (!ignoreSign)
    {
        if (a.Sign < b.Sign)
        {
            return -1;
        }
        else if (a.Sign > b.Sign)
        {
            return 1;
        }
    }

    return CompareSize(a, b);
}

private static int CompareSize(BigNumber a, BigNumber b)
{
    if (a.Size < b.Size)
    {
        return -1;
    }
    else if (a.Size > b.Size)
    {
        return 1;
    }

    return CompareDigits(a, b);
}

private static int CompareDigits(BigNumber a, BigNumber b)
{
    var maxLength = Math.Max(a.Size, b.Size);
    for (var i = maxLength; i >= 0; i--)
    {
        if (a.GetByte(i) < b.GetByte(i))
        {
            return -1;
        }
        else if (a.GetByte(i) > b.GetByte(i))
        {
            return 1;
        }
    }

    return 0;
}

При этом в самом начале числа сравниваются по знаку, если знаки равны, сравниваем длину, если и она равна, то сравниваем последовательно все цифры длинных чисел.

Перегрузка операторов сравнения

public static bool operator <(BigNumber a, BigNumber b) => Comparison(a, b) < 0;

public static bool operator >(BigNumber a, BigNumber b) => Comparison(a, b) > 0;

public static bool operator <=(BigNumber a, BigNumber b) => Comparison(a, b) <= 0;

public static bool operator >=(BigNumber a, BigNumber b) => Comparison(a, b) >= 0;

public static bool operator ==(BigNumber a, BigNumber b) => Comparison(a, b) == 0;

public static bool operator !=(BigNumber a, BigNumber b) => Comparison(a, b) != 0;

public override bool Equals(object obj) => !(obj is BigNumber) ? false : this == (BigNumber)obj;

Сложение длинных чисел

Используется метод вычисления в столбик знакомый нам с детства.

private static BigNumber Add(BigNumber a, BigNumber b)
{
    var digits = new List<byte>();

    var maxLength = Math.Max(a.Size, b.Size);
    byte t = 0;
    for (int i = 0; i < maxLength; i++)
    {
        byte sum = (byte)(a.GetByte(i) + b.GetByte(i) + t);
        if (sum > 10)
        {
            sum -= 10;
            t = 1;
        }
        else
        {
            t = 0;
        }

        digits.Add(sum);
    }

    if (t > 0)
    {
        digits.Add(t);
    }

    return new BigNumber(a.Sign, digits);
}

Вычитание двух больших чисел

Вычисление разности больших чисел реализуется подобно сложению. При этом числа сравниваются и от большего вычитается меньшее, а результату присваивается знак большего из чисел.

private static BigNumber Substract(BigNumber a, BigNumber b)
{
    var digits = new List<byte>();

    BigNumber max = Zero;
    BigNumber min = Zero;

    //сравниваем числа игнорируя знак
    var compare = Comparison(a, b, ignoreSign: true);

    switch (compare)
    {
        case -1:
            min = a;
            max = b;
            break;
        case 0:
            //если числа равны возвращаем 0
            return Zero;
        case 1:
            min = b;
            max = a;
            break;
    }
    
    //из большего вычитаем меньшее
    var maxLength = Math.Max(a.Size, b.Size);

    var t = 0;
    for (var i = 0; i < maxLength; i++)
    {
        var s = max.GetByte(i) - min.GetByte(i) - t;
        if (s < 0)
        {
            s += 10;
            t = 1;
        }
        else
        {
            t = 0;
        }

        digits.Add((byte)s);
    }

    return new BigNumber(max.Sign, digits);
}

Умножение двух больших чисел

Реализация операции умножения отличается от стандартного умножения в столбик, однако сам принцип сохраняется. Каждая цифра числа перемножается на цифру другого с последующим суммированием.

private static BigNumber Multiply(BigNumber a, BigNumber b)
{            
    var retValue = Zero;

    for (var i = 0; i < a.Size; i++)
    {
        for (int j = 0, carry = 0; (j < b.Size) || (carry > 0); j++)
        {
            var cur = retValue.GetByte(i + j) + a.GetByte(i) * b.GetByte(j) + carry;
            retValue.SetByte(i + j, (byte)(cur % 10));
            carry = cur / 10;
        }
    }

    retValue.Sign = a.Sign == b.Sign ? Sign.Plus : Sign.Minus;
    return retValue;
}

Деление одного длинного числа на другое

Деление одного большого числа на другое реализовано путем поиска наибольшего числа, результат умножения которого на второе число, ближе всего к первому.

private static BigNumber Div(BigNumber a, BigNumber b)
{
    var retValue = Zero;
    var curValue = Zero;

    for (var i = a.Size - 1; i >= 0; i--)
    {
        curValue += Exp(a.GetByte(i), i);

        var x = 0;
        var l = 0;
        var r = 10;
        while (l <= r)
        {
            var m = (l + r) / 2;
            var cur = b * Exp((byte)m,i);
            if (cur <= curValue)
            {
                x = m;
                l = m + 1;
            }
            else
            {
                r = m - 1;
            }
        }

        retValue.SetByte(i, (byte)(x % 10));
        var t = b * Exp((byte)x, i);
        curValue = curValue - t;
    }

    retValue.RemoveNulls();

    retValue.Sign = a.Sign == b.Sign ? Sign.Plus : Sign.Minus;
    return retValue;
}

Вычисление остатка от деления больших чисел

Остаток от деления вычисляется подобным к предыдущему методом.

private static BigNumber Mod(BigNumber a, BigNumber b)
{
    var retValue = Zero;

    for (var i = a.Size - 1; i >= 0; i--)
    {
        retValue += Exp(a.GetByte(i), i);

        var x = 0;
        var l = 0;
        var r = 10;

        while (l <= r)
        {
            var m = (l + r) >> 1;
            var cur = b * Exp((byte)m, i);
            if (cur <= retValue)
            {
                x = m;
                l = m + 1;
            }
            else
            {
                r = m - 1;
            }
        }

        retValue -= b * Exp((byte)x, i);
    }

    retValue.RemoveNulls();

    retValue.Sign = a.Sign == b.Sign ? Sign.Plus : Sign.Minus;
    return retValue;
}

Перегрузка арифметических операторов

Для удобства перегрузим арифметические операторы класса BigNumber.

// унарный минус(изменение знака числа)
public static BigNumber operator -(BigNumber a)
{
    a.Sign = a.Sign == Sign.Plus ? Sign.Minus : Sign.Plus;
    return a;
}

//сложение
public static BigNumber operator +(BigNumber a, BigNumber b) => a.Sign == b.Sign
        ? Add(a, b)
        : Substract(a, b);

//вычитание
public static BigNumber operator -(BigNumber a, BigNumber b) => a + -b;

//умножение
public static BigNumber operator *(BigNumber a, BigNumber b) => Multiply(a, b);

//целочисленное деление(без остатка)
public static BigNumber operator /(BigNumber a, BigNumber b) => Div(a, b);

//остаток от деления
public static BigNumber operator %(BigNumber a, BigNumber b) => Mod(a, b);

Полный код класса

Показать код
Поделиться: Vk Ok
comments powered by Disqus