मुझे इस तथ्य से अवगत है कि इरेटोस्टेनेस की चलनी को कार्यान्वित किया जा सकता है ताकि इसे ऊपरी बाउंड (सेगमेंटेड चलनी) के बिना लगातार प्राइम पाएं।एटकिन की विभाजित चलनी, संभव है?
मेरा सवाल है, क्या एटकिन/बर्नस्टीन की चाकू उसी तरह लागू की जा सकती है?
संबंधित प्रश्न: C#: How to make Sieve of Atkin incremental
हालांकि संबंधित सवाल केवल 1 जवाब है, जो कहते हैं, जो स्पष्ट रूप से गलत है "यह सब चलनी के लिए असंभव है" है।
एटकिन/बर्नस्टीन अपने original paper की धारा 5 में सेगमेंट संस्करण प्रदान करते हैं। संभवतः बर्नस्टीन के primegen प्रोग्राम उस विधि का उपयोग करता है।
धन्यवाद, मैं मूल पेपर को अंत से अंत तक नहीं पढ़ने के लिए अपमानित हूं। –
क्या एटकिन और बर्नस्टीन उनके पेपर में उल्लेख नहीं करते हैं, हालांकि यह सी स्रोत कोड में आता है, बड़ी श्रेणियों के लिए आवश्यक पृष्ठ विभाजन का उपयोग करके एटकिन की दक्षता की चलनी को बनाए रखने में अत्यधिक कठिनाई होती है: 1) प्राइम स्क्वायर फ्री कदम जल्दी से बन जाते हैं एक पृष्ठ से बहुत बड़ा, इन प्रक्रियाओं में कुछ जटिलताओं (और अक्षमता में वृद्धि) की आवश्यकता होती है, और 2) यह प्रत्येक 'x' और 'y' चर के लिए नए पेज प्रारंभ बिंदुओं की गणना करने में अधिक से अधिक समय लेता है बढ़ती रेंज के साथ वर्गबद्ध समाधान इसलिए ओ (एन) सापेक्ष प्रदर्शन कभी नहीं होता है। – GordonBGood
असल में, कोई एटकिन (एसओए) की एक असीमित चलनी को कार्यान्वित नहीं कर सकता है जैसा कि मैंने here in F# किया है। ध्यान दें कि यह एक शुद्ध कार्यात्मक संस्करण है जो वर्गों के समीकरणों और वर्गों के फ़िल्टर के समाधान को गठबंधन करने के लिए सरणी का भी उपयोग नहीं करता है और इस प्रकार एक अधिक अनिवार्य दृष्टिकोण से काफी धीमा है।
इष्टतम 32-बिट श्रेणियों के लिए लुकअप टेबल का उपयोग करके बर्लिन के अनुकूलन कोड को बेहद जटिल बनाते हैं और यहां प्रेजेंटेशन के लिए उपयुक्त नहीं हैं, लेकिन मेरे एफ # कोड को अनुकूलित करना काफी आसान होगा ताकि अनुक्रम एक सेट कम सीमा पर शुरू हो जाएं और खंडित संस्करण को लागू करने के लिए केवल एक सीमा से अधिक उपयोग किया जाता है, और/या उसी तकनीकों को ऐरे का उपयोग करके एक और अनिवार्य दृष्टिकोण के लिए लागू किया जाता है।
नोट SOA के भी Berstein के कार्यान्वयन वास्तव में नहीं है कि प्रति Kim Walisch's primesieve के रूप में सभी संभव अनुकूलन के साथ तेजी से एरेटोस्थेनेज की चलनी से लेकिन संख्या के चयनित श्रेणी के लिए एरेटोस्थेनेज की चलनी का केवल तुलना में तेजी से एक समतुल्य रूप अनुकूलित संस्करण है उनके कार्यान्वयन के अनुसार।
EDIT_ADD: जो लोग उच्च जहां के लिए कम से एक सीमा से अधिक SOA उपयोग करने के लिए एक छद्म कोड विधि जोड़ने का Berstein के छद्म कोड और सी कोड की खोजबीन करना, मैं इस सवाल का जवाब करने के लिए जोड़ा जा रहा नहीं करना चाहती के लिए मॉड्यूलो (और 2,3,5 पहिया पर केवल प्रविष्टियों के लिए संभावित बिट पैकिंग) ऑप्टिमाइज़ेशन का उपयोग करने के लिए लो से उच्च + 1 तक डेल्टा को भी मॉड्यूल 60 तक सीमित किया जा सकता है।
यह एसओए क्वाड्रेटिक्स (4 * x^2 + y ^), (3 * x^2 + y^2), (3 * x^2 -y^2) का उपयोग करके संभावित कार्यान्वयन पर आधारित है, और (3 * x^2 -y^2) एक और एसक्यूआरटी ((उच्च -1)/4), एसक्यूआरटी ((उच्च -1)/3) के बीच मूल्यों के लिए निर्धारित प्रत्येक अनुक्रम के लिए एक्स मान के साथ संख्याओं के अनुक्रम के रूप में व्यक्त किया जाना चाहिए, और 2 * के लिए वर्गबद्ध हल करना x^2 + 2 * x - उच्च - 1 = 0 x = (एसक्यूआरटी (1 + 2 * (उच्च + 1)) - 1)/2, क्रमशः, मेरे लिंक # कोड में शीर्ष लिंक के अनुसार व्यक्त किए गए अनुक्रमों के साथ । अनुक्रमों के अनुकूलन का उपयोग तब होता है जब "4x" अनुक्रमों के लिए केवल विषम कंपोजिट्स के लिए सिलाई, वाई मानों को केवल अजीब होना चाहिए और "3x" अनुक्रमों को केवल वाई के विषम मानों का उपयोग करने की आवश्यकता होती है जब x भी होता है और इसके विपरीत। आगे ऑप्टिमाइज़ेशन क्वाड्रैटिक समीकरणों (अनुक्रमों में तत्वों) के समाधानों की संख्या को कम करता है, यह देखते हुए कि उपर्युक्त अनुक्रमों पर मॉड्यूलो पैटर्न x की बहुत छोटी श्रेणियों पर दोहराए जाते हैं और केवल 30 में से y की श्रेणियों को दोहराते हैं, जिनका उपयोग किया जाता है बर्स्टीन कोड लेकिन मेरे एफ # कोड में अभी तक लागू नहीं किया गया है।
मैं अच्छी तरह से ज्ञात ऑप्टिमाइज़ेशन भी शामिल नहीं करता हूं जिसे पहिया कारक बनाने और शुरुआती सेगमेंट पते के लिए गणना के लिए प्राइम "स्क्वायर फ्री" कूलिंग पर लागू किया जा सकता है जैसा कि मैं my implementations of a segmented SoE में उपयोग करता हूं।
तो क्रमशः "4x", "3x +", और "3x-" (या "3x +" और "3x-" के साथ सेगमेंट पतों को अनुक्रमित करने के प्रयोजनों के लिए एफ # कोड में किया गया है), - FIRST_ELEMENT, जहां FIRST_ELEMENT प्रत्येक दिए गए मूल्य के लिए y के न्यूनतम लागू मूल्य के साथ है
की गणना सीमा कम: और इसके बाद के संस्करण के अनुसार प्रत्येक के लिए एक्स की सीमाओं की गणना करने के बाद, छद्म कोड इस प्रकार है "3x-" अनुक्रम के मामले के लिए x या y = x - 1 का।
इस सीमा में कितने तत्व हैं, यह गणना करने के काम के लिए, यह कितने (y1)^2 + (y2)^2 + (y3)^2 के सवाल के लिए उबलता है ... जहां प्रत्येक वाई संख्या दो से अलग होती है, आवश्यकतानुसार या अजीब 'y' उत्पन्न करने के लिए। स्क्वायर अनुक्रम विश्लेषण में सामान्य रूप से, हम देखते हैं कि वर्गों के बीच अंतर लगातार बढ़ती वृद्धि है क्योंकि डेल्टा (9 -1) 8 है, डेल्टा (25 - 9) 8 की वृद्धि के लिए 16 है, डेल्टा (4 9 -25) है 24, इत्यादि की आगे बढ़ने के लिए 24। ताकि एन तत्वों के लिए इस उदाहरण के लिए अंतिम वृद्धि 8 * एन है। इसका उपयोग करते हुए तत्वों के अनुक्रम को व्यक्त करते हुए, हम पाते हैं कि यह एक है (या जो भी पहले तत्व के रूप में चुनता है) और कुछ बार अनुक्रम के आठ गुना (1 + 2 + 3 + ... + n)। अब रैखिक अनुक्रमों में मानक कमी लागू होती है जहां यह योग (एन + 1) * एन/2 या एन^2/2 + एन/2 है। यह हम हल कर सकते हैं कि वर्गबद्ध समीकरण एन^2/2 + एन/2 - रेंज = 0 या एन = (एसक्यूआरटी (8 * रेंज + 1) - 1)/2 को हल करके सीमा में कितने एन तत्व हैं।
अब, यदि FIRST_ELEMENT + 4 * (n + 1) * n शुरुआती पते के रूप में कम के बराबर नहीं है, तो एक में जोड़ें और FIRST_ELEMENT + 4 * (n + 2) * (n + 1) का उपयोग करें प्रारंभिक पता यदि कोई अनुक्रम पैटर्न को खींचने वाले व्हील फैक्टरलाइज़ेशन को लागू करने के लिए और अधिक अनुकूलन का उपयोग करता है, तो तालिका सारणी को उपयोग किए गए एन के निकटतम मूल्य को देखने के लिए उपयोग किया जा सकता है जो शर्तों को पूरा करता है।
प्रारंभिक तत्व के मॉड्यूलस 12 या 60 को सीधे गणना की जा सकती है या मॉड्यूलो अनुक्रमों की दोहराने वाली प्रकृति के आधार पर लुकअप टेबल के उपयोग द्वारा उत्पादित किया जा सकता है।
प्रत्येक अनुक्रम का उपयोग समग्र राज्यों को उच्च सीमा तक टॉगल करने के लिए किया जाता है। यदि प्रति अनुक्रम केवल लागू तत्वों के बीच मूल्यों को कूदने के लिए अनुक्रमों में अतिरिक्त तर्क जोड़ा जाता है, तो मॉड्यूल स्थितियों का कोई और उपयोग आवश्यक नहीं है।
उपरोक्त "3x +" और "3x-" अनुक्रमों के बाद उपरोक्त "4x" अनुक्रम के बाद किया जाता है (या "3x +" और "3x-" को "3x" अनुक्रमों के एक सेट में जोड़कर) पहले की गणना या प्रति लूप परीक्षण के रूप में एक्स सीमाएं।
और वहाँ तुम्हारे पास है: खंडों में चलनी रेंज है, जो सबसे अच्छा तय आकार है कि सबसे अच्छा स्मृति पहुँच क्षमता के लिए CPU कैश आकार से जुड़े हुए हैं के रूप में प्रयोग किया जाता है विभाजित की उचित विधि, के आधार पर विभाजित करने की एक विधि दी एसओए जैसे कि बर्नस्टीन द्वारा उपयोग किया जाता है लेकिन अभिव्यक्ति में कुछ हद तक सरल होता है क्योंकि यह उल्लेख करता है लेकिन मॉड्यूलो ऑपरेशंस और बिट पैकिंग को गठबंधन नहीं करता है।
मैंने वर्षों के लिए एटकिन/बर्नस्टीन चलनी का अध्ययन किया है और कभी भी यह समझ नहीं लिया कि इसे कैसे विभाजित किया जाए - जिसका अर्थ है कि, इसे कुछ मनमाने ढंग से बड़ी संख्या में शुरू करने के लिए, शायद थोड़ी सी प्रीकंप्यूशन के साथ। मुझे यह देखने में दिलचस्पी होगी कि किसी के पास है या नहीं। – librik