C#에서 소수를 계산하는 가장 빠른 방법은 무엇입니까?

StackOverflow https://stackoverflow.com/questions/30877

문제

실제로 내 질문에 대한 답변이 있지만 병렬화되지 않아 알고리즘을 개선할 수 있는 방법에 관심이 있습니다.어쨌든 어떤 사람들에게는 있는 그대로 유용할 수도 있습니다.

int Until = 20000000;
BitArray PrimeBits = new BitArray(Until, true);

/*
 * Sieve of Eratosthenes
 * PrimeBits is a simple BitArray where all bit is an integer
 * and we mark composite numbers as false
 */

PrimeBits.Set(0, false); // You don't actually need this, just
PrimeBits.Set(1, false); // remindig you that 2 is the smallest prime

for (int P = 2; P < (int)Math.Sqrt(Until) + 1; P++)
    if (PrimeBits.Get(P))
        // These are going to be the multiples of P if it is a prime
        for (int PMultiply = P * 2; PMultiply < Until; PMultiply += P)
            PrimeBits.Set(PMultiply, false);

// We use this to store the actual prime numbers
List<int> Primes = new List<int>();

for (int i = 2; i < Until; i++)
    if (PrimeBits.Get(i))
        Primes.Add(i);

어쩌면 여러 개를 사용할 수도 있을 것 같아요 BitArray모래 BitArray.And() 같이?

도움이 되었습니까?

해결책

이중 연결 목록으로 비트 배열을 교차 참조하여 시간을 절약 할 수 있으므로 다음 프라임으로 더 빠르게 발전 할 수 있습니다.

또한, 처음으로 새로운 Prime P를 쳤을 때 나중에 복합재를 제거 할 때 - 나머지 P의 첫 번째 복합물 다중은 이미 제거 되었기 때문에 P*P가됩니다. 실제로, 당신은 목록에 남은 나머지의 모든 잠재적 프라임에 p에 p에 곱하면 제품이 범위를 벗어나 자마자 중지됩니다.

Miller-Rabin 테스트와 같은 좋은 확률 적 알고리즘도 있습니다. Wikipedia 페이지 좋은 소개입니다.

다른 팁

병렬화를 제외하고 매 반복마다 sqrt(Until)을 계산하고 싶지는 않습니다.또한 2, 3, 5의 배수를 가정하고 {1,5}의 N%6 또는 {1,7,11,13,17,19,23,29}의 N%30에 대해서만 계산할 수 있습니다.

N번째 단계는 sqrt(n)번째 결과에만 의존하므로 잠시 후에 충돌이 발생하지 않으므로 인수분해 알고리즘을 매우 쉽게 병렬화할 수 있습니다.하지만 이는 많은 분할이 필요하기 때문에 좋은 알고리즘이 아닙니다.

읽기 전에 완료가 보장되는 작성자 작업 패킷이 있는 경우 시브(sieve) 알고리즘을 병렬화할 수도 있어야 합니다.대부분 작성자는 독자와 충돌해서는 안 됩니다. 최소한 몇 가지 항목을 수행한 후에는 리더보다 최소한 N 이상 작업해야 하므로 아주 가끔씩만 동기화 읽기가 필요합니다(N이 마지막 동기화 읽기를 초과하는 경우). 값).쓰기 충돌이 발생하지 않으므로 여러 쓰기 스레드에서 bool 배열을 동기화할 필요가 없습니다(최악의 경우 둘 이상의 스레드가 동일한 위치에 true를 씁니다).

주요 문제는 쓰기를 기다리고 있는 모든 작업자가 완료되었는지 확인하는 것입니다.C++에서는 비교 및 ​​설정을 사용하여 언제든지 기다리고 있는 작업자로 전환합니다.저는 C# 전문가가 아니기 때문에 해당 언어를 수행하는 방법을 모르지만 Win32 InterlockedCompareExchange 기능을 사용할 수 있습니다.

또한 액터 기반 접근 방식을 시도해 볼 수도 있습니다. 이렇게 하면 액터가 가장 낮은 값으로 작업하도록 예약할 수 있기 때문에 각 증분마다 버스를 잠그지 않고도 체의 유효한 부분을 읽는다는 것을 더 쉽게 보장할 수 있습니다. N.

어느 쪽이든 읽기 전에 모든 작업자가 항목 N 이상을 얻었는지 확인해야 하며, 이를 수행하는 데 드는 비용은 병렬과 직렬 간의 균형이 이루어지는 곳입니다.

프로파일 링하지 않으면 프로그램의 비트가 어떤 최적화가 필요한지 알 수 없습니다.

큰 시스템에 있었다면 프로파일 러를 사용하여 소수 생성기가 최적화가 필요한 부분임을 알게됩니다.

수십 정도 정도의 지침으로 루프를 프로파일 링하는 것은 일반적으로 가치가 없습니다. 프로파일 러의 오버 헤드는 루프 본체에 비해 중요하며, 작은 반복을 더 적은 반복을 수행하도록 알고리즘을 변경하는 유일한 방법은 알고리즘을 개선하는 유일한 방법입니다. . 따라서 IME, 고가의 기능을 제거하고 간단한 코드의 몇 줄에 알려진 대상을 가지고 있다면, 알고리즘을 변경하고 명령어 수준별로 코드를 개선하는 것보다 엔드 투 엔드 실행 타이밍이 더 좋습니다. 프로파일 링.

@DrPizza 프로파일링은 구현을 개선하는 데 실제로 도움이 될 뿐이며 병렬 실행 기회를 공개하거나 더 나은 알고리즘을 제안하지 않습니다(다른 경험이 없는 한, 이 경우 프로파일러를 꼭 보고 싶습니다).

저는 집에 단일 코어 머신만 가지고 있지만 BitArray 체와 동등한 Java와 체 반전의 단일 스레드 버전을 실행했습니다. 배열에 마킹 프라임을 유지하고 바퀴 검색 공간을 5배로 줄인 다음 각 마킹 프라임을 사용하여 휠 증분으로 비트 배열을 표시합니다.또한 스토리지를 O(N) 대신 O(sqrt(N))로 줄여 최대 N, 페이징 및 대역폭 측면에서 모두 도움이 됩니다.

중간 값 N(1e8 ~ 1e12)의 경우 sqrt(N)까지의 소수를 매우 빠르게 찾을 수 있으며 그 후에는 CPU에서 후속 검색을 매우 쉽게 병렬화할 수 있습니다.내 단일 코어 컴퓨터에서 휠 접근 방식은 28초에 최대 1e9의 소수를 찾는 반면, 시브(sqrt를 루프 밖으로 이동한 후)는 86초가 걸립니다. 개선은 휠 때문입니다.반전은 2^32보다 큰 N을 처리할 수 있지만 속도가 느려진다는 것을 의미합니다.코드를 찾을 수 있습니다 여기.sqrt(N)을 지나간 후에도 순진한 체의 결과 출력을 병렬화할 수 있습니다. 해당 지점 이후에는 비트 배열이 수정되지 않기 때문입니다.그러나 일단 N이 문제가 될 만큼 큰 경우 배열 크기가 int에 비해 너무 큽니다.

또한 가능한 변화를 고려해야합니다 알고리즘.

찾은 것처럼 요소를 목록에 추가하는 것이 더 저렴할 수 있습니다.

아마도 당신의 목록을위한 preallocating space는 아마도 구축/채우기가 더 저렴하게 만들 것입니다.

새로운 프라임을 찾으려고합니까? 이것은 어리석게 들릴지 모르지만 알려진 프라임으로 일종의 데이터 구조를로드 할 수 있습니다. 나는 누군가가 목록이 있다고 확신합니다. 새로운 숫자를 계산하는 기존 숫자를 찾는 것이 훨씬 쉬운 문제 일 수 있습니다.

마이크로 소프트를 볼 수도 있습니다 병렬 FX 라이브러리 기존 코드를 멀티 코어 시스템을 활용하기 위해 멀티 스레드를 만들었습니다. 최소한의 코드 변경으로 루프가 멀티 스레드로 만들 수 있습니다.

에라토스테네스의 체에 관한 아주 좋은 기사가 있습니다: 에라토스테네스의 진짜 체

이는 기능적 설정에 있지만 대부분의 최적화는 C#의 절차적 구현에도 적용됩니다.

가장 중요한 두 가지 최적화는 2*P 대신 P^2에서 지우기 시작하고 다음 소수에 휠을 사용하는 것입니다.

동시성을 위해 불필요한 작업을 수행하지 않고 P^2까지의 모든 숫자를 P와 병렬로 처리할 수 있습니다.

    void PrimeNumber(long number)
    {
        bool IsprimeNumber = true;
        long  value = Convert.ToInt32(Math.Sqrt(number));
        if (number % 2 == 0)
        {
            IsprimeNumber = false;
            MessageBox.Show("No It is not a Prime NUmber");
            return;
        }
        for (long i = 3; i <= value; i=i+2)
        {             
           if (number % i == 0)
            {

                MessageBox.Show("It is divisible by" + i);
                IsprimeNumber = false;
                break;
            }

        }
        if (IsprimeNumber)
        {
            MessageBox.Show("Yes Prime NUmber");
        }
        else
        {
            MessageBox.Show("No It is not a Prime NUmber");
        }
    }
라이센스 : CC-BY-SA ~와 함께 속성
제휴하지 않습니다 StackOverflow
scroll top