시간과 공간의 관계

새로운 업데이트가 있어요 나사의 엔지니어링 부서와 연락을 했습니다 그리고 새로운 탐사선이 큐리오시티와 동일한 저장방법을 사용한다고 합니다 큐리오시티는 두 개의 컴퓨터를 탑재하고 있는데 그 시점엔 오직 한개만 작동되고 있었고 다음의 스펙을 가지고 있었습니다 플래시메모리 2기가바이트와 256 메가바이트의 랜덤 엑세스 메모리 중요 시스템 루틴을 가지고 있는 256 키로바이트의 읽기전용메모리 입니다 우리는 RAM 메모리에 전체 프로그램을 저장할 수 있기를 바라는데 이 공간을 다른 프로그램과 공유해야 하므로 우리가 사용할 수 있는 최대용량엔 5%의 RAM 메모리를 할당합니다 이것은 총 12.8 메가바이트 정도입니다 저는 시간 공간 또는 공간 시간 트레이드오프라는 것을 소개하기 위해 이 주제를 가져왔습니다 이것은 컴퓨터 과학에서 많이 쓰는 용어이지요 IV46에 의해 만들어진 프로그램을 보고 있었는데 만개의 소수 배열이 있었습니다 소수판별법 테스트를 할 때 알고리즘이 소수를 제외한 수를 건너뛸 수 있도록 하기 위해서요 왜 소수숫자들을 계산하는 대신에 배열에 우리가 필요한 모든 소수를 가능한 만큼 저장하지 않는지 의문이 듭니다 이것이 나누기 알고리즘에서는 최적이라고 앞 비디오에서 언급했었죠 이 알고리즘에 단계가 많지는 않아도 매우 느리게 계산됩니다 마지막에는 제한된 단계에 이르기 전에 끝나게 됩니다 그래서 제가 이전에 정의했던 크기의 문제는 빠르게 풀 수가 없었습니다 이럴 경우에는 배열을 저장하고있는 메모리인 공간을 비용으로 반복되는 가분성 실험 형태의 시간을 벌수 있습니다 그런데 왜 이것이 성공적이지 못했을까요? 우리가 배운 것을 이용하여 이 방법이 메모리 한계안에 있는지 알아보는 간단한 계산을 해봅시다 기억하세요 우리는 9000조 이상의 숫자를 다룰 수 있어야 합니다 우리가 사용하는 나누기 알고리즘은 오직 숫자의 제곱근까지의 인수만 확인합니다 인수가 없을 시점에 100%의 확률로 소수인지 아닌지 알수 있습니다 이제, 9000조의 제곱근이 9천4백 9십만일 때 제곱근에 이르는 소수가 몇 개 있을까요? 9천 5백만 아래로 몇 개의 소수가 있을까요? 다행히도 소수정리 이론을 통해 이 답을 어림잡는 수학적 방법을 배웠죠 그럼 x 밑에는 몇 개의 소수가 있을까요? 답은 x나누기 x의 자연로그 입니다 x가 9천 4백 9십만을 막 넘을 때 소수의 개수가 약 5.1백만인 것을 알 수 있습니다 우리는 이 소수들을 저장하려고 하기 때문에 가장 큰 소수의 사이즈를 알아야 합니다 또는 이 경우 9천4백 9십만보다 작은 숫자인 5.1백만째 소수를 알아야 합니다 이제 표를 재검토합니다 우리가 한계값의 제곱근 밑으로 저장할 수 있는 가장 큰 소수인 이 수의 값은 89,078,611 입니다 이제 이 큰 소수에는 얼마의 메모리가 필요할까요? 답을 찾기 위해서 이 숫자를 메모리에서 저장하기 위해서 사용되는 숫자인 이진수로 바꿔봅시다 이진법에 대해서는 컴퓨터 메모리 영상에서 배웠습니다 비트에서는 가장 큰 소수가 이런 모습입니다 이 숫자 하나를 저장하는데 필요한 공간은 24bit 또는 3byte이죠 그럼 이제 메모리에 각각의 숫자를 저장하고자 합니다 가장 큰 숫자는 24비트라는 것을 알고있으므로 각 소수를 저장할 24비트 블럭의 긴 리스트를 상상해 볼 수 있습니다 전체 리스트를 위해서 몇 비트가 필요할까요? 필요한 메모리는 값의 수이거나 각 공간에 대한 값 곱하기 소수의 수입니다 값이 5.1백만 곱하기 24비트이므로 1억2천4백만 비트 또는 바이트로 바꾸면 약 1천4백7십만 바이트 입니다 거의 15메가바이트가 됩니다 그렇니 우리의 한계치를 사용하면 이 숫자들의 리스트조차 저장하기가 불가능합니다 이것은 장난감같은 예에 불과합니다 이것은 사실 필요한 것의 과소평가치입니다 예를 들어 배열은 각 아이템에 포인터가 있을 공간이 필요합니다 그리고 32비트 기계의 각 포인터는 4바이트입니다 그러니 실제로 필요한 메모리의 양은 15메가바이트보다 훨씬 더 많죠 우리의 비교적 작은 수의 제곱근 까지의 소수를 모두 저장하려면 우리의 메모리 한계로는 가능하지 않습니다 이런 방식으로는 할 수 없죠 좋아요 그렇다면 천 또는 만의 요소로 값을 떨어트리면 어떨까요? 요즘 암호시스템은 512비트를 사용하거나 탐사나 셈이 불가능한 정도의 더 큰 수를 사용합니다 예를 들어 누군가 여러분에게 200자리까지의 모든 소수의 리스트를 만들어달라고 한다면 생각조차 할 수 없을 겁니다 이 모든 소수를 저장하기 위한 하드 드라이브가 식별할 수 있는 우주보다 더 무거울 지도 모르죠 이 계산은 다음번에 식당에서 크레용과 종이를 가지고 해보도록 남겨두겠습니다 하지만 기억하세요 대략 10의 80제곱개의 원자가 관측 가능한 우주에 존재합니다 약 80자리수의 숫자이죠 우리가 접근할수 있는 메모리와 공간의 수에는 근본적인 제한이 있습니다 시간이 얼마나 걸릴 지는 신경쓰지 마세요 그러나 문제를 풀기 위해 공간과 시간을 사용하는 데에는 항상 밀고 당김이 있습니다 그러니 작은공간을 사용하고 적은 시간을 사용하여 이 소수판펼법 문제를 빨리 풀기 위해서는 우리는 이 문제에 완전히 새로운 방법으로 접근을 해야 합니다