Как реализовать большой интервал в C++

Мой запуск должен был бы иметь произвольный размерный массив целых чисел, с помощью 31 бита и 32n'd как переполнение.

начинающий op был бы ADD, и затем, СДЕЛАТЬ - ОТРИЦАТЕЛЬНЫЙ, с помощью 2 дополнение. После этого вычитание течет тривиально, и как только у Вас есть add/sub, все остальное выполнимо.

существуют, вероятно, более сложные подходы. Но это было бы наивным подходом от цифровой логики.

Если Ваша целевая архитектура поддерживает BCD (двоично-десятичное число) представление чисел, можно получить некоторую поддержку оборудования для рукописного умножения/дополнения, которое необходимо сделать. Получение компилятора испустить инструкцию по BCD является чем-то, на чем необходимо будет читать...

микросхемы серии Motorola 68K имели это. Не то, чтобы я горек или что-либо.

Как сказанные другие, сделайте это к старомодному обычному письму путь, но держитесь подальше от выполнения этого всего в основе 10. Я предложил бы делать все это в основе 65536 и сохранить вещи в массиве longs.

Используйте алгоритмы, которые Вы изучили в 1-м через 4-й класс.
Запускают с тех столбец, тогда десятки, и т.д.

Не забывайте, что Вы не должны ограничивать себя 0-9 как цифры, т.е. байты использования как цифры (0-255), и можно все еще сделать длинную ручную арифметику то же, как Вы были бы для десятичных цифр. Вы могли даже использовать массив долго.

Как только у Вас есть цифры числа в массиве, можно сделать дополнение и умножение точно, как Вы сделали бы их обычное письмо.

дополнение должно было бы, вероятно, быть сделано в стандартном линейном алгоритме времени
, но для умножения Вы могли попробовать http://en.wikipedia.org/wiki/Karatsuba_algorithm

Существует полный раздел по этому: [Искусство Программирования, vol.2: получисловые Алгоритмы, разделите 4.3 Арифметики Многократно увеличенной точности, стр, 265-318 (редактор 3)]. Можно найти другой интересный материал в Главе 4, Арифметике.

, Если Вы действительно не хотите смотреть на другую реализацию, Вы рассмотрели то, что это - Вы, отсутствуют для изучения? Существуют неисчислимые ошибки, которые будут сделаны, и раскрывающий тех поучительно и также опасен. Существуют также проблемы в идентификации важных вычислительных экономических систем и наличии соответствующих структур устройства хранения данных для предотвращения серьезных проблем производительности.

Контрольный вопрос А для Вас: То, как Вы намереваетесь протестировать свою реализацию и как Вы предлагаете продемонстрировать, что это - арифметика, корректно?

Вы могли бы хотеть, чтобы другая реализация протестировала против (не смотря на то, как она делает это), но она возьмет больше, чем это, чтобы быть в состоянии сделать вывод, не ожидая excrutiating уровня тестирования. Не забывайте рассматривать виды отказа (из проблем памяти, из стека, работая слишком долго, и т.д.).

Развлекайтесь!

Забавная проблема.:)

я предполагаю, что Вы хотите целые числа произвольной длины. Я предлагаю следующий подход:

Считают двоичную природу типа данных "интервалом". Думайте об использовании простых бинарных операций эмулировать то, что делают схемы в Вашем ЦП, когда они добавляют вещи. В случае, если Вы интересно более всесторонние, рассматриваете чтение эта статья Википедии о полусумматорах и полных сумматорах . Вы будете делать что-то подобное этому, но можно спуститься как низкий уровень как тот - но быть ленивым, я думал, что буду просто предшествовать и находить ровное простое решение.

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

template< class BaseType >
class BigInt
{
typedef typename BaseType BT;
protected: std::vector< BaseType > value_;
};

Вы могли бы хотеть рассмотреть, хотите ли Вы сделать вектор фиксированного размера и если предварительно выделить его. Причина, являющаяся этим для разнообразных операций, необходимо будет пройти каждый элемент вектора - O (n). Вы могли бы хотеть знать бесцеремонно, как сложный операция будет, и фиксированный n делает просто это.

, Но теперь к некоторым алгоритмам при работе на числах. Вы могли сделать это на логическом уровне, но мы будем использовать ту волшебную мощность ЦП для вычисления результатов. Но то, из чего мы вступим во владение из логической иллюстрации полу - и FullAdders, является способом, которым это имеет дело с переносами. Как пример, рассмотрите, как Вы реализовали бы + = оператор . Для каждого числа в BigInt<>:: оцените _, Вы добавили бы тех и видели бы, производит ли результат некоторую форму переноса. Мы не будем делать его поразрядно, но полагаться на природу нашего BaseType (быть им долго или интервал или короткий или безотносительно): это переполняется.

, Конечно, если Вы добавляете два числа, результат должен быть больше, чем большее из тех чисел, правильно? Если это не, то переполненный результат.

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. ;-)

другая арифметическая операция идут аналогичные. Heck, Вы могли даже использовать станд. stl-функторов:: плюс и станд.:: минус, станд.:: времена и станд.:: делится..., но возражайте против переноса.:) Можно также реализовать умножение и разделение при помощи Вашего плюс и минус операторы, но это очень медленно, потому что это повторно вычислило бы результаты, к которым Вы уже вычислили в предшествующих вызовах плюс и минус в каждом повторении. Существует много хороших алгоритмов там для этой простой задачи, использование Википедия или сеть.

И конечно, необходимо реализовать стандартные операторы такой как operator<< (просто смещают каждое значение в value_ налево для n битов, запускающихся в value_.size()-1..., о, и помнят перенос:), operator< - можно даже оптимизировать немного здесь, проверив грубое количество цифр с size() сначала. И так далее. Тогда сделайте свой класс полезным befriendig станд.:: ostream operator<<.

Hope этот подход полезен!

Я не убежден с помощью строки, правильный способ пойти - хотя я никогда не писал код сам, я думаю, что использование массива основного числового типа могло бы быть лучшим решением. Идея состоит в том, что Вы просто расширили бы то, что Вы уже получили тот же способ, которым ЦП расширяет единственный бит в целое число.

, Например, если у Вас есть структура

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;
}

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

вычтите 48 из вашей строки целого числа и выведите его, чтобы получить большую цифру. затем выполните базовую математическую операцию. {{1} } в противном случае я предоставлю полное решение.