LongNumber

LongNumber::operator/ (const LongNumber& number)

{

LongNumber result;

// Проверка на нулевой делитель и на то, что делитель больше делимого (по модулю)

if (compareModules(*this, number) > 0)

return result;

if (number.length_ == 1 && number.array_[0] == 0) {

std::cerr << "Divizion by zero.\n";

return result;

}

// Создаем переменные, с которыми будем работать

LongNumber dividend (*this);

LongNumber divisor (number);

// Сделаем обе переменные положительными

dividend.sign_ = divisor.sign_ = 1;

// Временное хранилище для результатов деления

int storage[dividend.length_];

for (int i = 0; i < dividend.length_; i++)

storage[i] = -1;

int storagePosition = 0;

int storageLen = dividend.length_;

// Остаток от разности (elderDigits - x * divisor) (см. ниже)

LongNumber remainder;

// Узнаем длину делителя

int divisorLen = divisor.length_;

while (dividend >= divisor)

{

// Создаем переменную для старших разрядов делимого количеством divisorLen

LongNumber elderDigits;

elderDigits.setLength(divisorLen);

for (int i = dividend.length_ - divisorLen, j = 0; i < dividend.length_; i++, j++)

elderDigits.array_[j] = dividend.array_[i];

// Если получившиеся старшие разряды меньше делителя,

// нужно взять на один разряд больше из делимого.

if (elderDigits < divisor) {

elderDigits.setLength(divisorLen + 1);

for (int i = dividend.length_ - divisorLen - 1, j = 0; i < dividend.length_; i++, j++)

elderDigits.array_[j] = dividend.array_[i];

}

// Найдем такое максимальное x, которое удовлетворяло бы условию

// x * divisor <= elderDigits. x будет лежать в пределах (0..BASE)

int x = 0, w = 0, left = 0, right = BASE;

LongNumber supposition;

while (left <= right)

{

w = (left + right) >> 1;

supposition = divisor * w;

if (supposition > elderDigits)

{

right = w - 1;

}

else

{

left = w + 1;

x = w;

}

}

// Поместим полученный x во временное хранилище

storage[storagePosition++] = x;

// Запомним длину elderDigits

int elderDigitsLen = elderDigits.length_;

// Вычисляем остаток от разности (elderDigits - x * divisor)

remainder = elderDigits - (divisor * x);

// Если remainder оказался равен нулю, то помещаем в него поочередно следующие разряды dividend

// до тех пор пока не найдем ненулевой разряд или не закончится делимое.

// Если очередной разряд нулевой, сохраняем 0 в storage и увеличиваем elderDigitsLen на единицу.

LongNumber zeroNumber;

while (remainder == zeroNumber && elderDigitsLen < dividend.length_)

{

elderDigitsLen++;

remainder.setLength(1);

remainder.array_[0] = dividend.array_[dividend.length_ - elderDigitsLen];

if (remainder == zeroNumber) {

storage[storagePosition++] = 0;

}

}

// Вычислим насколько нужно сдвинуть remainder влево

int sh = dividend.length_ - elderDigitsLen;

// Сдвигаем

remainder = remainder << sh;

// Копируем оставшиеся младшие разряды dividend в младшие разряды remainder i = 0..sh-1

for (int i = 0; i < sh; i++)

remainder.array_[i] = dividend.array_[i];

// Заменяем dividend на remainder.

dividend = remainder;

}

// Теперь скопируем результаты из временного хранилища в результирующее число.

// Сначало посмотрим, какой длины должно быть число

int resultLen = 0;

for (int i = storageLen - 1; i >= 0; i--)

if (storage[i] >= 0)

resultLen++;

// Зададим длину результирующего числа

result.setLength(resultLen);

// Скопируем полученные резьтаты в разряды числа

for (int i = storageLen - 1, j = 0; i >= 0; i--)

{

if (storage[i] >= 0)

{

result.array_[j] = storage[i];

j++;

}

}

// Установим знак результирующего числа

result.sign_ = this->sign_ * number.sign_;

return result;

}

// Оператор поразрядного сдвига влево

// Равносильно умножению числа на BASE^n