| [ QuizWit ] in KIDS 글 쓴 이(By): shaper (나~랑께롱!) 날 짜 (Date): 1998년 7월 15일 수요일 오전 04시 43분 55초 제 목(Title): [답신!] 도와주세요! 이 수식의 계산좀... /* * 다음 프로그램은 형식만 쓴 것이므로 원하는 정도의 자리수연산을 * 할 수 있게 고치세요. * * 첫번째 방법(modI)은 (M*G^X)%P = ((M*G)%P*(G^(X-1))%P)%P 을 이용하여 * (M*G)%P --> M 으로 계속 갱신해가는 방법으로서 가장 간단하긴 하나 * 계산시간이 가히 무지막지하게 걸리는 방법이므로 권할 만한 것이 못됨. * * 두번째 방법(modII)은 * (M*G^X)%P = ( M * G^(2*X1+Y1) )%P = ( (M*G^Y1)%P * ( ((G^2)%P)^X1)%P )%P * 을 이용한 것으로 ( Atreyu님의 식에서는 제일 마지막의 %P가 빠져 있음) * Y1=X%2, X1=X/2 --> X, M*G^Y1 --> M, (G^2)%P --> G 으로 계속갱신하여 * X=0 즉 G^X=1이 될 때까지 하는 것으로 이렇게 되면 위의 마지막의 %P는 * 무의미해짐. * 하여튼 이 방법은 위의 첫번째방법에 비교도 안될정도로 빠름. * 계산속도비교 : modI = O(X), modII = O(log X) ..음.. 비교는 되는군... * P.S. : 두번째 방법에서 M!=0 검사와 G==0 검사는 더이상의 계산이 무의미할 때 * 일찍 빠져나오도록 하는 것으로 없어도 상관은 없음. */ long modI(long G, long X, long P) { long M; for ( M=1, G%=P; X>0 && M!=0; X-- ) M = ( M * G ) % P; return M; } long modII(long G, long X, long P) { long M; for ( M=1, G%=P; X>0 && M!=0; X/=2 ) { if ( G == 0 ) M = 0; if ( X%2 == 1 ) M = ( M * G ) % P; G = ( G * G ) % P; } return M; } void main() { long G, X, P; printf(" G^X mod P ---> G, X, P = ?\n"); scanf("%ld%ld%ld",&G,&X,&P); printf("First Method = %ld\n",modI (G,X,P)); printf("Second Method = %ld\n",modII(G,X,P)); } ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ 나가 누구냐고요 ? 나가 누구냐하면 말이요.... 바로 " 나~~랑께롱! " ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ |