C#. Длинная арифметика. Урок 5. Деление

Длинная арифметика   3 марта 2013  Автор статьи:  

Теперь перейдем к достаточно сложной операции над большими числами — делению. Сначала, как и с умножением реализуем деление большого числа на короткое:

public BigInteger Divide(int v, out int r)
{
int[] ans = new int[arr.Count];//результат деления
r = 0;//остаток
int j = arr.Count - 1;
while (j >= 0)
{
long cur = (long)(r) * (long)(myBase) + arr[j];
ans[j] = (int)(cur/ v);
r = (int)(cur % v);
j--;
}

return new BigInteger(ans, sign);
}

Удаление лидирующих нулей теперь происходит прямо в конструкторе, так что не забудьте его выполнить, если у вас не так. Очевидно, что при делении длинного на короткое, мы можем поразрядно брать и считать ответ, при этом он не уменьшится больше чем на один разряд. В переменной r в этом случае мы храним остаток, который не превышает соответственно числа v, которое в данной задачи короткое, поэтому r тоже короткое. В принципе весь этот алгоритм моделирует деление столбиком, просто оно тут достаточно упрощено тем, что делитель может быть только одноразрядным, при этом все равно возникают некоторые проблемы с переполнением, поэтому я использую приведение типов, чтобы избежать их.
Дальше будет рассмотрен алгоритм деления большого числа на большое. Данный алгоритм достаточно труден, поэтому давайте подумаем, а как мы можем это реализовать? Первая, самая очевидная идея это реализовать алгоритм деления столбиком, но возникает куча проблем, которые мы смогли обойти в коротком делении. Например, нельзя тривиальным образом свести короткое деление к длинному, как мы это сделали в умножении. Следующая идея, которая может придти вам в голову это организовать бинарный поиск по ответу, действительно данный поиск будет работать за логарифм отрезка в котором мы ищем, в худшем случае этот отрезок равен количеству цифр в делимом, а для проверки ответа можно воспользоваться умножением, которое можно написать за nlogn, где n — кол-во разрядов. Т.е какой — то плохой алгоритм деления мы все таки в состоянии придумать, но все же хочется уметь делить длинные числа за более хорошее время, поэтому дальше я расскажу алгоритм Кнута деления длинных чисел.
Дано:
u = u[m+n-1]..u[0] — делимое по основанию b
v = v[n-1]..v[0] — делитель по основанию b
[u/v] = q[m]..q[0] — частное
u mod v = r[n-1]..r[0] — остаток

  • Нормализация. Нам необходимо преобразовать делимое и делитель, умножив на коэффициент d. Данная операция является очень важной, так как позволяет избегать множество паленых моментов в этом алгоритме. d = [b/(v[n-1]+1)]. Ну и умножаем. Если d=1, то добавляем нулевой разряд u[m+n]=0
  • Начальная установка j. j = m
  • Вычислить временное q. tempq=[(u[j+n]*b+u[j+n-1])/v[n-1]], tempr — остаток от такого деления. Если tempq=b или q*v[n-2]>b*tempr + u[j+n-2], то tempq = tempq — 1 и tempr = tempr + v[n-1]. Необходимо повторять данную проверку пока temr < b
  • Умножить и вычесть. u[j+n]..u[j] = u[j+n]..u[j] — tempq * v[n-1].. v[0]. Значение разрядов должно быть всегда положительным, поэтому если мы получаем отрицательный разряд, то должны прибавить b^(n+1). Причем следует запомнить заимствование слева из старшего разряда.
  • Проверка остатка. q[j] = tempq. Если результат 4 — го шага был отрицательным, то перейти к шагу 6, иначе к шагу 7.
  • Компенсировать сложение. Вероятность данного шага очень мала, а именно r/b, т.е при большой базе вы очень редко будете попадать в отрицательные числа. q[j] = q[j] — 1. u[j+n]..u[j] = u[j+n]..u[j] + v[n-1]..v[0], при этом произойдет перенос в разряд слева от u[j+n], но им следует пренебречь, так как перенос погашается заимствованием из того же разряда произведенном на шаге 4.
  • Цикл по j. j уменьшаем на 1. Если j>=0, то вернуться к шагу 3.
  • Денормализация. q[m]..q[0] — искомое частное, а для получения искомого остатка достаточно u[n-1]..u[0]/d


public static int Divide(out BigInteger q, out BigInteger r, BigInteger u, BigInteger v)
{
//начальная инициализация
int n = v.arr.Count;
int m = u.arr.Count - v.arr.Count;
int[] tempArray = new int[m+1];
tempArray[m] = 1;
q = new BigInteger(tempArray, true);

//Нормализация
int d = (myBase / (v.arr[n - 1] + 1));
u = u.Multiply(d);
v = v.Multiply(d);
if (u.arr.Count==n+m)//аккуратная проверка на d==1
{
u.arr.Add(0);
}
//Начальная установка j
int j = m;
//Цикл по j
while (j >= 0)
{
//Вычислить временное q
long cur = (long)(u.arr[j + n]) * (long)(myBase) + u.arr[j + n - 1];
int tempq = (int)(cur / v.arr[n - 1]);//нормализация помогает не выпрыгнуть за границу типа
int tempr = (int)(cur % v.arr[n - 1]);
do
{
if (tempq == myBase || (long)tempq * (long)v.arr[n - 2] > (long)myBase * (long)tempr + u.arr[j+n-2])
{
tempq--;
tempr += v.arr[n - 1];
}
else
{
break;
}
}
while(tempr < myBase); //Умножить и вычесть BigInteger u2 = new BigInteger(u.arr.GetRange(j, n + 1), true); u2 = u2.Substract(v.Multiply(tempq)); bool flag = false; if (!u2.sign)//если отрицательные { flag = true; List bn = new List();
for (int i = 0; i <= n; i++) { bn.Add(0); } bn.Add(1); u2.ChangeSign(true); u2 = new BigInteger(bn, true).Substract(u2); } //Проверка остатка q.arr[j] = tempq; if (flag) { //Компенсировать сложение q.arr[j]--; u2 = u2.Add(v); if(u2.arr.Count>n+j)
u2.arr.RemoveAt(n + j);

}
//меняем u, так как все вычисления происходят с его разрядами
for (int h = j; h < j + n; h++) { if (h - j >= u2.arr.Count)
{
u.arr[h] = 0;
}
else
{
u.arr[h] = u2.arr[h - j];
}
}
j--;
}
q.arr = q.normalize(q.arr);
//Денормализация
int unusedR = 0;
r = new BigInteger(u.arr.GetRange(0, n), true).Divide(d, out unusedR);
return 0;
}

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

Научиться программировать

  • на Delphi

  • на Java

  • на C++