현재 시간:0:00전체 재생 길이:5:22
0 에너지 포인트
동영상 대본
지금까지 내용을 되짚어보자면, Trial division 방법으로 어떤 수 N이 소수인지 아닌지를 검사하려고 합니다 N의 제곱근은 여기있습니다 3은 여기 있습니다 3에서부터 시작해서 N의 제곱근을 만날때까지 숫자를 두 개씩 뛰어넘어 셀 겁니다 그리고 각 지점에 있는 수가 N을 나누어떨어지게 하는지 확인할 겁니다 지금까지 사람들은 지나가야하는 단계의 수를 줄이려고 노력했습니다 큰 수 부터 시작하거나 마디의 간격을 늘리는 방식으로 말이죠 여기서 잠시 멈추고 Trial Division 알고리즘의 이상적인 경우에 대해 생각해볼까요? Trial Division 알고리즘의 이상적인 경우에 대해 생각해볼까요? 다른 창의적인 방법으로 간격을 세면 가장 효율적으로 목표를 달성할 수 있지 않을까요? N은 어떤 세 인수의 곱으로 이루어져 있습니다 N의 제곱근이 여기에 있다고 합시다 그리고 오직 소수만 세면서 건너갈 수만 있다면 그게 최선의 방법일 것입니다 왜냐하면 소수만 세면서 가면 결국 인수를 찾을 수 있기 때문입니다 합성수라면 소인수가 나오겠죠 문제는 이 방법이 얼마나 효율적이냐는 것이죠 왜냐하면 지금으로선 이 방법이 최고의 방법으로 보입니다 만약 체를 처음에 호출하는 어떤 새로운 알고리즘을 만들 때 이 새로운 알고리즘이 N이 소수인지 아닌지 검사한다고 해봅시다 이 알고리즘은 체를 호출하고 N의 제곱근보다 작은 소수로 이루어진 긴 목록을 생성하고 그 다음에 Trial Division을 합니다 이 때 위 목록의 소수값을 사용하여 소수만 짚으면서 넘어갑니다 어딘지는 모르겠지만 N의 제곱근까지 말이죠 무엇이 잘못되었을까요? 우리는 시간복잡성이나 계산하는데 걸린 단계 수를 눈에 보이게 표시 할 수 있습니다 예전에 제가 이야기했던 것을 기억하고 있나요? 예전에 이 알고리즘을 설명하면서 각 단계를 재는 스텝 카운터를 각 반복문 안에 넣었었지요 이제 단순히 step++라고 하면 step을 하나 증가시키는 것을 의미합니다 안쪽에 있는 다른 반복문에도 스탭 카운터가 있습니다 step++를 써줍니다 전부 IF 와 mark 여부를 확인하는 상수 연산입니다 방금 각 반복문안에 스텝 카운터가 있는 것을 확인했습니다 이제 여기서 비교를 할 겁니다 왼쪽은 우리가 예전에 사용하던 방식이고 중간은 체를 호출하는 알고리즘으로 N보다 작은 모든 소수 목록을 생성합니다 오른쪽 부분은 체를 호출하여 N의 제곱근까지의 소수들의 목록을 만들고 이 소수에 한해서 Trial Division을 호출하는 것입니다 그럼 작은 숫자를 넣었을 때 어떻게 되는지 볼까요? 첫 부분에서 보이는 것과 같이 체는 수를 아주 여러 번 셉니다 오른쪽에 수정한 버전도 사실은 Trial Division보다 느립니다 입력값이 커지게 되면 체에서 세는 마디의 수는 더욱 빠르게 증가합니다 일단 중간 부분을 제외하고 Trial Division만 쓰는 방식과 N의 제곱근까지 소수를 체로 거른 다음 Trial Division을 쓰는 방식을 비교해 봅시다 지금은 오래된 Trial Division 방식이 더욱 효율적인 것 처럼 보입니다 N의 제곱근까지 소수를 체를 사용해서 거른 다음 Trial Division을 사용하면 연산의 수는 훨씬 빠르게 증가합니다 실제로 개선된 점이 없다는 것이죠 아래 있는 프로그램은 제가 둘을 비교할 때 쓰려고 붙인겁니다 여기에 제가 어떠한 값을 설정했었는지 기록 해둔 것이 있습니다 그럼 여러분은 지금 이런 생각이 들 겁니다 "그 전에 소수를 계산해 놓으면 안되나요?" 첫 번째 단계로 우선 소수 배열을 하나 만들고 이를 하드 디스크 드라이브에 저장합니다 그 다음에 알고리즘은 Trial Division을 합니다 알고리즘은 여기서 소수만 짚고 넘어갈 수 있습니다 바로 소수의 목록에서 값을 읽기 때문이죠 소수 목록에 20 자릿수 소수를 모두 저장한다고 쳐봅시다 아니면 심지어 100 자릿수 까지 저장한다고 쳐봅시다 왜 이렇게 할 수 없을까요? 문제는 컴퓨터의 메모리가 한정되어 있다는 것입니다 특히 셀 수 없이 많은 수를 다룰 때에 말이죠 바로 다음에 배울 겁니다 단순히 예를 들어 다음과 같은 연산을 수작업으로 하고 있다고 칩시다 계산해서 5가 소수라고 판단하고 종이에 5를 써서 파일 보관함에 저장합니다 그 다음에는 7도 똑같은 방식으로 보관함에 저장합니다 9는 아니고요 11도 보관함에 저장합니다 그러면 보관함은 소수로 꽉 차게 될 것이고 이것을 소수가 들어있는 소수 배열이라고 생각할 수 있습니다 우리가 20 자릿수 아래 모든 소수나 100 자릿수 아래 모든 소수를 저장하기 위해서는 얼마나 큰 보관함이 필요할까요? 그 배열을 하드 드라이브에 저장할 수 있기는 할까요? 이것이 사실상 왜 불가능한지 이해하기 위해서는 이 소수 배열이 얼마나 커지는지에 대해서 조금 더 깊게 살펴보아야 합니다 그러면 그 크기의 제한이 현재의 컴퓨터에서는 어느 정도이며 나아가 미래의 컴퓨터 하드웨어는 어느 정도일까요?