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

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

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

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

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

Целочисленное возведение в степень можно эффективно вычислить с помощью метода, известного как "Возведение в степень путем возведения в квадрат" ссылка.

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

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

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