C#. Длинная арифметика. Урок 4. Знак и сравнение

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

В данной статье мы научимся хранить отрицательные большие числа, а также сравнивать их по модулю. Эти две операции нам нужны для реализации деления. Для того, чтобы понимать положительное или отрицательное большое число перед нами мы добавим флаг sign, который будет равен true, если число неотрицательное и равен false в другом случае. К сожалению, нам придется чуть — чуть дописать все наши функции, но я думаю вы сами догадаетесь как, а нам конкретно интересно переписать функцию вычитания, чтобы в случае, если уменьшаемое меньше вычитаемого нам возвращался корректный результат. Для этого сначала перепишем наши конструкторы так, чтобы они принимали на вход sign:

private bool sign = true;
public void ChangeSign(bool flag)
{
sign = flag;
}
public BigInteger(string s)
{
int tempValue = 0;
int tempOrder = 0;
sign = true;
for (int i = s.Length - 1; i >= 0; i--)
{
if(i==0 && s[0]=='-')
{
sign = false;
}
else
{

if (tempOrder == order)
{
arr.Add(tempValue);
tempValue = int.Parse(s[i].ToString());
tempOrder = 1;

}
else
{
tempValue = tempValue + (int)Math.Pow(10,tempOrder) * int.Parse(s[i].ToString());
tempOrder++;
}
}

}
if(tempOrder!=0){
arr.Add(tempValue);
}
}
public BigInteger(int[] arr, bool sign)
{
for (int i = 0; i < arr.Length; i++) { this.arr.Add(arr[i]); } this.sign = sign; } public BigInteger(List arr, bool sign)
{
this.arr = arr;
this.sign = sign;
}

Теперь нам необходим метод для сравнения двух больших чисел. Напишем его для модуля, а при необходимости будем сравнивать знак, дело в том, что работа с отрицательными большими числами нужна нам только в рамках специфичных операций, в целом же мы можем не поддерживать операции с ними:

public int CompareTo(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; }

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

public string ToString()
{
StringBuilder ans = new StringBuilder();
if (!sign)
{
ans.Append('-');
}
ans.Append(arr[arr.Count - 1].ToString());
for (int i = arr.Count - 2; i >= 0; i--)
{
string temp = arr[i].ToString();
int zeroCount = order - temp.Length;
for (int j = 0; j < zeroCount; j++) { ans.Append('0'); } ans.Append(temp); } return ans.ToString(); }

Осталось разобраться с операцией вычитания. Если первое число больше второго, то операция вычитания возвращает корректный результат, если первое большое число меньше второго, то необходимо из второго числа вычесть первое и сменить знак на минус. Конечно, это верно только для неотрицательных чисел.

public BigInteger Substract(BigInteger value)
{
if (this.CompareTo(value)==-1)
{
BigInteger temp = value.Substract(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); }

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

  • на Delphi

  • на Java

  • на C++