Как обработать произвольно большие целые числа

Если Вам нужно больше, чем 32 бита, Вы могли бы рассмотреть использование 64-разрядных целых чисел (долго долго), или использовать или записать математической библиотеке произвольной точности, например, GNU MP.

Если вы хотите свернуть свою собственную библиотеку произвольной точности, см. Получисловые алгоритмы Кнута, том 2 его большого опуса.

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

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

(Деление является твердым, но я держал пари, что можно найти некоторый код там где-нибудь.)

Я могу дать Вам некоторый подобный Java psuedocode, но не могу действительно сделать C++ с нуля в этой точке:

class BigAssNumber {
    private byte[] value;

    // This constructor can handle numbers where overflows have occurred.
    public BigAssNumber(byte[] value) {
        this.value=normalize(value);
    }

    // Adds two numbers and returns the sum.  Originals not changed.
    public BigAssNumber add(BigAssNumber other) {
        // This needs to be a byte by byte copy in newly allocated space, not pointer copy!
        byte[] dest = value.length > other.length ? value : other.value;         

        // Just add each pair of numbers, like in a pencil and paper addition problem.
        for(int i=0; i<min(value.length, other.value.length); i++)
            dest[i]=value[i]+other.value[i];

        // constructor will fix overflows.
        return new BigAssNumber(dest);
    }

    // Fix things that might have overflowed  0,17,22 will turn into 1,9,2        
    private byte[] normalize(byte [] value) {
        if (most significant digit of value is not zero)
            extend the byte array by a few zero bytes in the front (MSB) position.

        // Simple cheap adjust.  Could lose inner loop easily if It mattered.
        for(int i=0;i<value.length;i++)
            while(value[i] > 9) {
                value[i] -=10;
                value[i+1] +=1;
            }
        }
    }
}

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

Нет никакого простого способа сделать это в C++. Необходимо будет пользоваться внешней библиотекой, такой как Мультиточность GNU или использовать другой язык, который исходно поддерживает произвольно большие целые числа, такие как Python.

Другие плакаты дали ссылки на библиотеки, которые сделают это для Вас, но кажется, что Вы пытаетесь встроить это в свой язык. Моя первая мысль: действительно ли Вы уверены, что необходимо сделать это? Большинство языков пользовалось бы дополнительной библиотекой, как другие предположили.

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

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

Кроме того, рассмотрите использование специализированного типа данных для этих больших целых чисел. Тем путем "нормальные" целые числа могут использовать стандартную арифметику на 32 бита.

Мой предпочтенный подход должен был бы использовать мой текущий международный тип для 32-разрядного ints (или возможно изменить его на внутренне, чтобы быть длинным длинным или некоторыми такой, пока он может продолжить использовать те же алгоритмы), затем когда он переполняется, имейте его, изменяются на хранение как сверхбольшое число, ли из моего собственного создания или пользования внешней библиотекой. Однако я чувствую, что должен был бы проверять на переполнение на каждой арифметической операции, примерно 2x наверху на арифметической операции в секунду. Как я мог решить это?

Если бы я реализовал свой собственный язык и хотел бы поддерживать числа произвольной длины, я буду использовать целевой язык с переносом / заимствовать понятие. Но поскольку нет HLL, который бы реализовывал это без серьезных последствий для производительности (например, исключений), я, конечно, пойду реализовывать его в сборке. Вероятно, потребуется одна инструкция (как в JC в x86) для проверки на переполнение и обработки (как в ADC в x86), что является приемлемым компромиссом для языка, реализующего произвольную точность. Тогда я буду использовать несколько функций, написанных на ассемблере, вместо обычных операторов, если вы можете использовать перегрузку для более элегантного вывода, даже лучше. Но я не ожидаю, что сгенерированный C ++ будет поддерживаемым (или предназначенным для поддержания) в качестве целевого языка.

Или,