이 문제는 페르마의 작은 정리(Fermat's Little Theorem)을 이용해

해당 수가 소수임을 확인하는 프로시저를 사용하였을 때

자람 차수(order of growth)가 Θ(log n)임을 확인하는 문제입니다.

그래서 위에서처럼 프로시저를 만든 후 프로그램을 돌렸습니다.

하지만 다음과 같은 에러가 뜨더군요.

알고리즘에 문제가 있는가 살펴보았지만 그렇지 않았습니다.

에러 내용을 대충 생각해보니 수가 너무 크다는 말을 하는 듯싶었습니다.

페르마의 작은 정리는 n이 소수라면 0<a<n인 어떤 수 a를 잡아

aⁿ은 a modulo n으로 나누어 떨어진다는 것입니다.

따라서 n이 커질수록 aⁿ은 매우 커지기에 감당할 수 없겠지요.

그렇기에 n을 작게 잡아보았습니다.

차이를 알 수 없습니다.OTL....

테스트를 한 노트북은 4년 전에 구입한 것이라 그리 좋지 못합니다.

그런데도 이렇게 암담하다니...ㅜㅜ

여기서도 잘 맞아떨어지지 않는다면, 그 까닭을 설명하라고 합니다.

그 결과를 알 수 없기에 얘기하기 힘들지만,

해당 소스를 보면 아마 기대했던 것보다는 조금 나쁘게 나올 듯싶습니다.

왜냐하면 a를 구하기 위해 random이라는 프로시저를 사용하고 있으며

aⁿ은 그 수가 매우 크기에 계산 시간이 조금 더 걸릴 듯싶습니다.

참조

Structure and Interpretation of Computer Programs 2/E - Page 70

PS

이 문제를 풀다가 이상하게 춥다는 생각이 들어 주위를 살펴보니 창문이 열려있더군요.

덕분에 감기에 걸려 이제서야 이 문제의 글을 적습니다.ㅜㅜ

크리에이티브 커먼즈 라이선스

이 저작물은 크리에이티브 커먼즈 코리아 저작자표시-비영리-변경금지 2.0 대한민국 라이선스에 따라 이용하실 수 있습니다.