Как обрабатывать сколь угодно большие целые числа

Question

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

Answer 1

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

Answer 2

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

Answer 3

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

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

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

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

Answer 4

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

Answer 5

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

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

Answer 7

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

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

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