빠른 지수화 구현

Question

누군가 C#을 사용하여 정수 지수를 대규모 전력으로 효율적으로 계산하기위한 알고리즘을 찾을 수있는 사이트를 지적 할 수 있습니까?

예를 들어. 2^60000 또는 3^12345를 계산하고 싶습니다.

Answer 1

이것이 숙제가 아닌 한, 당신은 아마도 임의의 정밀 지수를 구현하고 싶지 않을 것입니다. 설명하는 유형의 대규모 지수를 계산하는 것은 복잡합니다. 성능은 제쳐두고 있습니다.

나는 하나를 사용하는 것이 좋습니다 GMP와 같은 기존의 임의 정밀 산술 라이브러리 - 대부분은 C#에서 라이브러리에 액세스 할 수있는 라이브러리가 있습니다.

F#은 Bigint 클래스를 사용하여 임의의 정밀 산술을 지원합니다 (입력을 가져 오면 C#에서 액세스 할 수도 있음). 그러나 Bigint 지수가 얼마나 최적화되어 있는지 모르겠습니다.

지수를위한 효율적인 알고리즘에 대해 단순히 배우려고한다면 정사각형 지수를위한 알고리즘.

Answer 2

정수 지수는 "제곱에 의한 지수화"로 알려진 방법을 사용하여 효과적으로 계산할 수 있습니다. 링크.

이 방법은 모듈 식 지수를 계산하는 데 사용될 수도 있습니다. 링크, RSA와 같은 일부 비대칭 암호화 방법에 사용됩니다.

Answer 3

이것 좀 봐: intx 큰 정수와 함께 일합니다. 자신의 전력 구현을 작성해야 할 수도 있지만 곱셈이 지원되므로 그렇게 어렵지 않아야합니다.

280Z28에 의해 편집 : 빠른 Pow, Modpow 및 Primital Testing을 포함한 또 다른 구현은 이것입니다. Biginteger 과거 프로젝트 Euler 문제에 사용한 구현 (코드 프로젝트) - 이제 .NET 4.0과 함께 일하고 사용하지만 System.numerics.biginteger 구현.