Быстрое возведение в степень

Question

Может ли кто-нибудь указать на сайт, где я могу найти алгоритм для эффективного вычисления возведения целых чисел в большие степени с использованием C #?

например. Я хочу рассчитать 2 ^ 60000 или 3 ^ 12345

Answer 1

Если это не домашнее задание, вы, вероятно, не хотите использовать собственную реализацию возведения в произвольную точность. Вычисление больших показателей типа, который вы описываете, является сложным - производительность в стороне.

Я бы порекомендовал использовать одну из существующих арифметических библиотек произвольной точности, например GMP , большинство из которых имеют библиотеки для доступа к ним из C #.

F # поддерживает арифметику произвольной точности с использованием класса BigInt (к которому вы также можете получить доступ из C #, если импортируете сборку, в которой он находится). Однако я не знаю, насколько оптимизировано возведение в степень BigInt.

Если вы просто пытаетесь узнать об эффективных алгоритмах возведения в степень, вы можете обратиться к алгоритму возведения в степень Square-And-Multiply .

Answer 2

Целочисленное возведение в степень может быть эффективно рассчитано с использованием метода, известного как «Вычисление по квадрату» link .

Этот метод также можно использовать для вычисления модульного возведения в степень link , который используется в некоторых асимметричных методах шифрования, таких как RSA.

Answer 3

Проверьте это: IntX для работы с БОЛЬШИМИ целыми числами. Возможно, вам придется написать свою собственную реализацию мощности, но поскольку умножение поддерживается, это не должно быть так сложно.

Редактирование с помощью 280Z28: еще одна реализация, включающая быстрое Pow, ModPow и тестирование простоты, - это BigInteger реализация (Code Project), которую я использовал в прошлом для задач Project Euler - хотя сейчас я работать с .NET 4.0 и использовать его System.Numerics.BigInteger реализация.