Длинная арифметика - готовый класс и примеры использования

[Irval]

Длинная арифметика - не только очень важная часть при создании крупных проектов, но и однин из разделов олимпиадного программирования. Часто в задачах стоит цель далеко не только реализовать, например, сложение чисел N-ной длины, требуется произвести еще и некоторые сложные действия, на которые как раз и делается упор. Тратить свое время на реализацию первичных алгоритмов не всегда хочется, поэтому на большинстве олимпиад, к счастью, разрешено пользоваться некоторыми своими наработками.
Я решил поделиться с вами своим первым классом по работе с длинной арифметикой. Если увижу отдачу - опубликую и последующие версии с нормальными оптимизациями :).

Реализация.
Любые алгоритмы по длинной арифметике основаны на использовании массива, в качестве "хранилища" для переменной. Зачастую используются строки, из-за простоты в работе. Для начала можно использовать обычные "школьные" методы умножения/деления, а потом уже переходить к более сложным и быстрым, например, умножение в хороших классах сделано через алгоритм Карацубы.
Сложение, вычитание и умножение я делал в столбик, деление уже частично основано на бинпоиске по ответу.

Класс для работы.
Файл large.hpp можно скачать с моего репозитория на GutHub'е:

Пожалуйста, авторизуйтесь для просмотра ссылки.

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

Основной функционал.

• Сложение
• Вычитание
• Умножение
• Деление
• Остаток от деления
• Возведение в степень
• Перевод в строку без/со знаком
• Постфиксные инкремент и декремент
• Различные операторы присваивания

Также имеется 3 конструктора класса: из long long, string и стандартный - 0.

Пример использования.
Напишем небольшую программу-калькулятор с использованием моего класса.

#include <iostream>
#include <conio.h>
#include "large.hpp"

int main() {
    setlocale(LC_ALL, "RU");
    string num1, num2;
    cout << "Первое число: ";
    getline(cin, num1);
    cout << "Первое число: ";
    getline(cin, num2);
    cout << "\nСумма: " << (large(num1) + large(num2)).ToString() << endl;
    cout << "Разность: " << (large(num1) - large(num2)).ToString() << endl;
    cout << "Произведение: " << (large(num1) * large(num2)).ToString() << endl;
    cout << "Частное: " << (large(num1) / large(num2)).ToString() << endl;
    cout << "Остаток от деления: " << (large(num1) % large(num2)).ToString() << endl;
    cout << "A в степени B: " << (large(num1).pow(large(num2))).ToString() << endl;
    _getch();
}

Спойлер: Пример вывода

Попрактиковаться можно на простейших задачках с сайта Informatics: №130-142, №2798

 

[Kamazik]

Как всегда отлично, работа на высшем уровне)

 

[dema6r]

Как всегда топ , +rep

 

[Doooooooo]

Топчик)

 

[sn0wyQ]

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

Основные направления для улучшения кода:

• [ЛЕГКО] Хранить число не как std::string num, а как std::vector<int> num. Причем в каждой ячейке не число от 0 до 9, а от 0 до 10^9 - 1.
  Т.е например 1 = {1}, а 3'000'200'001 = {200'001, 3} // При реализации будет удобнее чтобы num[0] отвечало за меньший разряд, чтобы не было
  
  reverse(num1.begin(), num1.end());
  reverse(num2.begin(), num2.end());
  Зачем? Так у нас операции будут выполняться в [примерно] 9 раз быстрее (не учитывая маленькие числа, но длинки обычно не для них пишутся)
• [ОЧЕНЬ СЛОЖНО] Умножение реализовать через быстрое преобразование Фурье или что-то подобное
• large pow(large val) {
          large ans = 1;
          bool isMinus = sign == Sign::Minus && large(string(val)) % large(2) != large(0);
          if (val.sign == Sign::Plus) {
              // [СРЕДНЕ] Реализовать через бинарное возведение в степень
              for (large i; i < val; i = i + large(1))
                  ans = ans * large(this->num);
          }
          else {
              // [ЛЕГКО] Т.к. длинка целочисленная здесь всегда 0 или 1, это можно просто закостылить по сути
              for (large i; i < large(string(val)); i++)
                  ans = ans / large(this->num);
          }
          // ...
      }
• [ЛЕГКО] Добавить префиксные ++ и --
• [ЛЕГКО]
  
  bool operator== (large val) {
      // Зачем num1 = num?
      string num1 = num, num2 = string(val);
      return num1 == num2;
  }
• [ЧУТЬ СЛОЖНЕЕ, ЧЕМ ЛЕГКО] Перегрузить операторы << и >>
• [ЛЕГКО] Операторы сравнения обычно делают так:
  • Реализуем operator<
  • (a > b) = (b < a)
  • (a >= b) = !(a < b)
  • (a <= b) = !(b < a)
    Это позволяет избежать кучи дублированного кода

P.S. !!! Ни в коем случае не считать за хейт. Этот топик в миллион раз лучше всех от DarwinRoot

 

[Irval]

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

Основные направления для улучшения кода:

• [ЛЕГКО] Хранить число не как std::string num, а как std::vector<int> num. Причем в каждой ячейке не число от 0 до 9, а от 0 до 10^9 - 1.
  Т.е например 1 = {1}, а 3'000'200'001 = {200'001, 3} // При реализации будет удобнее чтобы num[0] отвечало за меньший разряд, чтобы не было
  
  reverse(num1.begin(), num1.end());
  reverse(num2.begin(), num2.end());
  Зачем? Так у нас операции будут выполняться в [примерно] 9 раз быстрее (не учитывая маленькие числа, но длинки обычно не для них пишутся)
• [ОЧЕНЬ СЛОЖНО] Умножение реализовать через быстрое преобразование Фурье или что-то подобное
• large pow(large val) {
  large ans = 1;
  bool isMinus = sign == Sign::Minus && large(string(val)) % large(2) != large(0);
  if (val.sign == Sign::Plus) {
  // [СРЕДНЕ] Реализовать через бинарное возведение в степень
  for (large i; i < val; i = i + large(1))
  ans = ans * large(this->num);
  }
  else {
  // [ЛЕГКО] Т.к. длинка целочисленная здесь всегда 0 или 1, это можно просто закостылить по сути
  for (large i; i < large(string(val)); i++)
  ans = ans / large(this->num);
  }
  // ...
  }
• [ЛЕГКО] Добавить префиксные ++ и --
• [ЛЕГКО]
  
  bool operator== (large val) {
  // Зачем num1 = num?
  string num1 = num, num2 = string(val);
  return num1 == num2;
  }
• [ЧУТЬ СЛОЖНЕЕ, ЧЕМ ЛЕГКО] Перегрузить операторы << и >>
• [ЛЕГКО] Операторы сравнения обычно делают так:
  • Реализуем operator<
  • (a > b) = (b < a)
  • (a >= b) = !(a < b)
  • (a <= b) = !(b < a)
    Это позволяет избежать кучи дублированного кода

P.S. !!! Ни в коем случае не считать за хейт. Этот топик в миллион раз лучше всех от DarwinRoot

Большое спасибо за дельную критику. В моем основном классе уже реализована большая часть твоих замечаний. Этому коду уже около 3х лет :)

 

[KlareoN]

Как много знаков, молодец! Продолжай в том же духе!

 

[So30kap]

Длинная арифметика - не только очень важная часть при создании крупных проектов, но и однин из разделов олимпиадного программирования. Часто в задачах стоит цель далеко не только реализовать, например, сложение чисел N-ной длины, требуется произвести еще и некоторые сложные действия, на которые как раз и делается упор. Тратить свое время на реализацию первичных алгоритмов не всегда хочется, поэтому на большинстве олимпиад, к счастью, разрешено пользоваться некоторыми своими наработками.
Я решил поделиться с вами своим первым классом по работе с длинной арифметикой. Если увижу отдачу - опубликую и последующие версии с нормальными оптимизациями :).

Реализация.
Любые алгоритмы по длинной арифметике основаны на использовании массива, в качестве "хранилища" для переменной. Зачастую используются строки, из-за простоты в работе. Для начала можно использовать обычные "школьные" методы умножения/деления, а потом уже переходить к более сложным и быстрым, например, умножение в хороших классах сделано через алгоритм Карацубы.
Сложение, вычитание и умножение я делал в столбик, деление уже частично основано на бинпоиске по ответу.

Класс для работы.
Файл large.hpp можно скачать с моего репозитория на GutHub'е:

Пожалуйста, авторизуйтесь для просмотра ссылки.

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

Основной функционал.

• Сложение
• Вычитание
• Умножение
• Деление
• Остаток от деления
• Возведение в степень
• Перевод в строку без/со знаком
• Постфиксные инкремент и декремент
• Различные операторы присваивания

Также имеется 3 конструктора класса: из long long, string и стандартный - 0.

Пример использования.
Напишем небольшую программу-калькулятор с использованием моего класса.

#include <iostream>
#include <conio.h>
#include "large.hpp"

int main() {
    setlocale(LC_ALL, "RU");
    string num1, num2;
    cout << "Первое число: ";
    getline(cin, num1);
    cout << "Первое число: ";
    getline(cin, num2);
    cout << "\nСумма: " << (large(num1) + large(num2)).ToString() << endl;
    cout << "Разность: " << (large(num1) - large(num2)).ToString() << endl;
    cout << "Произведение: " << (large(num1) * large(num2)).ToString() << endl;
    cout << "Частное: " << (large(num1) / large(num2)).ToString() << endl;
    cout << "Остаток от деления: " << (large(num1) % large(num2)).ToString() << endl;
    cout << "A в степени B: " << (large(num1).pow(large(num2))).ToString() << endl;
    _getch();
}

Спойлер: Пример вывода

Посмотреть вложение 145173

Попрактиковаться можно на простейших задачках с сайта Informatics: №130-142, №2798

данная работа заслуживает уважения!