Быстрая реализация возведения в степень

Question

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

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

Answer 1

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

Я бы порекомендовал использовать один из existing arbitrary precision arithmetic libraries, like GMP - большинство из которых имеют библиотеки для доступа к ним с C#.

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

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

Answer 2

Отметьте: IntX для работы с целыми числами LARGE. Возможно, вам придется написать свою собственную реализацию власти, но, поскольку поддерживается умножение, это не должно быть так сложно.

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

Answer 3

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

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