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

Question

Я работаю над языком программирования, и сегодня я получил точку, где я мог бы скомпилировать факториальную функцию (рекурсивную), однако из-за максимального размера целого числа наибольшее, что я могу получить, это факториал (12). Каковы некоторые методы для обработки целых чисел произвольного максимального размера. Язык в настоящее время работает путем перевода кода на C++.

Answer 1

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

Answer 2

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

Answer 3

Если вы встраиваете это в язык (я полагаю, для целей обучения), я думаю, что, возможно, я бы написал небольшую библиотеку 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;
            }
        }
    }
}

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

Answer 4

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

Answer 5

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

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

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

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

Answer 6

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

Answer 7

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

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

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