C에서 시브의 방법을 사용하여 최대 20 억의 소수점 표시하기

시브 에라 토 스테 네스 (Sieve Eratosthenes) 방법을 사용하여 최대 20 억 개의 소수를 나열하려고했습니다. 여기 내가 사용한 것입니다!C에서 시브의 방법을 사용하여 최대 20 억의 소수점 표시하기

내가 직면 한 문제는 1,000 만 개가 넘을 수 없다는 것입니다. 내가 시도했을 때, 그것은 'Segmentation Fault'라고 말한다. 나는 그 원인을 찾기 위해 인터넷에서 수색했다. 일부 사이트에서는 컴파일러 자체의 메모리 할당 제한이 있다고합니다. 어떤 이는 하드웨어 제한 사항이라고 말합니다. 4GB RAM이 설치된 64 비트 프로세서를 사용하고 있습니다. 제발 그들을 나열하는 방법을 제안하십시오.

#include <stdio.h> 
#include <stdlib.h> 

#define MAX 1000000 
long int mark[MAX] = {0}; 

int isone(){ 
    long int i; 
    long int cnt = 0; 
    for(i = 0; i < MAX ; i++){ 
     if(mark[i] == 1) 
     cnt++; 
    } 
    if(cnt == MAX) 
     return 1; 
    else 
     return 0; 
} 



int main(int argc,char* argv[]){ 
    long int list[MAX]; 
    long int s = 2; 
    long int i; 
    for(i = 0 ; i < MAX ; i++){ 
     list[i] = s; 
     s++; 
    } 
    s = 2; 
    printf("\n"); 

    while(isone() == 0){ 
     for(i = 0 ; i < MAX ; i++){ 
     if((list[i] % s) == 0) 
      mark[i] = 1; 
     } 
     printf(" %lu ",s); 
     while(mark[++s - 2] != 0); 
    } 

    return 1; 
}

출처

2013-01-08 Krishna

'gdb'를 사용해보세요. 유용한 도구입니다. – banuj

기본적으로 'long int mark [2e9]'로 16GB의 메모리를 요구하고 있다는 것을 알고 있습니까? –

당신은 16 기가 바이트의 메모리를 얻지 않을 것입니다, 특히 스택에는 없습니다. –

long int mark[1000000] 메모리 할당량을 원하지 않습니다. 대신 힙 메모리를 할당하려면 long int *mark = malloc(sizeof(long int) * 1000000)을 시도하십시오. 이것은 배열 요소의 ~ 1mil을 초과하게합니다.

더 이상 사용하지 않는 경우 메모리가 free 인 것을 기억하십시오. yon이 malloc이나 free를 모르는 경우, 모든 리눅스 터미널에서 man 3 malloc과 man 3 free을 통해 제공되는 기능에 대한 맨 페이지 (매뉴얼)를 읽으십시오. (또는 man malloc)

편집 : calloc(1000000, sizeof(long int))에 0으로 초기화 된 배열을 사용하는 것이 좋습니다.

또한 배열의 모든 요소를 비트 마스크로 사용하여 sizeof (long int) 바이트가 아닌 비트 당 하나의 표시를 저장할 수 있습니다. 배열 요소에 대해 uint32_t과 같은 고정 너비 정수형을 사용하고 n 번째 요소를 1로 설정하는 대신 배열의 (n/32) 번째 요소에있는 (n % 32) 번째 비트를 1로 설정하는 것이 좋습니다.

당신은 사용하여 정수 i의 n 번째 비트를 설정할 수 있습니다

uint32_t i = 0; 
i |= ((uint32_t) 1) << n

을 당신이 번호의 uint32_t 비트 마스크 배열에 설정 작업을하게 0

N에서 계산을 시작 가정 :

mask[n/32] |= ((uint32_t)1) << (n % 32)

32 비트 유형에 대해 99 % 이상의 메모리를 절약합니다. 재밌게 지내라 : D

또 다른 진보 된 접근법은 프라임 휠 분해 (prime wheel factorization)이다. 기본적으로 당신이 2,3 등분을 미리 정한 후 소수점 이하를 선언하고 나눌 수없는 숫자만을 사용한다는 것을 의미한다. 이 중 하나를 마스크 배열에 넣으십시오. 그러나 그것은 정말로 진보 된 개념입니다.

출처

2013-01-08 09:21:59

+1, 특히 비트 마스크 제안입니다. 이렇게하면 16GB 상자에 최대 1000 억을 생성 할 수 있습니다. – mvp

더 복잡한 비트 마스크 접근법이 없어도 할당 된 메모리는'long int * 대신'char * mark'를 사용하여 1/8로 줄일 수 있습니다. 실제 숫자가 아니라 '0'또는 '1'표시 만 있기 때문에 'mark'로 표시됩니다. –

가장 즉각적인에게)

그러나, 나는 (또한 오일러 프로젝트에 대한) 코드에 대한 ~ 15 라인 C에서 2와 3에 대한 primesieve 느릅 나무 바퀴 인수 분해를 작성했습니다 때문에 효율적으로이 물건을 구현하는 것이 가능하다 개선은 홀수를 나타내는 비트로 전환하는 것입니다. 따라서 M= 억 개의 숫자 또는 10 억 개의 확률을 다루려면 1000/8 = 1 억 2,500 만 바이트 = ~ 120MB의 메모리가 필요합니다 (힙에는 여전히 calloc 함수로 할당하십시오).

위치 i의 비트는 2*i+1을 나타냅니다. 따라서 프라임의 배수를 표시 할 때 p, 즉p^2, p^2+2p, ..., M 우리 위치 j=(p^2-1)/2=2i(i+1)에서 비트로 표현 p^2=(2i+1)^2=4i^2+4i+1 및 p=2i+1 위치 단위로 위 p의 다음 배수

for(i=1; ; ++i) 
    if(bit_not_set(i)) 
    { 
     p=i+i+1; 
     k=(p-1)*(i+1); 
     if(k > 1000000000) break; 
     for(; k<1000000000; k+=p) 
     set_bit(k); // mark as composite 
    } 
// all bits i>0 where bit_not_set(i) holds, 
// represent prime numbers 2i+1

다음 단계에 맞는 작은 세그먼트에서 작업으로 전환하는 것을 캐시 크기 이렇게하면 속도가 빨라집니다. 소수의 제곱근 (즉, 44721)에서 메모리 영역을 예약하기 만하면됩니다.

먼저이 작은 영역을 체로 쳐서 소수를 찾습니다. 이 소수를 별도의 int 배열에 씁니다. 이 소수의 배열을 사용하여 각 세그먼트를 체로 치고 발견 된 소수를 stdout 또는 그 밖의 것으로 인쇄하십시오.

출처

2013-01-08 11:01:47 arrrghidian

세분화로 인해 작업 속도가 빨라질 수 있습니까? 벤치마킹이나 비슷한 것을 실행 했습니까? 나는 생각을 좋아하고, 어떤 숫자를 보니 좋을 것이다. :) –

@AndreasGrapentin 아니, 나는 그것을 시도하지 않았다. 그것은 받아 들여지는 지혜 AFAIK입니다. – arrrghidian

예, 세그먼트가 제대로 완료되면 작업 속도가 빨라집니다. 트릭은 캐시 메모리에 맞는 세그먼트 크기를 설정하는 것입니다. 에라토스테네스의 분열 된 체에 대한 설명은 http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes에서 내 응답을 참조하십시오. – user448810

C에서 시브의 방법을 사용하여 최대 20 억의 소수점 표시하기

답변

관련 문제