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

Question

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

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

Answer 1

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

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

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

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

Answer 2

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

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

Answer 3

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

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