C#. Длинная арифметика. Урок 7. Отрицательные большие числа

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

Пришло время вылизать наш код для работы с отрицательными большими числами. Так как мы уже умеем осуществлять различные операции с неотрицательными числами, то нам следует просто учесть знак. Для этого мы вынесем в отдельные методы, написанные нами операции, добавим приставку Abs и сделаем их приватными, а в стандартном имени просто обработаем знаки с помощью if-ов. Кроме этого добавим функцию Equals, чтобы можно было удобно сравнивать большие числа. В предыдущих уроках мы уже добавили в класс BigInteger поле sign, которое показывает является ли число положительным или отрицательным. Для удобства программирования необходимо добавить статическими членами 0 и 1, чтобы не создавать их каждый раз для использования в алгоритмах. Итак, начнем со сравнения, в нем мы рассмотрим четыре случая:

public int CompareTo(BigInteger other)
{
if (this.sign && other.sign)//оба положительных
{
return AbsCompareTo(other);
}
if (this.sign && !other.sign)//первое число положительное
{
return 1;
}
if (!this.sign && other.sign)//второе число положительное
{
return -1;
}
return -1 * AbsCompareTo(other);//оба отрицательные
}
private int AbsCompareTo(BigInteger other)
{
int ans = 0;
if (this.arr.Count == other.arr.Count)
{
for (int i = 0; i < this.arr.Count; i++) { if (this.arr[i] > other.arr[i])
{
ans = 1;
}

if (this.arr[i] < other.arr[i]) { ans = -1; } } } else { if (this.arr.Count > other.arr.Count)
{
ans = 1;
}
if (this.arr.Count < other.arr.Count) { ans = -1; } } return ans; }

Теперь реализуем сложение. В нем тоже существует 4 варианта, если оба положительные, то мы должны вернуть результат сложения по модулю (обычный результат), если одно из чисел отрицательное, то мы должны вернуть результат вычитания, а если оба отрицательные, то мы их складываем по модулю и у результата меняем знак. Для реализации сначала переименуем наши методы сложения и вычитания больших чисел:

public BigInteger AbsAdd(BigInteger value)
{
int k = 0;//значение переноса
int n = Math.Max(arr.Count, value.arr.Count);//максимальная длина числа
List ans = new List();//результирующий массив
for (int i = 0; i < n; i++) { int tempA = (arr.Count > i)? arr[i] : 0;//временное значение i-го разряда из первого числа
int tempB = (value.arr.Count > i) ? value.arr[i] : 0;//временное значение i-го разряда из второго числа
ans.Add(tempA + tempB + k);
if (ans[i] >= myBase)//если результат получился больше базы
{
ans[i] -= myBase;
k = 1;
}
else
{
k = 0;
}
}
if (k == 1)
{
ans.Add(k);
}
return new BigInteger(ans, true);
}
public BigInteger AbsSubstract(BigInteger value)
{
if (this.AbsCompareTo(value)==-1)
{
BigInteger temp = value.AbsSubstract(this);
temp.ChangeSign(false);
return temp;
}
int k = 0;//перенос
int n = Math.Max(arr.Count, value.arr.Count);
List ans = new List();
for (int i = 0; i < n; i++) { int tempA = (arr.Count > i) ? arr[i] : 0;
int tempB = (value.arr.Count > i) ? value.arr[i] : 0;
ans.Add(tempA - tempB - k);
if (ans[i] < 0) { ans[i] += myBase;//прибавляем базу k = 1;//задаем перенос } else { k = 0; } } return new BigInteger(normalize(ans), true); }

Вот так выглядит сложение:

public BigInteger Add(BigInteger value)
{
if (this.sign && value.sign)
{
return this.AbsAdd(value);
}
if (!this.sign && value.sign)
{
return value.AbsSubstract(this);
}
if (this.sign && !value.sign)
{
return this.AbsSubstract(value);
}
BigInteger ans = this.AbsAdd(value);
ans.ChangeSign(false);
return ans;
}

Вычитание больших чисел с учетом знака:

public BigInteger Substract(BigInteger value)
{
if (this.sign && value.sign)
{
return this.AbsSubstract(value);
}
if (!this.sign && value.sign)
{
BigInteger ans = this.AbsAdd(value);
ans.ChangeSign(false);
return ans;
}
if (this.sign && !value.sign)
{
return this.AbsAdd(value);
}
return value.AbsSubstract(this);
}

Умножение больших чисел со знаком реализуется еще проще. Знак у результата либо положительный, либо отрицательный:

public BigInteger Multiply(int value)
{
BigInteger ans = this.AbsMultiply(Math.Abs(value));
if (this.sign && value >= 0)
{
return ans;
}
if (!this.sign && value < 0) { return ans; } ans.ChangeSign(false); return ans; } public BigInteger AbsMultiply(int value) { if (value >= myBase)
{
throw new Exception("This value is bigger than base");
}
int k = 0;
List ans = new List();
for (int i = 0; i < arr.Count; i++) { long temp = (long)arr[i] * (long)value + k; ans.Add((int)(temp % myBase)); k = (int)(temp / myBase); } ans.Add(k); return new BigInteger(normalize(ans), true); } public BigInteger Multiply(BigInteger value) { BigInteger ans = this.AbsMultiply(value); if((this.sign && value.sign)||(!this.sign && !value.sign)) { return ans; } ans.ChangeSign(false); return ans; } public BigInteger AbsMultiply(BigInteger value) { BigInteger ans = new BigInteger("0"); for (int i = 0; i < arr.Count; i++) { BigInteger temp = value.AbsMultiply(arr[i]); for(int j = 0; j < i; j++) { temp.arr.Insert(0,0); } ans = ans.AbsAdd(temp); } return ans; }

Короткое деление переписывается также как и умножение:

public BigInteger Divide(int v, out int r)
{
if (v == 0)
{
throw new Exception("divide by zero");
}
BigInteger ans = this.AbsDivide(Math.Abs(v), out r);
if ((this.sign && v > 0) || (!this.sign && v < 0)) { return ans; } ans.ChangeSign(false); r = -r; return ans; } public BigInteger AbsDivide(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, true);
}

Код деления по Кнуту мы приводить заново не будем, я надеюсь вы сможете переписать его и сами:

private static int Divide(out BigInteger q, out BigInteger r, BigInteger u, BigInteger v)
{
int ans = AbsDivide(out q, out r, u, v);
if ((u.sign && v.sign) || (!u.sign && !v.sign))
{
return ans;
}
q.ChangeSign(!q.sign);
r.ChangeSign(!r.sign);
return ans;

}

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

  • на Delphi

  • на Java

  • на C++