에라 토 스테 네스 체가 구현되어 상한선 (분열 된 체)없이 연속적으로 소수를 찾을 수 있다는 사실을 알고 있습니다.Atkin의 분단 체, 가능?
제 질문은 Atkin/Bernstein의 체를 같은 방식으로 구현할 수 있습니까?
관련 질문 : C#: How to make Sieve of Atkin incremental
관련 질문은 분명 잘못된 것입니다, "그것은 모든 체에 대한 불가능하다"라는 단 한 대답을 가지고 그러나.
Atkin/Bernstein은 (는) original paper 섹션 5에서 세그먼트 버전을 제공합니다. 아마도 번스타인의 primegen 프로그램은 그 방법을 사용합니다.
감사합니다. 원본 종이를 끝까지 읽지 않아서 굴욕에 빠져 있습니다. –
Atkin과 Bernstein이 C 소스 코드에서 다루지 만 자신의 논문에서 언급하지 않은 것은 큰 범위에 필요한 페이지 분할을 사용하여 Sieve of Atkin의 효율성을 유지하는 데 극도의 어려움이 있습니다. 1) 한 페이지보다 훨씬 더 크고, 이들을 처리하는 데있어 복잡성 (그리고 비효율적 인 요소)이 요구되며, 2) 'x'및 'y'변수 각각에 대해 새로운 페이지 시작점을 계산하는 데 점점 많은 시간이 소요됩니다. 범위가 증가하는 2 차 솔루션이므로 O (n) 상대적 성능은 결코 발생하지 않습니다. – GordonBGood
실제로 내가 수행 한 것처럼 세그먼트 화를 전혀 사용하지 않는 무한대의 Atkin (SoA) 체를 구현할 수 있습니다. here in F#. 이것은 2 차 방정식의 솔루션과 squaresfree 필터를 결합하기 위해 배열을 사용하지 않는 순수 함수 버전이므로 더 긴급한 접근 방식보다 상당히 느립니다.
최적의 32 비트 범위를위한 룩업 테이블을 사용하는 Berstein의 최적화는 코드를 극도로 복잡하게 만들어 프리젠 테이션에 적합하지 않지만 시퀀스가 설정된 최소 한도에서 시작되도록 내 F # 코드를 적용하는 것은 매우 쉽습니다 세그먼트 화 된 버전을 구현하거나 배열을 사용하는보다 긴급한 접근법에 동일한 기술을 적용하기 위해 범위에서만 사용됩니다. SOA는 심지어 Berstein의 구현은 정말 빨리 에라토스테네스의 체보다는 가능한 모든 최적화와 Kim Walisch's primesieve에 따라이 아니라 숫자의 선택 범위 에라토스테네스의 체의 빠른 보다 동등 최적화 된 버전입니다
주 그의 구현에 따라.
EDIT_ADD : HIGH 곳으로 LOW의 범위에 걸쳐 SOA를 사용하는 의사 코드 방법을 추가, 나는이 답변에 추가하고 Berstein의 의사 코드와 C 코드를 통해 웨이드하지 않으려는 사람들을 위해 LOW에서 HIGH + 1 로의 델타는 모듈로 (및 2,3,5 휠상의 엔트리에만 포텐셜 비트 패킹) 최적화를 사용하기 위해 모듈로 60으로 제한 될 수있다.
이것은 (4 * x^2 + y^2), (3 * x^2 + y^2) 및 (3 * x^2 -y^2)의 SoA 2 차 방정식)는 1과 SQRT ((HIGH - 1)/4), SQRT ((HIGH - 1)/3) 사이의 값으로 고정 된 각 시퀀스의 x 값을 갖는 숫자의 시퀀스로 표현되고 2 * x = (SQRT (1 + 2 * (HIGH + 1)) - 1)/2에 대해 각각 x = 2 + 2 * x - HIGH - 1 = 0이며, 맨 위 링크 당 내 F # . 시퀀스에 대한 최적화는 "4x"시퀀스에 대해 홀수 복합물 만 체질 할 때 y 값은 홀수 일 필요가 있고 "3x"시퀀스는 x가 짝수 일 때 홀수 값을 사용할 필요가 있고 그 반대의 경우도 사용하는 것이 좋습니다. 추가 최적화는 위의 시퀀스에 대한 모듈러스 패턴이 매우 작은 범위의 x에서 반복되고 또한 y의 범위가 30에서 반복되는 것을 관찰하여 이차 방정식 (= 시퀀스의 요소)에 대한 솔루션 수를 줄입니다. Berstein 코드지만 (아직) 내 F # 코드에서 구현되지 않습니다.
휠 분해 및 시작 세그먼트 주소에 대한 계산을 my implementations of a segmented SoE에서 사용하는 것처럼 소수 "제곱 자유"컬링에 적용 할 수있는 잘 알려진 최적화는 포함하지 않았습니다.
따라서 "4x", "3x +"및 "3x-"(또는 F # 코드에서와 같이 "3x +"및 "3x-"결합 된) 세그먼트 시작 주소를 계산할 때, - FIRST_ELEMENT 각각 소정 값 (Y)의 최저 해당 값이다 FIRST_ELEMENT,
의 범위 LOW 계산 다음과 같이 상기 따라 각각의 x의 범위를 계산하는 데, 상기 의사 코드는 "3x-"시퀀스의 경우 x 또는 y = x - 1입니다.
얼마나 많은 요소가이 범위에 있는지 계산할 때, 이것은 (y1)^2 + (y2)^2 + (y3)^2 중 몇 개가 ... 각각의 y 번호는 2로 분리되어 필요에 따라 짝수 또는 홀수의 y를 생성합니다. 델타 (9-1)가 8 일 때, 델타 (25-9)가 8 증가 할 때 16, 델타 (49-25)가 16 일 때, 사각 시퀀스 분석에서 평소와 같이, 8의 추가 증가를 위해 24 등. n 요소의 경우 마지막 증가분은이 예제의 경우 8 * n입니다. 이것을 사용하여 요소 시퀀스를 표현하면, (1 + 2 + 3 + ... + n)과 같은 시퀀스의 8 배에 8을 곱한 값이됩니다. 이제이 합계가 (n + 1) * n/2 또는 n^2/2 + n/2 인 경우 선형 순서의 표준 감소가 적용됩니다. 2 차 방정식 n/2 + n/2 - range = 0 또는 n = (SQRT (8 * range + 1) - 1)/2를 풀면 범위에 n 개의 원소가 몇 개 있는지를 풀 수 있습니다.
이제 FIRST_ELEMENT + 4 * (n + 1) * n이 시작 주소로 LOW와 같지 않으면 n에 1을 더하고 FIRST_ELEMENT + 4 * (n + 2) * (n + 1)을 시작 주소. 시퀀스 패턴에 휠 분해 인수를 적용하기 위해 추가 최적화를 사용하는 경우, 룩업 테이블 배열을 사용하여 조건을 만족하는 사용 된 n의 가장 가까운 값을 검색 할 수 있습니다.
시작 요소의 모듈러스 12 또는 60은 직접 계산할 수 있거나 모듈로 시퀀스의 반복적 인 특성에 기반한 룩업 테이블을 사용하여 생성 할 수 있습니다.
각 시퀀스는 복합 상태를 HIGH 한계까지 토글하는 데 사용됩니다. 추가 로직을 시퀀스에 추가하여 시퀀스 당 적용 가능한 요소 사이에서만 값을 점프하면 모듈로 조건을 더 이상 사용할 필요가 없습니다.
"3x +"및 "3x-"시퀀스가 뒤 따르는 모든 "4x"시퀀스 (위의 내용은 "3x +"및 "3x-"를 "3x"시퀀스의 한 세트로 결합 함) 이전에 계산되거나 루프마다 테스트 된대로 x 제한값.
그리고 거기가있다 : 가장 최선의 메모리 액세스 효율을위한 CPU의 캐시 크기와 관련된 고정 된 크기로 사용되는 세그먼트들로 자체의 범위를 분할하는 적절한 방법에있어서, 분할 방법 주어진 번스타인에 의해 사용되었지만 식으로 다소 단순한 SoA는 언급하지만 모듈 연산과 비트 패킹을 결합하지는 않습니다.
나는 Atkin/Bernstein 체를 수년간 공부했는데 그것을 어떻게 분할 할지를 결코 결정하지 못했다. 나는 누군가가 있는지 볼 흥미가있을 것입니다. – librik