15
http://cr.yp.to/primegen.html에는 Atkin의 체를 사용하여 소수를 생성하는 프로그램 소스를 찾을 수 있습니다. 저자가 보낸 이메일에 답변하는 데 몇 달이 걸릴 수도 있다고 말했듯이 (나는 분명히 그는 점령 된 사람입니다!) 나는이 질문을 게시하고 있습니다.D.J.의 10^15의 제한은 어디에서 있습니까? 번스타인의 'primegen'프로그램은 어디에서 왔습니까?
페이지에는 'primegen이 1000000000000000까지의 소수를 생성 할 수 있음'이라고 나와 있습니다. 왜 그런지 이해하려고 노력하고 있습니다. 물론 2^64 ~ 2 * 10^19 (long unsigned int 크기)의 제한이 있기 때문에 숫자가 표현되는 방식입니다. 나는 거대한 프라임 갭 (> 2^31)이 있다면 숫자 인쇄가 실패 할 것이라는 것을 확실히 알고 있습니다. 그러나이 범위에서 나는 그러한 주요한 격차가 없다고 생각한다.
저자가 바운드를 과대 평가했거나 (실제로는 약 10^19 정도) 소스 코드에서 산술 연산이 오버 플로우 할 수있는 위치 또는 그와 비슷한 위치에 있습니다.
재미있는 것은
당신이 실제로 번호> 10^15를 실행 할 수 있다는 것이다 :./primes 10000000000000000 10000000000000100
10000000000000061
10000000000000069
10000000000000079
10000000000000099
을하고 볼프람 알파를 믿는다면, 그것은 올바른 것입니다.
일부 사실 나는 "역 설계"했다 :
- 수는 1,920 * PRIMEGEN_WORDS = 3932160 개 번호 (primegen_next.c에서 primegen_fill 기능 참조)
- PRIMEGEN_WORDS 컨트롤 얼마나 큰 하나의 일괄 체질 선별은 - primegen_impl.h에서 CPU 캐시에 맞게 조정할 수 있습니다.
- 체 자체 구현은 primegen.c 파일에 있습니다. 올바른 것으로 가정합니다. 여러분이 얻는 것은 pg-> buf에있는 소수의 비트 마스크입니다 (primegen_fill 함수 참조).
- 비트 마스크가 분석되고 소수는 pg-> p 배열에 저장됩니다.
오버 플로우가 발생할 수있는 지점이 없습니다.
필자는 DJB가 sieving 소수 (따라서 32 비트 수)에 부호없는 정수를 사용한다고 가정하고 체에서 생성 된 소수 (따라서 64 비트 수)에 대해 부호없는 정수라고 가정하면 알고리즘의 한계 실제로 2^64입니다. DJB에 의한 코멘트는 그 범위에서의 체질이 엄청난 시간을 필요로하기 때문에 _practical_ 한도 일 수도 있습니다. – user448810