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