सी # में प्राइम की गणना करने का सबसे तेज़ तरीका?

Question

मुझे वास्तव में मेरे प्रश्न का उत्तर है लेकिन यह समांतर नहीं है इसलिए मुझे एल्गोरिदम सुधारने के तरीकों में रूचि है। वैसे भी यह कुछ लोगों के लिए उपयोगी हो सकता है।

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() एक साथ?

Answer 1

आप अपनी बिट सरणी को दोहरी-लिंक्ड सूची के साथ क्रॉस-रेफरेंस करके कुछ समय बचा सकते हैं, ताकि आप अगले प्राइम पर अधिक तेज़ी से आगे बढ़ सकें।

इसके अलावा, बाद में कंपोजिट को समाप्त करने के बाद पहली बार एक नया प्राइम पी मारा जाता है - शेष पी के पहले समग्र एकाधिक पी * पी होंगे, क्योंकि इससे पहले कि सब कुछ पहले से ही समाप्त हो चुका है। असल में, आपको केवल शेष शेष संभावित प्राइम्स द्वारा पी को गुणा करने की आवश्यकता है जो सूची में इसके बाद छोड़ी जाती है, जैसे ही आपका उत्पाद रेंज से बाहर हो जाता है (जब तक बड़ा हो)।

मिलर-राबिन परीक्षण जैसे कुछ अच्छे संभाव्य एल्गोरिदम भी हैं। The wikipedia page एक अच्छा परिचय है।

Answer 2

समानांतरता, आप प्रत्येक पुनरावृत्ति पर sqrt (जब तक) की गणना नहीं करना चाहते हैं। आप 2, 3 और 5 के गुणक भी मान सकते हैं और केवल {1,5} या एन% 30 में {1,7,11,13,17,19,23,29} में एन% 6 की गणना कर सकते हैं।

आपको फैक्टरिंग एल्गोरिदम को आसानी से समानांतर करने में सक्षम होना चाहिए, क्योंकि एनएच चरण केवल वर्ग (एन) वें परिणाम पर निर्भर करता है, इसलिए थोड़ी देर के बाद कोई संघर्ष नहीं होगा। लेकिन यह एक अच्छा एल्गोरिदम नहीं है, क्योंकि इसमें बहुत सारे विभाजन की आवश्यकता है।

यदि आपके पास लेखक कार्य पैकेट हैं जो पढ़ने से पहले पूरा होने की गारंटी है, तो आपको भी चलनी एल्गोरिदम समानांतर करने में सक्षम होना चाहिए। अधिकतर लेखकों को पाठक के साथ संघर्ष नहीं करना चाहिए - कम से कम एक बार जब आप कुछ प्रविष्टियां कर लेते हैं, तो उन्हें कम से कम एन पाठक के ऊपर काम करना चाहिए, इसलिए आपको केवल कभी-कभी सिंक्रनाइज़ पढ़ने की ज़रूरत होती है (जब एन अंतिम सिंक्रनाइज़ किए गए पढ़ने से अधिक हो जाता है मूल्य)। आपको किसी भी लेखक धागे में बूल सरणी को सिंक्रनाइज़ करने की आवश्यकता नहीं है, क्योंकि लिखने के संघर्ष उत्पन्न नहीं होते हैं (सबसे खराब, एक से अधिक धागे एक ही स्थान पर एक सत्य लिखेंगे)।

मुख्य मुद्दा यह सुनिश्चित करना होगा कि किसी भी कार्यकर्ता को लिखने की प्रतीक्षा की जा रही है। सी ++ में आप उस कार्यकर्ता को स्विच करने के लिए एक तुलना-और-सेट का उपयोग करेंगे जिसका किसी भी बिंदु पर इंतजार किया जा रहा है। मैं सी # जीता नहीं हूं इसलिए यह नहीं जानता कि यह भाषा कैसे करें, लेकिन Win32 InterlockedCompareExchange फ़ंक्शन उपलब्ध होना चाहिए।

आप अभिनेता आधारित दृष्टिकोण भी आजमा सकते हैं, इस तरह से आप निम्नतम मूल्यों के साथ काम करने वाले कलाकारों को शेड्यूल कर सकते हैं, जो गारंटी देना आसान हो सकता है कि आप बस को लॉक किए बिना चाकू के वैध हिस्सों को पढ़ रहे हैं एन

किसी भी तरह से, आपको यह सुनिश्चित करना होगा कि सभी श्रमिक इसे पढ़ने से पहले ए एन से ऊपर हो गए हैं, और ऐसा करने की लागत है जहां समांतर और धारावाहिक के बीच व्यापार-बंद किया जाता है।

Answer 3

@DrPizza प्रोफाइलिंग केवल वास्तव में कार्यान्वयन में सुधार करने में मदद करता है, यह समानांतर निष्पादन के अवसरों को प्रकट नहीं करता है, या बेहतर एल्गोरिदम का सुझाव नहीं देता है (जब तक कि आप अन्यथा अनुभव नहीं करते हैं, इस मामले में मैं वास्तव में आपके प्रोफाइलर को देखना चाहता हूं)।

मेरे पास घर पर केवल एक ही कोर मशीन है, लेकिन आपके बिटरएरे चलनी के जावा समकक्ष, और चाकू के उलटा होने का एक थ्रेड संस्करण - एक सरणी में अंकन प्राइम रखने और wheel का उपयोग करके कम करने के लिए पांच के कारक द्वारा खोज स्थान, फिर प्रत्येक अंकन प्राइम का उपयोग करके पहिया की वृद्धि में थोड़ा सरणी चिह्नित करना। यह ओ (एन) के बजाय ओ (वर्ग (एन)) में भंडारण को भी कम करता है, जो सबसे बड़ी एन, पेजिंग और बैंडविड्थ के मामले में दोनों की सहायता करता है।

एन (1e8 से 1e12) के मध्यम मानों के लिए, sqrt (एन) तक की कीमतें बहुत जल्दी मिल सकती हैं, और इसके बाद आप सीपीयू पर बाद में खोज को आसानी से समानांतर करने में सक्षम होना चाहिए। मेरी एकल कोर मशीन पर, पहिया दृष्टिकोण 28s में 1e9 तक प्राइम पाता है, जबकि आपकी चलनी (लूप से बाहर निकलने के बाद) 86 लेती है - सुधार चक्र के कारण होता है; उलटा मतलब है कि आप 2^32 से बड़े एन को संभाल सकते हैं लेकिन इसे धीमा कर देता है। कोड here पाया जा सकता है। पिछले sqrt (एन) के बाद भी आप बेवकूफ चलनी से परिणामों के आउटपुट को समानांतर बना सकते हैं, क्योंकि उस बिंदु के बाद बिट सरणी संशोधित नहीं होती है; लेकिन एक बार जब आप एन के साथ पर्याप्त रूप से काम कर रहे हैं तो सरणी के आकार के लिए सरणी के आकार के लिए बहुत बड़ा है।

Answer 4

प्रोफाइलिंग के बिना हम यह नहीं बता सकते कि प्रोग्राम के किस बिट को अनुकूलित करने की आवश्यकता है।

यदि आप एक बड़ी प्रणाली में थे, तो कोई एक प्रोफाइलर का उपयोग करेगा ताकि यह पता चल सके कि प्राइम नंबर जनरेटर वह हिस्सा है जिसे अनुकूलित करने की आवश्यकता है।

इसमें एक दर्जन या उससे अधिक निर्देशों के साथ एक लूप प्रोफाइलिंग आमतौर पर लायक नहीं है - प्रोफाइलर का ओवरहेड लूप बॉडी की तुलना में महत्वपूर्ण है, और एक लूप को बेहतर बनाने के एकमात्र तरीकों के बारे में जो एल्गोरिदम को छोटा करना है कम पुनरावृत्ति करने के लिए। तो आईएमई, एक बार जब आप किसी भी महंगे कार्यों को समाप्त कर देते हैं और सरल कोड की कुछ पंक्तियों का ज्ञात लक्ष्य रखते हैं, तो आप एल्गोरिदम को बदलने और निर्देश स्तर से कोड को बेहतर बनाने की कोशिश करने से अंत तक अंत तक चलने से बेहतर होते हैं। रूपरेखा।

Answer 5

आपको algorithms के संभावित परिवर्तन पर भी विचार करना चाहिए।

मान लें कि तत्वों को बस अपनी सूची में जोड़ने के लिए सस्ता हो सकता है, जैसा कि आप उन्हें पाते हैं।

शायद आपकी सूची के लिए स्थान स्थगित करने से, इसे बनाने/पॉप्युलेट करने के लिए सस्ता बना दिया जाएगा।

Answer 6

क्या आप नए प्राइम ढूंढने की कोशिश कर रहे हैं? यह बेवकूफ लग सकता है, लेकिन आप ज्ञात प्राइम के साथ कुछ प्रकार की डेटा संरचना को लोड करने में सक्षम हो सकते हैं। मुझे यकीन है कि वहां कोई सूची है। नए नंबरों की गणना करने वाली मौजूदा संख्याओं को ढूंढना एक बहुत ही आसान समस्या हो सकती है।

आप बहु-कोर सिस्टम का लाभ लेने के लिए अपने मौजूदा कोड बहु-थ्रेडेड बनाने के लिए माइक्रोस्कोफ्ट Parallel FX Library पर भी देख सकते हैं। न्यूनतम कोड परिवर्तनों के साथ आप लूप को बहु-थ्रेडेड के लिए बना सकते हैं।

Answer 7

वहाँ एरेटोस्थेनेज की चलनी के बारे में एक बहुत अच्छा लेख है: The Genuine Sieve of Eratosthenes

यह एक कार्यात्मक की स्थापना में है, लेकिन opimization के सबसे भी सी # में एक प्रक्रियात्मक कार्यान्वयन पर लागू होते हैं।

दो सबसे महत्वपूर्ण अनुकूलन 2 * पी के बजाय पी^2 पर क्रॉसिंग शुरू करना और अगले प्राइम नंबरों के लिए एक व्हील का उपयोग करना है।

समेकन के लिए, आप सभी संख्याओं को पी^2 तक पी के समानांतर में बिना किसी अनावश्यक काम के संसाधित कर सकते हैं।

Answer 8

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"); 
     } 
    }