C#. Длинная арифметика. Урок 6. Возведение в степень

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

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

public BigInteger Mod(BigInteger v)
{
BigInteger q;
BigInteger r;
if (this.AbsCompareTo(v) > -1)
{
if (v.arr.Count == 1)
{
int tempr = 0;
this.Divide(v.arr[0], out tempr);
return new BigInteger(tempr.ToString());
}
Divide(out q, out r, this, v);
return r;
}
else
{
return this;
}
}
public BigInteger Div(BigInteger v)
{
BigInteger q;
BigInteger r;
if (this.CompareTo(v) > -1)
{
if (v.arr.Count == 1)
{
int tempr = 0;
return this.Divide(v.arr[0], out tempr);
}
Divide(out q, out r, this, v);
}
else
{
return 0;
}
return q;
}

По факту мы добавили проверку на то, что никто не попытается поделить меньшее на большое, а также не запускаем длинное деление, если второе число короткое.
Алгоритм возведения большого числа в большую степень по модулю:

public BigInteger Pow(BigInteger k, BigInteger n)
{
BigInteger a = new BigInteger(arr, sign);
BigInteger b = new BigInteger("1");
while (k.CompareTo(new BigInteger("0")) > 0)
{

int r = 0;
BigInteger q = k.Divide(2, out r);
if (r == 0)
{
k = q;
a = a.Multiply(a).Mod(n);// [ a = (a*a)%n; ]
}
else
{
k = k.Substract(new BigInteger("1"));
b = b.Multiply(a).Mod(n);// [ b = (b*a)%n; ]
}
}
return b;
}

  • angryNerd

    1. Откуда взялся метод AbsCompareTo()?!
    2. Начиная с 5-ого урока не работает кнопка «Следующий урок» — ошибка «404» (Опера 12.16).

    • Метод AbsCompareTo() появился из метода Compare добавлением слова Abs в названии. А метод Compare стал учитывать еще и знак и при сравнении.

  • somewho

    В чем была проблема реализовать методы сложения вычитания и прочих арифметических операций с помощью перегрузки соответствующих операторов? Или так удобнее в целях наглядности

    • Мне просто не нравится переопределять арифметические операции для объектов, потому что мне кажется, что из-за этого могут возникнуть какие-то недоразумения, в целом да, для наглядности. Но если Вам хочется, Вы легко можете сделать это сами.

  • guest

    Скажите, а какой именно алгоритм возведения в степень вы использовали?

    • бинарное возведение в степень.

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

  • на Delphi

  • на Java

  • на C++