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

Ответ 1

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

Ответ 2

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

Ответ 3

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

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

(Divide - жесткий, но я уверен, вы можете найти там какой-то код.)

Я могу дать вам некоторый Java-подобный psuedocode, но на данный момент он не может делать С++ с нуля:

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

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

Ответ 4

В С++ нет простого способа сделать это. Вам нужно будет использовать внешнюю библиотеку, такую ​​как GNU Multiprecision, или использовать другой язык, который изначально поддерживает сколь угодно большие целые числа, такие как Python.

Ответ 5

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

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

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

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

Ответ 6

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

Ответ 7

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

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

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