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

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

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

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

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

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

Я могу дать вам псевдокод, похожий на Java, но на данный момент я не могу сделать 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 Multiprecision, или использовать другой язык, изначально поддерживающий произвольно большие целые числа. например Питон.

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

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

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

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

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

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

Или просто используйте библиотеку, в которой больше наворотов, чем вам нужно, и используйте ее для всех своих номеров.

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