Как преобразовать строку в массив uint с основанием 2^32

111
16 апреля 2021, 06:50

Подскажите пожалуйста как из например "12413523578274952895672975235" сделать массив uint[] digits в котором будут храниться коэффициенты разложения этого длинного числа с основанием 2^32.

Смотрел в исходниках библиотеки System.Numerics, но ничего понять не смог.
Подскажите алгоритм который парсит строку в массив uint[] digits, где digits[i] коэффициент разложения данного числа с основанием 2^32

Answer 1

Подходов для преобразования может быть несколько: можно реализовать деление в столбик и стандартный алгоритм для перевода числа в систему с другим основанием, а можно воспользоваться подходом из System.Numerics, в котором преобразование можно свести к следующему алгоритму:

создаем пустой объект большого числа, эквивалентный 0.
проход по строке:
  умножаем число на 10
  добавляем к числу цифру из строки

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

  1. умножение на число
  2. добавление числа.

Со сложением все просто: обычное сложение в столбик

  1. добавляем число к младшему разряду
  2. если полученное значение меньше основания закончить
  3. иначе перенести лишнее в старший разряд

С умножением аналогично, умножаем каждый разряд на переданное число и переносим лишнее в старшие разряды.

Итоговый код класса может выглядеть так:

class BN
{
    private List<uint> coefs;
    private const long BASE = (long)uint.MaxValue + 1;
    public BN(uint init = 0)
    {
        coefs = new List<uint>() { init };
    }
    public void Add(uint val)
    {
        long carry = val;
        for (int i = 0; i < coefs.Count; i++)
        {
            var sum = coefs[i] + carry; // вычисляем сумму
            coefs[i] = (uint)(sum % BASE); // нормализуем значение
            carry = sum / BASE; // вычисляем лишнее для переноса в старший разряд
            if (carry == 0) // если переносить нечего, то и цикл продолжать не нужно
            {
                break;
            }
        }
        if (carry != 0) // если после выхода из цикла осталось лишнее, добавляем еще один разряд
        {
            coefs.Add((uint)carry);
        }
    }
    public void Mul(uint val)
    {
        var dVal = (decimal)val;
        var carry = 0m;
        for (int i = 0; i < coefs.Count; i++)
        {
            var mul = coefs[i] * dVal + carry; // вычисляем произведение и добавляем то, что пришло от младших разрядов
            coefs[i] = (uint)(mul % BASE); // нормализуем значение
            carry = Math.Floor(mul / BASE); // вычисляем лишнее для переноса в старший разряд
        }
        while(carry != 0) // если после выхода осталось лишнее
                          // добавляем необходимое количество разрядов
        {
            coefs.Add((uint)(carry % BASE)); 
            carry = Math.Floor(carry / BASE);
        }
    }
    public static BN Parse(string v)
    {
        var bn = new BN(0); // создаем 0
        foreach (var c in v) // бежим по строке
        {
            bn.Mul(10); // умножаем на 10
            bn.Add(uint.Parse(c.ToString())); // добавляем число из строки
        }
        return bn;
    }
}
READ ALSO
Как отобразить данные пользователя в Layout?

Как отобразить данные пользователя в Layout?

Бьюсь с сей проблемой уже некоторое времяСуть такова

96
Работа с event Action, отписка от события

Работа с event Action, отписка от события

Как в такой ситуации можно отписать метод? Отписка, используя (-=) после Invoke не работает, метод все равно вызывается

103
Как объединить и сложить статистику просмотров по дням из двух таблиц?

Как объединить и сложить статистику просмотров по дням из двух таблиц?

Нужно объединить статистику из двух таблиц с группировкой по дням (day)p1, p2 - разделы сайта, здесь только для наглядности

131