Третья часть из серии статей про реализацию больших чисел на C/C++, в начале по традиции ссылки на предыдущие части.
- Реализация больших чисел на C/C++ со сложением и вычитанием;
- Операторы сравнения больших чисел — реализация на C/C++;
- Умножение больших чисел — реализация на C/++;
Наконец я добрался до реализации самых интересных операций. В совокупности с предыдущими наработками наши большие числа уже можно использовать для реализации различных алгоритмов, например, из области криптографии. О них я тоже скорее всего напишу, но уже чуть позже.
Умножение больших чисел
Начать предлагаю с умножения, оно попроще в реализации и понимании. Сразу оговорюсь, это не реализация быстрого блочного умножения, а пока просто «в лоб». Про блочное умножение напишу как-нибудь в следующий раз.
По традиции сначала объявление оператора и функций в классе BigNumber.
1 2 3 4 5 |
private: BigNumber _multi(BigNumber &); BigNumber _simplemulti(BigNumber &); public: BigNumber operator * (BigNumber); |
Две приватные функции, одна реализует приведение больших чисел по размеру, а вторая выполняет непосредственное умножение.
Исходный код умножения больших чисел на 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 |
//Функция умножения больших чисел BigNumber BigNumber::_simplemulti(BigNumber &num) { BigNumber result; result._resize(2 * this->chunks.size()); result.sign = this->sign; for (int i = 0; i < this->chunks.size(); i++) { for (int j = 0; j < num.chunks.size(); j++) { result.chunks[i + j] += this->chunks[i] * num.chunks[j]; } } result._normalizationChunks(); return result; } //Функция приводит большие числа к нужному размеру BigNumber BigNumber::_multi(BigNumber &num) { auto maxSize = max(this->chunks.size(), num.chunks.size()); int newSize = 1; while (newSize < maxSize) { newSize *= 2; } (*this)._resize(newSize); num._resize(newSize); //return (*this)._fastmulti(num); return (*this)._simplemulti(num); } BigNumber BigNumber::operator * (BigNumber num) { BigNumber result; result = (*this)._multi(num); result._normalizationChunks(); if (this->sign == num.sign) { result.sign = 1; } else { result.sign = -1; } return result; } |
Совсем короткая получилась заметка, но оно и к лучшему. Спасибо за внимание!