현재 시간:0:00전체 재생 길이:5:22
0 에너지 포인트
동영상 대본
지금부터 간단히 되돌아 보도록 하죠 우리는 어떠한 숫자 N이 소수인지 아닌지를 체크할것입니다 트라이얼 디비전(trial division)을 이용해서 말이죠 이곳이 N의 제곱근입니다 그리고 여기가 3입니다 3에서부터 시작하여 우리는 N의 제곱근을 만날때까지 숫자를 두개씩 뛰어넘어 이동할 것입니다 지나가는 각 지점마다 N으로 나누어지는지를 체크할 것입니다 지금까지 사람들은 우리가 지나가야하는 단계의 수를 줄이려고 노력했습니다 아마도 시작지점을 늦추거나 보다 큰 간격을 건너뛰는 방식을 사용해서요 저는 단순히 여기서 멈추기를 원하고 그러면 트라이얼 디비전을 위한 이상적인 경우에 대해 생각해볼까요? 과연 우리가 보다 창의적으로 간격을 계산하기 위한 최고의 방법은 무엇이 있을까요? 기억하시나요 모든 숫자 N은 어떠한 세 인수(factor)의 곱으로 이루어져있습니다 N의 제곱근이 여기라고 해보죠 우리는 오직 소수만을 거쳐서 건너가는것을 필요로 합니다 그것이 바로 우리가 할 수있는 최고의 방법일 것입니다 우리는 오직 소수만을 거쳐서 가려면, 결국 인수를 찾아야 한다는 것을 알고 있습니다 세 인수가 합성수인 것 말이죠 지금 문제는 '이 방법이 얼마나 효과적이냐?' 라는 것이죠 우리가 생각한 이 방법은 지금은 최고의 방법으로 보입니다 만일 우리가 체를 맨 처음 사용하는 새로운 알고리즘(algorithm)을 쓸 수 있다면 말이죠 그럼 N이 소수인지 아닌지 알아보는 새로운 알고리즘에 대해서 이야기해보죠 만일 당신이 체(sieve)를 이용하고 우리를 위한 충분히 긴 소수들의 리스트를 만들어낼 수 있다면 우리는 이러한 소수들의 리스트에 사용할 수 있는 트라이얼 디비전을 가지게 될것이고 이렇게 되면 우리는 오직 소수만을 건너뛰게 될 것입니다 어딘지는 모르겠지만 N의 제곱근까지 말이죠 무엇이 잘못되었을까요? 우리는 시간복잡도(time complexity)나 각 단계의 숫자를 볼 수 있도록 할 수 있습니다 예전에 제가 이야기했던 것을 기억하고 있나요? 예전에 이 알고리즘을 인용했었고 각 단계를 재는 스텝 카운터(step counter)를 각 루프 안에 넣었었지요 이제 단순히 step++라고 하면 여기의 스탭을 하나 증가시키는 것을 의미합니다 안쪽에 있는 다른 루프에서도 스탭 카운터가 존재합니다 step++를 해줍니다 체크하는것 가능하다면 마크하는 것까지 모두 상수 연산입니다 우리는 단지 각 루프안에 스텝 카운터를 가지고 있습니다 이제 여기서 비교를 할 겁니다 왼쪽에서는 우리가 예전에 사용하던 방식으로 중간은 체를 사용하여 N까지의 모든 소수의 리스트를 만드는 방법으로 오른쪽 부분은 체를 사용하여 N의 제곱근까지의 소수들의 리스트를 만들고 트라이얼 디비전을 이용하여 소수들을 구하는 방법입니다 그럼 작은 숫자를 넣었을때 어떻게 되는지 볼까요? 맨 처음으로 우리는 체에서 얼마나 많은 스탭 카운터가 진행되었는지를 볼 수 있습니다 이때는 어떠한 수정된 버전들도 트라이얼 디비전보다 실제로 느립니다 넣는 숫자가 커지게 되면, 각 체에서 사용되는 스텝 카운터의 숫자도 매우 빠르게 증가합니다 일단 중간의 값은 너무 크니 제외하고 N의 제곱근까지 체를 사용하고 트라이얼 디비전을 사용하는 방식과 트라이얼 디비전과 비교해보도록 하죠 지금은 오래된 트라이얼 디비전 방식이 더욱 효과적인 것 처럼 보입니다 우리가 N의 제곱근까지 체를 사용하고 추가로 트라이얼 디비전을 적용할 때 나오는 스탭 카운터의 수는 보다 빠르게 증가합니다 이 것은 진짜 향상된것이 아니라는 것이죠 아래 프로그램을 보면 저는 이러한 비교법을 사용하곤 했습니다 여기에 제가 어떠한 값을 설정했었는지 기록을 해둔 것이 있습니다 그럼 지금부터 어떻게 하면 보다 나은 방식으로 소수를 계산할수 있는지 알아보겠습니다 첫번째 단계로 우선 소수들을 위한 배열(Array)을 하나 만들고 이를 하드 디스크에 저장합니다 그리고 이 알고리즘은 단순히 트라이얼 디비전을 수행합니다 그리고 우리는 어떻게 소수들만 거쳐서 가는지 알고 있습니다 이는 제공된 소수의 리스트들을 읽어가기 때문이죠 보통 소수의 리스트는 20자리가 넘게 저장됩니다 심지어 100자리일수도 있죠 왜 우리는 할 수 없을까요? 문제는 컴퓨터의 메모리는 한정되어 있다는 것입니다 우리가 셀수없는 숫자들의 리스트를 가지고 다음과 같이 찾아나간다고 생각해봅시다 단순히 예를 들어보면 손으로 다음과 같이 작업하고 있다고 할 수 있어요 우리는 5가 소수라고 계산하고 종이에 5라고 써서 파일 보관함(filing cabinet)에 저장합니다 그 다음에는 7도 똑같은 방식으로 보관함에 저장합니다 9 아니 미안해요 11도 보관함에 저장합니다 그러면 보관함은 소수들로 꽉 차게 될 것이고 이것을 소수들이 들어있는 배열로 생각할 수 있습니다 우리가 20자리가 넘는 모든 소수나 100자리가 넘는 모든 소수들을 저장하기 위해서는 얼마나 큰 보관함이 필요할까요? 그 배열을 하드디스크에 저장하는 것이 가능할까요? 이것이 진정으로 왜 불가능한지 이해하기 위해서는 이 소수 배열이 얼마나 커지는지에 대해서 조금 더 깊게 살펴보아야 합니다 그러면 그 크기의 제한이 현재의 컴퓨터에서는 얼마나 되며 심지어 미래의 컴퓨터 하드웨어에서는 어떠할까요?