Как правильно реализовать ввод в мой класс BigInteger?

Question

Вот мой класс:

class BigInteger
{
private:
    const size_t base = 65536; 
    vector<size_t> digits;
public:
    friend istream& operator >> (istream& in, BigInteger& object);
};

istream& operator >> (istream& in, BigInteger& object) //работает независимо от base в 10-ричной системе счисления
{
    string input;
    in >> input;
    object.digits.clear(); 

    for (string::reverse_iterator i = input.rbegin(); i != input.rend(); i++)
    {
        object.digits.push_back(*i - '0');
    }
    return in;
}

Однако есть проблема: я хочу сделать так, чтобы числа со входа переводились в нужную систему счисления (в моем случае size_t base = 65536) и уже эти числа поступали на вход моего объекта класса. Вопрос как это реализовать? Ведь по идее, надо как-то делить мои числа и узнавать от них остатки? Но как? Кроме идеи вычитания (ну ведь деление - сокращенное вычитание) и даже она кажется мне достаточно сложноватой для реализации. и не смотря на это она мне ооооочень долгой. Вопрос как реализовать мою идею?

Answer 1

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

https://sourceforge.net/projects/muntl/

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

Answer 2

На C++ объяснять долго и лезут всякие "правильные" вещи вроде чтения из потока, функции на итераторах и тому подобное. Поэтому псевдокод, который на самом деле рабочий код на Python. Перевод на C++ оставляю читателю.

from_list_base - функция чтения числа из списка десятичных цифр. В качестве аккумулятора длинное целое. Начинаем с нуля, с каждой новой цифрой умножаем аккумулятор на 10 и добавляем эту цифру к сумме:

def from_list_base(base, digits):
    n = BigInteger(0)
    for d in digits:
        n = n * base + d
    return n
   
assert repr(from_list_base(10, [1, 2, 3, 4])) == '1234'

Цифры можно группировать, база должна быть степенью 10. Тогда исходное текстовое представление числа удобно разрезать на кусочки и каждый кусочек превратить в число средствами C++. Позволяет уменьшить число умножений в основном цикле. Конечно база должна помещаться в целочисленный тип С++ (в вашем случае 10000, не больше):

assert repr(from_list_base(100, [12, 34])) == '1234'

Теперь мы умеем читать число из строки любой длины. Чтение не самое быстрое, так как число в аккумуляторе все время удлиняется и операция n * base делается всё дольше и дольше. Время работы будет N^2, где N - число цифр в исходном тексте.

Если в типе BigInteger реализовано быстрое умножение чисел, то можно прочитать число из текста быстрее. Эффект будет заметен только на достаточно длинных текстах - сотни, тысячи цифр.

Умножение в столбик для чисел из N и M цифр занимает время пропорциональное MN. Быстрое умножение - это любой алгоритм который работает быстрее: умножение Карацубы, Шёнхаге-Штрассена.

Если такое умножение реализовано, то читать можно быстрее при помощи "разделяй и властвуй". Цифры числа разбиваются на две половинки (digits[:m] - старшие разряды и digits[m:] - младшие разряды), каждая читается рекурсивно, затем составляется результат: 10^p * high + low. Если цифр мало, запускаем базовый метод. Граница в этом примере занижена, её нужно подбирать измеряя производительность:

threshould = 2

def from_list(base, digits):
    if len(digits) < threshould:
        return from_list_base(base, digits)

    m = len(digits) // 2
    high = from_list(base, digits[:m])
    low = from_list(base, digits[m:])
    factor = power(BigInteger(base), len(digits) - m)
    return factor * high + low

Функция power - быстрое возведение в степень. Обычное последовательное умножение в цикле уничтожит все усилия по ускорению:

def power(n, e):
    if e == 0:
        return BigInteger(1)
    if e % 2 == 0:
        n2 = power(n, e // 2)
        return n2 * n2
    return n * power(n, e - 1)

БЛОГ НА HUSL

Как правильно реализовать ввод в мой класс BigInteger?

Ответы (2 шт):