C#. Длинная арифметика. Урок 2. Сложение и вычитание

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

В предыдущей статье мы уже научились считывать и выводить большие числа. Теперь пришло время разобраться в сложении и вычитании. Для этого нам придется вспомнить школу. В ней мы складывали и вычитали столбиком. Для этого действа как мы помним, мы записывали числа одно под другим и шли с конца на начало, выполняя сложение или вычитание по столбцам. При этом, нужно было еще держать в уме некоторое число, которое переходило в следующий столбец. Для реализации данных операций напишем еще один конструктор у класса BigInteger. Он будет принимать на вход массив целых чисел, в котором написано большое число в уже известном нам формате, а именно, сначала младшие разряды, а затем старшие:

public BigInteger(int[] arr)
{
for (int i = 0; i < arr.Length; i++) { this.arr.Add(arr[i]); } }

Реализуем такой же конструктор, но принимающий на вход список, так как он более удобен в работе:

public BigInteger(List arr)
{
this.arr = arr;
}

Сложение выполним следующим образом, сначала определим длину большего числа. Затем пробежимся циклом по ней, в случае, если длины числа не хватаем возьмем в качестве значения текущего "разряда" ноль. После этого выполним сложение двух разрядов и временной переменной k, теперь если текущее значение вдруг стало больше чем размер одного разряда выполним перенос.

public BigInteger Add(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);
}

Вычитание выполняется аналогичным образом. Используется некоторая переменная, которая отвечает за перенос, но только теперь она вычитается вместе со вторым и если число стало отрицательным, то мы добавляем базу к числу, а перенос делаем равный единице. Это очень легко понять на примере:
100000000 - 1 = 99999999

Индекс 0 1
Первое число 0 1
Второе число 1 0

Таким образом первым действием мы вычитаем из 0 1, получаем -1, после этого проверяем больше ли нуля получившиеся число, так как оно меньше, то прибавляем к нему базу получаем 99999999, после этого вычитаем из 1 - 0 - перенос, так как перенос на предыдущем шаге стал равен 1, то получаем ноль. Для того, чтобы получить окончательный результат необходимо только удалить лидирующие нули:

public BigInteger Substract(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;
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; } } while (ans.Count > 0 && ans[ans.Count - 1] == 0)//удаляем лидирующие нули
{
ans.RemoveAt(ans.Count - 1);
}
return new BigInteger(ans);
}

  • Леонид

    Здравствуйте, не понятно что за переменная myBase? Какого она типа и где объявляется?

    Извините что задаю вопрос в этом уроке, но что за метод такой ChangeSign? Не могли бы хотя бы описать его или привести пример его реализации!?

    • Здравствуйте, переменная myBase нужна для того, чтобы указать сколько цифр хранить в одной ячейке массива. Это важный параметр для быстродействия. Например, если вы будете хранить только одну цифру в ячейке, то у вас будет выполняться много действий в цикле, если вы будете хранить максимальное возможное количество цифр, то тоже возникают какие — то проблемы, поэтому обычно выбирают базу исходя из практики. Метод ChangeSign меняет знак числа на указанный. (4 урок)

  • Артем

    Add теперь тоже выдает бредятину полнейшую

    • Вышли мне свой код на почту lordrp@bk.ru Ты что-то не правильно скопировал. Или в конце уроков, там где-то были все исходники скачай и посмотри, что делаешь не так. Если что в первых уроках сложение и вычитание не умеет работать с отрицательными числами.

      • Артем

        Я уже разобрался, написал свой, но на базе вашего, сам бы долго додумывался до некоторых вещей, чтобы сделать с отрицательными долго возился, конечно…

  • Андрей

    чему равна переменная myBase? у вас изначально база(order) задана и =8 а myBase я так понимаю должна быть 9?

    • 10^order по умолчанию. Но можно изменить на любое свое значение, тогда операции будут происходить по этой базе.

  • Валерия

    Какая-то странная штука. На вход в функцию сложения подается одно значение, так как же мы складываем два числа в таком случае?

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

  • на Delphi

  • на Java

  • на C++