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

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

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

private List normalize(List arr)
{
while (arr.Count > 0 && arr[arr.Count - 1] == 0)//удаляем лидирующие нули
{
arr.RemoveAt(arr.Count - 1);
}
return arr;
}

Напишем код умножения короткого числа на длинное:

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

Для умножение длинного на длинное необходимо взять одно число и брать из него разряды по очереди, а затем умножать длинное на короткое. Суммирую такие результаты, при этом не забывая их смещать в зависимости от разряда мы полностью повторяем алгоритм перемножения чисел столбиком:

public BigInteger Multiply(BigInteger value)
{
BigInteger ans = new BigInteger("0");
for (int i = 0; i < arr.Count; i++) { BigInteger temp = value.Multiply(arr[i]);//умножаем текущий разряд числа на другое длинное число for(int j = 0; j < i; j++)//сдвигаем его { temp.arr.Insert(0,0); } ans = ans.Add(temp);//складываем с другими } return ans; }

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

  • на Delphi

  • на Java

  • на C++