В данной статье мы рассмотрим возведение в степень больших чисел. Возводить мы будем в большую степень по какому — то модулю. Очевидно, что нельзя в тупую начать перемножать числа, как следует из определения степени. Для реализации данной операции нам поможет бинарное возведение в степень. Пусть у нас есть большое число 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;
>
1. Откуда взялся метод AbsCompareTo()?!
2. Начиная с 5-ого урока не работает кнопка «Следующий урок» — ошибка «404» (Опера 12.16).
Метод AbsCompareTo() появился из метода Compare добавлением слова Abs в названии. А метод Compare стал учитывать еще и знак и при сравнении.
В чем была проблема реализовать методы сложения вычитания и прочих арифметических операций с помощью перегрузки соответствующих операторов? Или так удобнее в целях наглядности
Мне просто не нравится переопределять арифметические операции для объектов, потому что мне кажется, что из-за этого могут возникнуть какие-то недоразумения, в целом да, для наглядности. Но если Вам хочется, Вы легко можете сделать это сами.
Скажите, а какой именно алгоритм возведения в степень вы использовали?
Задача состоит в том, чтобы возвести большое число n ( 0 | улучшить этот вопрос
1 ответ 1
А вы не хотите учесть, что ваш вывод
должен, вообще-то, выводить еще и ведущие нули (буде таковые имеются). Т.е. если ваш элемент вектора меньше того самого миллиарда, то он-то все равно должен выводиться в 9 знакомест?
Быстрое возведение в степень – это алгоритм, который позволяет возвести любое число в натуральную степень за сокращенное количество умножений.
Описание алгоритма
Для любого числа x и четной степени n выполняется тождество:
x n = (x n/2 ) 2 = x n/2 ⋅ x n/2
Это и является основой алгоритма быстрого возведения в степень. Поскольку такое разбиение позволяет, за одну операцию умножения, вдвое уменьшить вычисляемую степень.
Для случая нечетной степени, достаточно её понизить на единицу:
x n = x n — 1 ⋅ x, при этом (n — 1) четное число.
Рекурсивная реализация быстрого возведения в степень
Для оптимизации можно заменить проверку четности и деление на 2 битовыми операциями:
Итерационная реализация
В этом методе, быстрого возведения в степень, также используем оптимизацию проверки на четность и деления на два:
