Как реализовать большой int в C++
Я хотел бы реализовать большой класс int в C++ как упражнение по программированию - класс, который может обрабатывать числа, большие чем long int. Я знаю, что уже есть несколько реализаций с открытым исходным кодом, но я бы хотел написать свою собственную. Я пытаюсь понять, что такое правильный подход.
Я понимаю, что общая стратегия состоит в том, чтобы получить число в виде строки, а затем разбить его на меньшие числа (например, на одну цифру) и поместить их в массив. На этом этапе должно быть относительно просто реализовать различные операторы сравнения. Моя главная задача - как бы я реализовал такие вещи, как сложение и умножение.
Я ищу общий подход и совет в отличие от реального рабочего кода.
16 ответов
Что нужно учитывать для большого класса int:
Математические операторы: +, -, /, *, % Не забывайте, что ваш класс может находиться по обе стороны от оператора, что операторы могут быть объединены в цепочки, что одним из операндов может быть int, float, double и т. Д.,
Операторы ввода / вывода: >>, << Здесь вы узнаете, как правильно создать свой класс из пользовательского ввода, а также как отформатировать его для вывода.
Преобразования / Приведения: выясните, к каким типам / классам должен быть конвертирован ваш большой int-класс, и как правильно обрабатывать преобразование. Быстрый список будет включать в себя double и float, и может включать int (с надлежащей проверкой границ) и complex (при условии, что он может обрабатывать диапазон).
Забавный вызов.:)
Я предполагаю, что вы хотите целые числа произвольной длины. Я предлагаю следующий подход:
Рассмотрим двоичную природу типа данных "int". Подумайте об использовании простых бинарных операций, чтобы эмулировать действия схем в вашем процессоре, когда они что-то добавляют. В случае, если вы заинтересованы более подробно, рассмотрите эту статью в Википедии о полусуммерах и полных сумматорах. Вы будете делать что-то похожее на это, но вы можете понизиться до такого низкого уровня - но, будучи ленивым, я подумал, что просто воздержусь и найду еще более простое решение.
Но прежде чем углубляться в алгоритмические подробности о сложении, вычитании, умножении, давайте найдем некоторую структуру данных. Конечно, простой способ хранить вещи в std::vector.
template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};
Возможно, вы захотите подумать, хотите ли вы сделать вектор фиксированного размера и предварительно выделить его. Причина в том, что для разнообразных операций вам придется пройти через каждый элемент вектора - O(n). Возможно, вы захотите узнать, насколько сложной будет операция, и фиксированное n делает именно это.
Но теперь о некоторых алгоритмах работы с числами. Вы можете сделать это на логическом уровне, но мы будем использовать эту магическую мощность процессора для вычисления результатов. Но то, что мы извлечем из логической иллюстрации Half- и FullAdders, - это то, как они работают с переносами. В качестве примера рассмотрим, как бы вы реализовали оператор +=. Для каждого числа в BigInt<>::value_ вы добавите их и посмотрите, не приведет ли результат к какой-либо форме переноса. Мы не будем делать это побитно, но будем полагаться на природу нашего BaseType (будь то long или int, short или что-то еще): он переполнен.
Конечно, если вы добавите два числа, результат должен быть больше, чем большее из этих чисел, верно? Если это не так, то результат переполнен.
template< class BaseType >
BigInt< BaseType >& BigInt< BaseType >::operator += (BigInt< BaseType > const& operand)
{
BT count, carry = 0;
for (count = 0; count < std::max(value_.size(), operand.value_.size(); count++)
{
BT op0 = count < value_.size() ? value_.at(count) : 0,
op1 = count < operand.value_.size() ? operand.value_.at(count) : 0;
BT digits_result = op0 + op1 + carry;
if (digits_result-carry < std::max(op0, op1)
{
BT carry_old = carry;
carry = digits_result;
digits_result = (op0 + op1 + carry) >> sizeof(BT)*8; // NOTE [1]
}
else carry = 0;
}
return *this;
}
// NOTE 1: I did not test this code. And I am not sure if this will work; if it does
// not, then you must restrict BaseType to be the second biggest type
// available, i.e. a 32-bit int when you have a 64-bit long. Then use
// a temporary or a cast to the mightier type and retrieve the upper bits.
// Or you do it bitwise. ;-)
Другая арифметическая операция идет аналогично. Черт возьми, вы даже можете использовать stl-функторы std::plus и std::minus, std::times и std::divides, ..., но помните о переносе.:) Вы также можете реализовать умножение и деление, используя операторы "плюс" и "минус", но это очень медленно, потому что это пересчитало бы результаты, которые вы уже рассчитывали в предыдущих вызовах "плюс" и "минус" в каждой итерации. Есть много хороших алгоритмов для этой простой задачи, используйте Википедию или Интернет.
И, конечно же, вы должны реализовать стандартные операторы, такие как operator<< (просто сдвиньте каждое значение в value_ влево для n битов, начиная с value_.size()-1... о, и помни о переносе:), operator< - Вы можете даже немного оптимизировать здесь, проверяя приблизительное количество цифр с size() первый. И так далее. Тогда сделайте ваш класс полезным, используя befriendig std::ostream operator<<,
Надеюсь, что этот подход полезен!
Там есть полный раздел об этом: [Искусство компьютерного программирования, том 2: Полу числовые алгоритмы, раздел 4.3 Арифметика с множественной точностью, с. 265-318 (изд.3)]. Вы можете найти другой интересный материал в главе 4 "Арифметика".
Если вы действительно не хотите смотреть на другую реализацию, задумывались ли вы о том, что вы хотите узнать? Есть неисчислимые ошибки, которые можно сделать, и выявление их поучительно, а также опасно. Существуют также проблемы в определении важных вычислительных возможностей и наличии соответствующих структур хранения для избежания серьезных проблем с производительностью.
Вопрос для вас: как вы собираетесь протестировать свою реализацию и как вы предлагаете продемонстрировать, что ее арифметика верна?
Возможно, вы захотите протестировать другую реализацию (не глядя на то, как она это делает), но для ее обобщения потребуется больше, чем ожидание мучительного уровня тестирования. Не забудьте рассмотреть режимы сбоев (из-за проблем с памятью, из-за стека, слишком долгой работы и т. Д.).
Повеселись!
Сложение, вероятно, должно быть сделано в стандартном линейном алгоритме времени
но для умножения вы можете попробовать http://en.wikipedia.org/wiki/Karatsuba_algorithm
Не забывайте, что вам не нужно ограничивать себя цифрами 0-9, т. Е. Использовать байты в качестве цифр (0-255), и вы все равно можете делать арифметику длинной руки так же, как и для десятичных цифр. Вы могли бы даже использовать массив long.
Когда у вас есть цифры числа в массиве, вы можете делать сложение и умножение точно так же, как вы делали бы их от руки.
Я не уверен, что использование строки - это правильный путь - хотя я сам никогда не писал код, я думаю, что использование массива базового числового типа может быть лучшим решением. Идея состоит в том, что вы просто расширите то, что у вас уже есть, точно так же, как процессор расширяет один бит в целое число.
Например, если у вас есть структура
typedef struct {
int high, low;
} BiggerInt;
Затем вы можете вручную выполнить собственные операции над каждой из "цифр" (в данном случае, высокой и низкой), учитывая условия переполнения:
BiggerInt add( const BiggerInt *lhs, const BiggerInt *rhs ) {
BiggerInt ret;
/* Ideally, you'd want a better way to check for overflow conditions */
if ( rhs->high < INT_MAX - lhs->high ) {
/* With a variable-length (a real) BigInt, you'd allocate some more room here */
}
ret.high = lhs->high + rhs->high;
if ( rhs->low < INT_MAX - lhs->low ) {
/* No overflow */
ret.low = lhs->low + rhs->low;
}
else {
/* Overflow */
ret.high += 1;
ret.low = lhs->low - ( INT_MAX - rhs->low ); /* Right? */
}
return ret;
}
Это немного упрощенный пример, но должно быть достаточно очевидно, как расширить структуру, которая имеет переменное число любого базового числового класса, который вы используете.
Используйте алгоритмы, которые вы изучили с 1 по 4 класс.
Начните со столбца единиц, затем десятков и так далее.
Как говорили другие, делайте это старомодным длинным способом, но держитесь подальше от выполнения всего этого на базе 10. Я бы предложил сделать все это на базе 65536 и хранить вещи в массиве длинных позиций.
Посмотрите здесь, чтобы увидеть, как GMP реализует свои алгоритмы.
Если ваша целевая архитектура поддерживает представление чисел в двоично-десятичном формате, вы можете получить некоторую аппаратную поддержку для сложного умножения / сложения, которое вам нужно сделать. Заставить компилятор выдавать инструкцию BCD - это то, о чем вам нужно прочитать...
Чипы Motorola серии 68K имели это. Не то чтобы я горький или что-то в этом роде.
Аппаратное обеспечение компьютера обеспечивает возможность хранения целых чисел и выполнения основных арифметических операций над ними; обычно это ограничивается целыми числами в диапазоне (например, до 2^{64}-1). Но большие целые числа могут поддерживаться с помощью программ; ниже один из таких методов.
Используя позиционную систему счисления (например, популярную систему счисления с основанием 10), любое произвольно большое целое число может быть представлено как последовательность цифр по основанию. Таким образом, такие целые числа могут быть сохранены как массив 32-битных целых чисел, где каждый элемент массива является цифрой в базе
B=2^{32}.
Мы уже знаем, как представлять целые числа в системе счисления с основанием.
B=10, а также как выполнять основную арифметику (сложение, вычитание, умножение, деление и т. д.) в этой системе. Алгоритмы для выполнения этих операций иногда называют алгоритмами учебника. Мы можем применить (с некоторыми корректировками) эти алгоритмы Учебника к любой базе и, таким образом, можем реализовать те же операции для наших больших целых чисел в базе.
Применять эти алгоритмы для любой базы
B, нам нужно будет лучше понять их и решить такие проблемы, как:
каков диапазон различных промежуточных значений, полученных в ходе этих алгоритмов.
каков максимальный перенос, произведенный итеративным сложением и умножением.
как оценить следующую частную цифру при делении чисел в столбик.
(Конечно, могут быть альтернативные алгоритмы выполнения этих операций).
Некоторые детали алгоритма / реализации можно найти здесь (начальные главы), здесь и здесь .
Можно попробовать реализовать что-то вроде этого:
http://www.docjar.org/html/api/java/math/BigInteger.java.html
Вам понадобится только 4 бита для одной цифры 0 - 9
Таким образом, Int Value будет содержать до 8 цифр каждая. Я решил, что буду использовать массив символов, поэтому я использую удвоенную память, но для меня она используется только 1 раз.
Кроме того, при хранении всех цифр в одном int это чрезмерно усложняет его и, в случае чего, может даже замедлить его.
У меня нет никаких тестов скорости, но, глядя на Java-версию BigInteger, кажется, что она проделывает огромную работу.
Для меня я делаю ниже
//Number = 100,000.00, Number Digits = 32, Decimal Digits = 2.
BigDecimal *decimal = new BigDecimal("100000.00", 32, 2);
decimal += "1000.99";
cout << decimal->GetValue(0x1 | 0x2) << endl; //Format and show decimals.
//Prints: 101,000.99
Мое начало было бы иметь массив целых чисел произвольного размера, используя 31 бит и 32n'd как переполнение.
Начальная операция будет ДОБАВЛЕНА, а затем СДЕЛАТЬ ОТРИЦАТЕЛЬНОЙ, используя 2 дополнения. После этого вычитание выполняется тривиально, и как только вы добавите /sub, все остальное выполнимо.
Есть, вероятно, более сложные подходы. Но это был бы наивный подход со стороны цифровой логики.
Класс C++ BigInt, позволяющий пользователю работать с целыми числами произвольной точности. http://sourceforge.net/projects/cpp-bigint/
Вычтите 48 из целой строки и напечатайте, чтобы получить число большой цифры. затем выполните основную математическую операцию. в противном случае я предоставлю полное решение.