Доброго времени суток и светлого неба над головой, дорогие друзья! Ни для кого из вас не секрет, что ограничение максимального и минимального значения целого числа, хоть и разнится на разных архитектурах, но существует. Например, для целого числа типа int диапазон его значений равен от –2147483647 – 1 до 2147483647. Казалось бы, 2 миллиарда в каждую сторону это целая гора, но как только вы займетесь настоящей криптографией, либо машинным обучением, теорией вероятностей или еще более крутой математикой, вы поймете, что это чертовски мало. Именно в таком случае на помощь приходят, так называемые, большие числа.
Идея большого числа в том, чтобы вылезти за рамки ограничений стандартных типов данных, оперировать бесконечно большими числами, размер которых будет ограничен только вычислительной мощностью «машины». Как этого достичь? Самый логичный способ заключается в том, чтобы записывать число в строку и конвертировать специальным образом в согласованный массив чисел стандартного типа.
Например, как можно хранить число 123456789123456789, в int оно не поместится. тогда мы поместим его в массив int`ов, mas[0] = 123456, mas[1] = 789123, mas[2] = 456789, напишем специальные алгоритмы, которые будут корректно складывать, вычитать, умножать и делить такие числа.
Как раз о таких алгоритмах инициализации, сложения и вычитания больших чисел я сейчас расскажу, поехали!
Другие статьи по теме
- Реализация больших чисел на C/C++ со сложением и вычитанием;
- Операторы сравнения больших чисел — реализация на C/C++;
- Умножение больших чисел — реализация на C/C++.
Как реализовать большие числа на C/C++
Сейчас я расскажу о том, как будет работать написанный нами специальный класс BigNumber с реализованной инициализацией числа из строки, сложением, вычитанием и выводом в поток. А после приведу полный листинг исходного кода с этим классом, снабженный комментариями. Вы можете читать описания, поглядывая на код. Я специально не стал дублировать функции, чтобы не нагромождать и без того длинный текст статьи.
Инициализация большого числа
Конструктор класса BigNumber(string str), принимающий на вход строку, работает следующим образом. Начиная с конца строки отсекаются подстроки длины BASE, конвертируются в числа и закидываются в вектор chunks. В зависимости от наличия минуса в строке инициализируется еще одно приватное поле класса — sign. BASE это статическое константное поле, одинаковое для всех объектов класса, чтобы не было конфликтов в нормализации.
Сложение больших чисел
Для сложения мы перегрузим оператор +, он в свою очередь будет вызывать метод _plus(), который сложит два больших числа «почанково». Кроме того, перед самим сложением необходимо сделать одинаковыми размеры векторов chunks обоих чисел. А после сложения нормализовать результат функцией _normalizationChunks(). Нормализовать — значит сделать так, чтобы во всех чанках лежали BASE-разрядные числа (если BASE = 2, то только двузначные числа).
Вычитание больших чисел
Вычитание работает аналогично сложению, перегружается оператор —, используется метод _minus().
Вывод большого числа в поток
Вывод происходит благодаря перегрузке оператора <<, но перед самим выводом, число нужно нормализовать функцией _normalizationSigns(). Она почистит все нулевые чанки, отрицательные числа в чанках, корректно установит знак числа.
Исходный код реализации больших чисел на C/C++
Теперь непосредственно сама реализация с комментариями.
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241 242 243 |
#include <iostream> #include <vector> #include <algorithm> #include <iomanip> using namespace std; //Деление для отрицательных чисел int my_div(int num, int diver) { if ((num < 0) && (num % diver)) return num / diver - 1; else return num / diver; } //Взятие по модулю для отрицательных чисел int my_mod(int num, int diver) { if ((num < 0) && (num % diver)) return num % diver + diver; else return num % diver; } //Класс "большое число", описывает способ хранения большого числа и //длинную арифметику class BigNumber { private: vector<int> chunks; int sign; //Настроиваемые параметры хранения большого числа //Количество символов в строке, которые станут одной "чанкой" static const int BASE = 2; //Зависит от BASE (BASE10 = 10^BASE), используется при нормализации static const int BASE10 = 100; //Служебные функции BigNumber _plus(BigNumber &a); BigNumber _minus(BigNumber &a); void _normalizationSigns(); void _normalizationChunks(); void _resize(int newsize); public: BigNumber operator + (BigNumber &num); BigNumber operator - (BigNumber &num); friend ostream & operator << (ostream &os, BigNumber &num); int getBASE() { return this->BASE; } //Конструктор, строку конвертирует в большое число BigNumber(string str) { int i; if (BASE != 1) { //Записываем с конца по BASE символов строки в чанки for (i = str.size() - BASE; i >= BASE - 1; i -= BASE) { chunks.push_back(stoi(str.substr(i, BASE))); } } else { for (i = str.size() - BASE; i >= BASE; i -= BASE) { chunks.push_back(stoi(str.substr(i, BASE))); } } //Дошли до начала строки, тут ищем знак и записываем последнюю чанку if (str[0] == '-') { sign = -1; if (i + BASE - 1 != 0) { chunks.push_back(stoi(str.substr(1, i + BASE - 1))); } } else { sign = 1; chunks.push_back(stoi(str.substr(0, i+BASE))); } } //Конструктор без аргументов - "пустое" положительное число BigNumber() { sign = 1; } }; //Изменение размера массива с чанками void BigNumber::_resize(int newSize) { chunks.resize(newSize); } /* * Функция нормализует большое число так, чтобы * во всех чанках лежали BASE-разрядные числа */ void BigNumber::_normalizationChunks() { int over = 0; //"Лишнее", которое будет кочевать в следующие чанки for (int i = 0; i < chunks.size() - 1; i++) { chunks[i] += over; //Прибавляем привесок от прошлых чанок over = my_div(chunks[i], BASE10); //Считаем перевес в текущей чанке chunks[i] = my_mod(chunks[i], BASE10); //Выравниваем чанку по базе } //Прибавляем перевес к последней чанке chunks[chunks.size() - 1] += over; //Обрабатываем перевес в последней чанке if (chunks[chunks.size() - 1] / BASE10) { over = my_div(chunks[chunks.size() - 1], BASE10); chunks[chunks.size() - 1] = my_mod(chunks[chunks.size() - 1], BASE10); chunks.push_back(over); //Создаем нову чанку с остатками } return; } //Функция нормализует большое число для печати так, //чтобы все чанки были положительными, но sign = -1(если число отрицательное) void BigNumber::_normalizationSigns() { //Если в последней чанке отрицательное число if (chunks[chunks.size() - 1] < 0) { sign = -sign; //Меняем знак числа chunks[0] = BASE10 - chunks[0]; //Нормализуем первую чанку for (int i = 1; i < chunks.size(); i++) { chunks[i] = (BASE10 - chunks[i] - 1) % BASE10; //Нормализуем ост. чанки } } //Убираем из числа нулевые чанки int i = chunks.size() - 1; while (chunks[i] == 0) { if (i == 0) { sign = 1; return; } chunks.pop_back(); i--; } return; } //Функция сложения BigNumber BigNumber::_plus(BigNumber &num) { BigNumber res; res.sign = this->sign; for (int i = 0; i < this->chunks.size(); i++) { res.chunks.push_back(this->chunks[i] + num.chunks[i]); } return res; } //Функция вычитания BigNumber BigNumber::_minus(BigNumber &num) { BigNumber res; res.sign = this->sign; for (int i = 0; i < this->chunks.size(); i++) { res.chunks.push_back(this->chunks[i] - num.chunks[i]); } return res; } //Оператор +, выполняет корректное сложение больших чисел BigNumber BigNumber::operator + (BigNumber &num) { BigNumber res; //Приводим размер чанок обоих чисел if (this->chunks.size() > num.chunks.size()) { num._resize(chunks.size()); } else { (*this)._resize(num.chunks.size()); } //Выполняем операцию в зависимости от знаков чисел if (sign == num.sign) { res = (*this)._plus(num); } else { res = (*this)._minus(num); } //Нормализуем результат res._normalizationChunks(); return res; } //Оператор -, выполняет корректное вычитание BigNumber BigNumber::operator - (BigNumber &num) { BigNumber res; //Приводим размер чанок if (this->chunks.size() > num.chunks.size()) { num._resize(chunks.size()); } else { (*this)._resize(num.chunks.size()); } //В зависимости от знаков, выполняем нужное действие if (sign != num.sign) { res = (*this)._plus(num); } else { res = (*this)._minus(num); } //Нормализуем результат res._normalizationChunks(); return res; } //Перегрузка оператора << для вывода в поток ostream & operator << (ostream &os, BigNumber &num) { num._normalizationSigns(); if (num.sign == -1) { os << '-'; } os << num.chunks[num.chunks.size() - 1]; for (int i = num.chunks.size() - 2; i >= 0; i--) { os << setw(num.getBASE()) << setfill('0') << num.chunks[i]; } return os; } int main() { BigNumber n1("-200000000000000000000000000000000000000000000000000000000000010"); BigNumber n2("-20"); BigNumber n3 = n1 - n2; cout << n3 << endl; return 0; } |
Заключение
Данная реализация не является оптимизированной по используемой памяти, особенно при маленьких значениях BASE, но является вполне рабочим вариантом. Кроме сложения и вычитания, большой интерес вызывает умножение (деление так вообще). Но с умножением разберемся как нибудь в следующий раз. А на сегодня у меня все, спасибо за внимание!