빠른 전력 모듈러스 알고리즘의 도입은 많은 수의 소수점에서 모듈러스를 가져 오는 순진한 알고리즘의 한계에 의해 제안됩니다. 순진한 방법에서, 우리는 컴퓨팅 리소스를 매우 많이 소비하는 5^1003%31과 같은 숫자를 계산합니다. 전체 계산 프로세스에서 가장 번거로운 것은 5^1003 프로세스입니다.
단점 1 : 나중에 색인을 계산하는 과정에서 계산 된 숫자가 모두 증가하는 것은 아니며, 이는 많은 컴퓨팅 리소스 (주로 시간 및 공간)를 차지합니다.
단점 2 : 계산의 숫자는 너무 커서 기존 컴퓨터가 그러한 긴 데이터를 기록 할 수 없으므로이 문제를 해결하는보다 효율적인 방법을 생각해야합니다.
AB%C를 계산할 때 가장 편리한 방법은 수학 기능에서 POW 방법을 호출하는 것입니다. 그러나 때로는 B의 전력에 대한 A의 수가 너무 크고, 이중 정제 더블도 오버플로됩니다. 현재 AB%C의 결과를 얻기 위해 빠른 전력 모듈러스 알고리즘을 사용하여 간단하고 빠르게 원하는 결과를 얻을 수 있습니다.
숫자가 넘쳐나는 것을 방지하고 복잡성을 줄이려면 다음 공식을 사용해야합니다.
ABMOD C = (A 모드 C) BMOD C
이 공식의 의미는 다음과 같습니다. 이 공식이 전이적이라는 것을 쉽게 알 수 있으므로 오버플로를 방지하기 위해 나머지를 지속적으로 복용함으로써 더 작고 작게 만들 수 있습니다.
이론적 으로이 공식으로 코드를 쓸 수 있습니다. A a를 지속적으로 모화함으로써 결과가 오버플로되지 않도록합니다. 이것은 실제로 더 큰 전력으로 전력의 계수를 계산할 수 있지만,이 방법의 복잡성은 여전히 O (n)이며 빠르지 않습니다.
전력 계수를 더 빨리 계산하려면 다음 공식에도 의존해야합니다.
ab mod c = (a2) b/2 mod c, b는 짝수 숫자입니다.
ab mod c = ((a2) b/2 ・ a) mod c, b는 홀수입니다.
이 공식은 매우 간단합니다. 원칙은 B를 A의 제곱으로 지속적으로 대체하고 B를 원래 절반으로 바꾸는 것입니다. 우리는 첫 번째 공식을 통해 숫자의 모듈이 동일한 힘을 가지고 있음을 알고 있기 때문에 (이 문장은 약간 혼란 스럽습니다. 이는 공식 1을 의미합니다). 그런 다음 A 대신 A*A%C의 결과를 사용하는 효과는 동일합니다.
따라서 위의 공식에 따라 복잡성 O (LOGN)로 빠른 전력을 계산하는 방법을 얻습니다.
import java.util.scanner; public class main {public static void main (string [] args) {scanner in = new Scanner (System.In); int a = in.nextInt (), b = in.nextInt (), c = in.nextInt (); int res = 1; A %= C; for (; b! = 0; b /= 2) {if (b % 2 == 1) res = (res * a) % c; a = (a * a) % c; } system.out.println (Res); }}이 알고리즘은 거의 이와 같습니다. 첫 번째 단계는 A*A가 처음으로 수행 될 때 숫자가 넘치지 않도록%= C를 줄이는 것입니다. for 루프에서 b가 홀수 인 경우 res = res*a를 놔두고 A를 먼저 곱한 다음 처리 한 다음 처리하십시오. 숫자가 넘치지 않도록하기 위해 RES*A의 결과 모드 C가 직접 작동합니다. 루프의 경우 조만간 B는 1과 같고 IF 분기를 입력 한 다음 최종적으로 RES 및 MOD C의 값을 계산 한 다음 최종 결과를 계산합니다.
요약
위의 내용은 Java 언어의 빠른 전력 모듈러스 알고리즘 구현에 대한이 기사의 모든 자세한 설명입니다. 모든 사람에게 도움이되기를 바랍니다. 관심있는 친구는이 사이트의 다른 관련 주제를 계속 참조 할 수 있습니다. 단점이 있으면 메시지를 남겨 두십시오. 이 사이트를 지원해 주신 친구들에게 감사드립니다!