डीजे में 10^15 की सीमा कहां है। बर्नस्टीन का 'प्राइमजेन' कार्यक्रम आया है?

Question

http://cr.yp.to/primegen.html पर आप प्रोग्राम के स्रोत ढूंढ सकते हैं जो प्राइम उत्पन्न करने के लिए एटकिन की चलनी का उपयोग करते हैं। जैसा कि लेखक कहते हैं कि उन्हें भेजे गए ई-मेल का जवाब देने में कुछ महीने लग सकते हैं (मैं समझता हूं कि, वह निश्चित रूप से एक कब्जा कर लिया आदमी है!) मैं यह प्रश्न पोस्ट कर रहा हूं।

पृष्ठ बताता है कि 'प्राइमजेन 1000000000000000 तक प्राइम उत्पन्न कर सकता है'। मैं समझने की कोशिश कर रहा हूं कि ऐसा क्यों है। निश्चित रूप से 2^64 ~ 2 * 10^1 (लंबे हस्ताक्षर किए गए int का आकार) तक सीमित है क्योंकि इस प्रकार संख्याओं का प्रतिनिधित्व किया जाता है। मुझे यकीन है कि अगर एक बड़ा प्राइम गैप होगा (> 2^31) तो संख्याओं की प्रिंटिंग असफल हो जाएगी। हालांकि इस सीमा में मुझे लगता है कि ऐसा कोई प्रमुख अंतर नहीं है।

या तो लेखक ने बाध्यता (और वास्तव में यह लगभग 10^1 9) है या स्रोत कोड में एक जगह है जहां अंकगणितीय ऑपरेशन ओवरफ्लो या ऐसा कुछ हो सकता है।

अजीब बात यह है कि आप वास्तव में संख्या> 10^15 के लिए यह चला सकते है:

./primes 10000000000000000 10000000000000100 
10000000000000061 
10000000000000069 
10000000000000079 
10000000000000099 

और यदि आपको लगता है Wolfram Alpha, यह सही है।

कुछ तथ्यों मैं "रिवर्स इंजीनियर" था:

1. संख्या के 1,920 * PRIMEGEN_WORDS = 3,932,160 संख्या (primegen_next.c में primegen_fill समारोह देखें)
2. PRIMEGEN_WORDS नियंत्रण कितना बड़ा एक भी बैचों में sifted कर रहे हैं sifting है - आप इसे अपने CPU कैश फिट करने के लिए primgen_impl.h में समायोजित कर सकते हैं,
3. चलनी का कार्यान्वयन स्वयं keygen.c फ़ाइल में है - मुझे लगता है कि यह सही है; आपको जो मिलता है वह पीजी-> buf में प्राइम का बिटमैस्क है (प्राइमजेन_फिल फ़ंक्शन देखें)
4. बिटमास्क का विश्लेषण किया जाता है और प्राइम को पीजी-> पी सरणी में संग्रहीत किया जाता है।

मुझे कोई बिंदु नहीं दिखता है कि ओवरफ़्लो हो सकता है।

Answer 1

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

Answer 2

बस एल्गोरिदम से, मैं निष्कर्ष निकालूंगा कि ऊपरी सीमा 32 बिट संख्याओं से आती है। पृष्ठ में पेंटियम -3 को सीपीयू के रूप में उल्लेख किया गया है, इसलिए मेरा अनुमान है कि यह बहुत पुराना है और 64 बिट का उपयोग नहीं करता है।

2^32 लगभग 10^9 हैं। एटकिन्स (जो एल्गोरिदम का उपयोग करता है) की चलनी एन^(1/2) बिट्स (यह एक बड़े बिटफील्ड का उपयोग करती है) की आवश्यकता होती है। जिसका अर्थ है 2^32 बड़ी मेमोरी में आप (conservativ) एन लगभग 10^15 बना सकते हैं। चूंकि यह संख्या एक मोटा रूढ़िवादी ऊपरी सीमा है (आपके पास सिस्टम और अन्य कार्यक्रम स्मृति पर कब्जा कर रहे हैं, आईओ के लिए पता श्रेणी आरक्षित है ...) असली ऊपरी सीमा उच्च/हो सकती है।