Как реализовать большой int в C ++
https://stackoverflow.com/questions/269268
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianВопрос
Я хотел бы реализовать большой класс int в C ++ как упражнение по программированию & # 8212, класс, который может обрабатывать числа, большие, чем long int. Я знаю, что уже есть несколько реализаций с открытым исходным кодом, но я бы хотел написать свою собственную. Я пытаюсь понять, что такое правильный подход.
Я понимаю, что общая стратегия состоит в том, чтобы получить число в виде строки, а затем разбить его на более мелкие числа (например, на одну цифру) и поместить их в массив. На этом этапе должно быть относительно просто реализовать различные операторы сравнения. Моя главная задача - как бы я реализовал такие вещи, как сложение и умножение.
Я ищу общий подход и советы, а не рабочий код.
Решение
Что нужно учитывать для большого класса int:
<Ол>Математические операторы: +, -, /, *,% Не забывайте, что ваш класс может быть по обе стороны от оператор, что операторы могут быть прикован, что один из операндов может быть int, float, double и т. д.
Операторы ввода / вывода: > > ;, < < Это где вы выясните, как правильно создать свой класс из пользовательского ввода и как отформатировать его для вывода.
Конверсии / Приведения: выяснить какие типы / классы ваш большой инт класс должен быть конвертируемым, и как правильно обращаться с преобразование. Быстрый список будет включают двойные и плавающие, и могут включить int (с правильными границами проверка) и сложная (при условии может обрабатывать диапазон).
Другие советы
Забавный вызов. :)
Я предполагаю, что вы хотите целые числа произвольной длины. Я предлагаю следующий подход:
Рассмотрим двоичную природу типа данных " int " ;. Подумайте об использовании простых двоичных операций, чтобы эмулировать действия схем в вашем процессоре, когда они что-то добавляют. Если вы заинтересованы в более глубоком рассмотрении, прочитайте эту статью в Википедии о полусумбровщиках и полных сумматорах . Вы будете делать что-то похожее на это, но вы можете понизиться до такого низкого уровня - но, будучи ленивым, я подумал, что просто воздержусь и найду еще более простое решение.
Но прежде чем углубляться в алгоритмические подробности о сложении, вычитании, умножении, давайте найдем некоторую структуру данных. Конечно, простой способ хранить вещи в std :: vector.
Возможно, вы захотите подумать, хотите ли вы сделать вектор фиксированного размера и предварительно выделить его. Причина в том, что для разнообразных операций вам придется пройти через каждый элемент вектора - O (n). Возможно, вы захотите узнать, насколько сложной будет операция, и фиксированное n делает именно это. Но теперь к некоторым алгоритмам по работе с числами. Вы можете сделать это на логическом уровне, но мы будем использовать эту магическую мощность процессора для вычисления результатов. Но то, что мы извлечем из логической иллюстрации Half- и FullAdders, - это то, как они работают с переносами. В качестве примера рассмотрим, как можно реализовать оператор + = . Для каждого числа в BigInt & Lt; & Gt; :: value_ вы добавите их и посмотрите, не приведет ли результат к какой-либо форме переноса. Мы не будем делать это побитно, но будем полагаться на природу нашего BaseType (будь то long или int, short или что-то еще): он переполнен.
Конечно, если вы добавите два числа, результат должен быть больше, чем большее из этих чисел, верно? Если это не так, то результат переполнен. Другая арифметическая операция выполняется аналогично. Черт возьми, вы можете даже использовать stl-функторы std :: plus и std :: minus, std :: times и std :: divides, ..., но помните о переносе. :) Вы также можете реализовать умножение и деление, используя операторы «плюс» и «минус», но это очень медленно, потому что это пересчитало бы результаты, которые вы уже вычислили в предыдущих вызовах плюс и минус в каждой итерации. Существует множество хороших алгоритмов для этой простой задачи: использовать википедия или в Интернете. И, конечно, вы должны реализовать стандартные операторы, такие как Надеюсь, что этот подход полезен! template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};
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. ;-)
operator<< (просто сдвиньте каждое значение в value_ влево на n бит, начиная с value_.size()-1 ... oh и запомните перенос :), <= > - здесь вы можете даже немного оптимизировать, проверив приблизительное количество цифр с помощью operator<. И так далее. Тогда сделайте ваш класс полезным, используя befriendig std :: ostream size().
Об этом есть полный раздел: [Искусство компьютерного программирования, том 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;
Затем вы можете вручную выполнить собственные операции с каждым из " digits " (высокий и низкий, в данном случае), помня об условиях переполнения:
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;
}
Это немного упрощенный пример, но должно быть довольно очевидно, как расширить структуру, в которой было переменное число любого базового числового класса, который вы используете.
Как говорили другие, делайте это старомодным способом, но держитесь подальше от всего этого в базе 10. Я бы предложил сделать все это в базе 65536 и хранить вещи в массиве длинных позиций.
Используйте алгоритмы, которые вы изучили с 1 по 4 класс.
Начните со столбца единиц, затем десятков и т. Д.
Если ваша целевая архитектура поддерживает представление чисел в двоично-десятичном формате, вы можете получить некоторую аппаратную поддержку для умножения / сложения, которое вам необходимо сделать. Заставить компилятор выдавать инструкцию BCD - это то, о чем вам нужно прочитать ...
Чипы Motorola серии 68K имели это. Не то чтобы я горький или что-то в этом роде.
Мое начало было бы иметь массив целых чисел произвольного размера, используя 31 бит и 32n в качестве переполнения.
Оператор для начала будет ADD, а затем MAKE-NEGATIVE, используя дополнение 2. После этого вычитание проходит тривиально, и как только вы добавите / sub, все остальное выполнимо.
Возможно, есть более сложные подходы. Но это был бы наивный подход со стороны цифровой логики.
Можно попробовать реализовать что-то вроде этого:
http://www.docjar.org/html/ апи / Java / математика / BigInteger.java.html
Вам понадобится только 4 бита для одной цифры 0 - 9
Таким образом, значение Int может содержать до 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
вычтите 48 из целой строки и напечатайте, чтобы получить число большой цифры. затем выполните основную математическую операцию. в противном случае я предоставлю полное решение.
