Реализация целочисленной длинной арифметики

Технология и методы программирования Спортивное программирование Реализация целочисленной длинной арифметики

  • В этой теме 3 ответа, 1 участник, последнее обновление 7 месяцев назад сделано .
Просмотр 3 веток ответов
  • Автор
    Сообщения
    • #4556
      @admin
      StudLance.ru

      Во многих олимпиадных задачах необходимо реализовать так называемую длинную арифметику. Дело в том, что встроенные типы данных в большинстве языков имеют ограничение на диапазон допустимых значений. Например, наибольшее целое число в С++ можно задать типом unsigned long long, который хранит двоичных 64 разряда, что соответствует примерно 18 биллионам. В олимпиадных же задачах нередко встречаются входные данные в большем диапазоне, например до 10^100.

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

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

      Итак, опишем класс содержащий флажок (bool) для знака, массив цифр и ряд самых необходимых методов (конструкторы, операторы сравнения и выполнения арифметических операций, функции приведения к строковому типу):

      class BigInt{
      public:
        BigInt(); 
        BigInt(std::string number); 
        BigInt(long long number); 
        BigInt(const BigInt& rhs); 
      
        BigInt& operator=(const BigInt& rhs);
      
        bool operator>(const BigInt& rhs) const;
        bool operator<(const BigInt& rhs) const;
        bool operator==(const BigInt& rhs) const;
      
        const BigInt operator+(const BigInt& rhs) const;
        const BigInt operator-(const BigInt& rhs) const;
        const BigInt operator*(const BigInt& rhs) const;
        const BigInt operator/(const BigInt& rhs) const;
      
        std::string to_string() const;
      
        BigInt abs() const; 
      private:
        void ignoreLeadingZeros(); 
        BigInt digitMultiply(unsigned int digit) const; 
      
        int digit(int index) const;
      
        std::vector<unsigned int> digits; 
        bool sign; 
      };

      Конструкторы реализовать очень просто. Конструктор по умолчанию инициализирует массив цифр нулем и устанавливает положительный знак. Конструктор из типа string анализирует первый символ на предмет знака, остальные цифры просто помещает в массив, вызовом функции ignoreLeadingZeros удаляет ведущие (незначащие) нули. Конструктор из типа long long преобразует свой аргумент к типу string и передает управление соответствующему конструктору:

      BigInt::BigInt(){
        digits.push_back(0);
        sign = true;
      }
      
      BigInt::BigInt(std::string number){
        int didits_pos = isdigit(number.at(0)) ? 0 : 1;
        sign = number.at(0) == '-' ? false:true;
        
        for(unsigned int i = didits_pos; i < number.length(); i++)
          digits.push_back(number.at(i) - '0');
        
        ignoreLeadingZeros();
      }
      
      BigInt::BigInt(long long number) 
        : BigInt(std::to_string(number)) {
      }
      
      BigInt::BigInt(const BigInt& rhs){
        sign = rhs.sign;
        digits = rhs.digits;
      }
      
      void BigInt::ignoreLeadingZeros(){
        while(digits.size() > 1 && digits.at(0) == 0)
          digits.erase(digits.begin(), digits.begin() + 1);
      }

      Функция приведения к строковому типу нам пригодится для вывода числа (например в файл) — она выполняет по сути операцию, обратную конструктору из типа string. Оператор присваивания похож на конструктор копирования, но выполняет проверку на самоприсваивание:

      std::string BigInt::to_string() const{
        std::string str;
        if(!sign)
          str+="-";
        for(unsigned int i = 0; i < digits.size(); i++)
          str += std::to_string(digits.at(i));
        return str;
      }
      
      BigInt& BigInt::operator=(const BigInt& rhs){
        if(this == &rhs)
          return *this;
        sign = rhs.sign;
        digits = rhs.digits;
        return *this;
      }

      Очень простая логика у операторов сравнения. Сначала проверяется знак, потом количество чисел в числе и только если два предыдущих параметра у чисел совпадают — выполняется сравнение разрядов, начиная со старших. Сравнение идет до первого различающегося символа. Из-за того, что при сравнении используется проверка длины чисел — в передаваемых на вход аргументах не должно быть ведущих нулей:

      bool BigInt::operator>(const BigInt& rhs) const{
        if(sign == true && rhs.sign == false) 
          return true;
        if(sign == false && rhs.sign == true) 
          return false;
      
        if(digits.size() > rhs.digits.size())
          return sign;
        if(digits.size() < rhs.digits.size())
          return !sign;
        
        for(size_t i = 0; i < digits.size(); i++) {
          if(digits.at(i) > rhs.digits.at(i))
            return sign;
          if(digits.at(i) < rhs.digits.at(i))
            return !sign;
        }
      
        return false;
      }
      
      bool BigInt::operator<(const BigInt& rhs) const{
        return false == (*this == rhs) && false == (*this > rhs);
      }
      
      bool BigInt::operator==(const BigInt& rhs) const{
        return (sign == rhs.sign && digits == rhs.digits);
      }

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

      BigInt BigInt::abs() const{
        BigInt a(*this); 
        a.sign = true;
        return a;
      }
      
      int BigInt::digit(int index) const {
        return index >= 0 ? digits[index] : 0;
      }
      

      С имеющимся набором функций мы уже можем считывать, сравнивать и записывать куда-нибудь длинные числа. Но например в олимпиадной задаче «Снова A+B» требуется их складывать.

      Сложение выполняется только в том случае, если числа имеют одинаковый знак. Если же знак разный — выполняется вычитание, при этом из большего по модулю числа вычитается меньшее, знак результата совпадает со знаком большего числа. Складываются разряды чисел справа налево (начиная с младших). Если в результате получается число, большее 10 — то из него вычитается 10 и единица переносится в соседний разряд справа. В приведенном ниже алгоритме цифры к результату добавляются в конец (методом push_back), поэтому когда счет окончен результат требуется перевернуть (алгоритм reverse):

      const BigInt BigInt::operator+(const BigInt& rhs) const{

        BigInt sum;
        if(digits.at(0) == 0 && rhs.digits.at(0) == 0) 
          return sum;
        if(sign == rhs.sign){
          sum.digits.clear();
          sum.sign = sign;
          unsigned int carry = 0;
          int index1 = digits.size() - 1;
          int index2 = rhs.digits.size() - 1;
          while(index1 >=0 || index2 >= 0){
            auto digitsum = this->digit(index1) + rhs.digit(index2) + carry;
            
            carry = digitsum / 10;
            digitsum %= 10;
            
            sum.digits.push_back(digitsum);
            index1--;
            index2--;
          }
          if(carry != 0)
            sum.digits.push_back(carry);
          std::reverse(sum.digits.begin(), sum.digits.end());
        } else{
          if(this->abs() > rhs.abs()){
            sum = this->abs() - rhs.abs();
            sum.sign = sign;
          } else{
            sum = rhs.abs() - this->abs();
            sum.sign = rhs.sign;
          }
        }
        return sum;
      }

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

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

      BigInt BigInt::digitMultiply(unsigned int digit) const{
        BigInt result;
        result.digits.clear();
        result.sign = true;
        unsigned int carry = 0;
        for(int i = digits.size()-1; i>=0; i--){
          unsigned int digitproduct = digits.at(i) * digit + carry;
          if(digitproduct > 9){
            carry = digitproduct / 10;
            digitproduct %= 10;
          }
          else
            carry = 0;
      
          result.digits.push_back(digitproduct);
        }
        if(carry != 0)
          result.digits.push_back(carry);
      
        std::reverse(result.digits.begin(), result.digits.end());
        return result;
      }
      
      const BigInt BigInt::operator*(const BigInt& rhs) const{
        BigInt product;
        BigInt psum;
        unsigned int zeros_to_insert = 0;
        for(int i = rhs.digits.size() - 1; i>=0; i--){
          unsigned int digit = rhs.digits.at(i);
          product = this->digitMultiply(digit);
          product.digits.insert(product.digits.end(), zeros_to_insert++, 0);
          psum = psum + product;
        }
        if(sign != rhs.sign)
          psum.sign = false;
        return psum;
      }

      С помощью описанных функций можно решить например следующие олимпиадные задачи: «A-B» и «A*B«. Однако, в задаче «A div B» требуется выполнять целочисленное деление.

      При делении в столбик мы из делимого добавляем по очереди (начиная со старших разрядов) цифры к некоторому буферу до тех пор, пока число в буфере не окажется больше делителя (или не кончатся разряды делимого — при этом результат уже вычислен). При каждом таком дописывании цифры к буферу — дописывается ноль к результату. Когда буфер стал достаточно большим, из него вычитается делитель, до тех пор пока буфер не станет меньше делителя. Такое вычитание в худшем случае будет выполнено 9 раз (в десятичной системе счисления). К результату дописывается количество выполненных вычитаний. Знак числа определяется также как в алгоритме умножения. На случай если кто-то забыл как это выглядит — картинка:

      const BigInt BigInt::operator/(const BigInt& rhs) const {
        BigInt buffer;
        BigInt result;
        BigInt rhsAbs = rhs.abs();
        result.digits.clear();
        buffer.digits.clear();
      
        if (rhs == BigInt(0))
          throw std::overflow_error("Divide by zero exception");
      
        for (size_t i = 0; i < digits.size(); ++i) {
          buffer.digits.push_back(digits[i]);
          buffer.ignoreLeadingZeros();
          if (buffer < rhsAbs) {
            result.digits.push_back(0);
            continue;
          }
          int count;
          for (count = 0; buffer > rhsAbs || buffer == rhsAbs; ++count) {
            buffer = buffer - rhsAbs;
          }
          result.digits.push_back(count);
        }
        result.ignoreLeadingZeros();
      
        result.sign = true;
        if(sign != rhs.sign && result.digits[0] != 0)
          result.sign = false;
      
        return result;
      }

      Указанные выше 4 олимпиадные задачи решаются примерно следующим образом:

      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
        
        BigInt a, b;
        
        ifst >> a >> b;
        ofst << (a/b).to_string();
      }

      Остается только заменить оператор в соответствии с условием.

      StudLance.ru

    • #4598
      @admin

      Также с помощью класса BigInt легко решается задача Факториал (Время: 1 сек. Память: 16 Мб Сложность: 42%)), где требуется вычислить

      N! = 1 * 2 * 3 * … * (N-1) * N, причем 0! = 1.
      Для любых N от 1 до 1000.

      Исходный код решения в комментариях думаю не нуждается:

      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
        int n;
         
        ifst >> n;
        
        BigInt fact(1);
        for (int i = 1; i <= n; ++i)
          fact = fact*i;
        
        ofst << fact.to_string();
         
        ofst.close();
        return 0;
      }

    • #6082
      @admin

      Задача «сумма факториалов» (Время: 1 сек. Память: 16 Мб Сложность: 45%)

      С приведенным выше классом может решаться так:

      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        int n;
        ifst >> n;
      
        BigInt sum(0), fact(1);
        for (int i = 1; i <= n; ++i) {
          fact = fact*i;
          sum = sum + fact;
        }
      
        ofst << sum.to_string();
      }

    • #6083
      @admin

      В задаче «деление с остатком» необходимо получить остаток от деления. Можно напистаь для этой цели спечиальную функцию (можно сделать эффективно), однако, подойдет и такое решение:

      int main() {
        ifstream ifst("input.txt");
        ofstream ofst("output.txt");
      
        string str_a, str_b;
      
        ifst >> str_a >> str_b;
        BigInt a(str_a), b(str_b);
      
        ofst << (a-(a/b)*b).to_string();
      }

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

Просмотр 3 веток ответов
  • Для ответа в этой теме необходимо авторизоваться.
×