छोटे-आइश संख्याओं के लिए सबसे तेज़ प्राइम टेस्ट

Question

मैं अपने खाली समय में प्रोजेक्ट यूलर के माध्यम से खेल रहा हूं, और यह उस बिंदु पर आया है जहां मुझे कुछ रिफैक्टरिंग करने की आवश्यकता है। मैंने मिलर-राबिन, साथ ही कुछ चोरों को लागू किया है। मैंने सुना है कि पहले से ही छोटे-आइश संख्याओं के लिए स्विस वास्तव में तेज़ हैं, जैसा कि कुछ मिलियन से कम है। क्या किसी के पास इस पर कोई जानकारी है? Google बहुत उपयोगी नहीं था।

Answer 1

हां, आपको अधिकांश एल्गोरिदम मिलेगा कि आप समय के लिए स्थान का व्यापार कर सकते हैं। दूसरे शब्दों में, अधिक स्मृति के उपयोग की अनुमति देकर, गति ^* में काफी बढ़ी है।

मैं वास्तव में मिलर-राबिन एल्गोरिथ्म पता नहीं है लेकिन, जब तक कि यह एक एकल पारी-बाएँ/जोड़ सकते हैं और स्मृति निष्कर्षण से अधिक आसान है, यह एक पूर्व गणना की चलनी से पानी से बाहर उड़ा दिया जाएगा।

यहां महत्वपूर्ण बात की गणना की जाती है। प्रदर्शन के संदर्भ में, इस तरह की चीजों की पूर्व गणना करने के लिए यह एक अच्छा विचार है क्योंकि पहले लाखों प्राइम्स निकट भविष्य में बदलने की संभावना नहीं होगी :-)

दूसरे शब्दों में, अपनी चाकू बनाएं जैसे कि:

unsigned char primeTbl[] = {0,0,1,1,0,1,0,1,0,0,0,1}; 
#define isPrime(x) ((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x)) 

मैक्रोज़ में a++ जैसी चीज़ों को पारित करने के बारे में सभी सामान्य चेतावनी के साथ। यह आपको दोनों दुनिया के सर्वश्रेष्ठ, "छोटे-आश" प्राइम्स के लिए एक अंधेरे से तेज टेबल लुकअप देता है, जो सीमा के बाहर के लोगों के लिए गणना विधि पर वापस आ जाता है।

स्पष्ट रूप से आप उस लुकअप टेबल को उत्पन्न करने के लिए अन्य विधियों में से एक का उपयोग करके एक प्रोग्राम लिखेंगे - आप वास्तव में इसे सभी हाथों में टाइप नहीं करना चाहते हैं।

लेकिन, सभी ऑप्टिमाइज़ेशन प्रश्नों के साथ, उपाय, अनुमान न करें!

---

^{* एक} इस का एक क्लासिक मामले कुछ ट्रिग कार्यों मैं एक बार एक एम्बेडेड सिस्टम के लिए लिखने के लिए किया था। यह एक प्रतिस्पर्धी अनुबंध बोली थी और सिस्टम की सीपीयू की तुलना में थोड़ा अधिक भंडारण था।

हम वास्तव में अनुबंध जीत चुके हैं क्योंकि कार्यों के लिए हमारे बेंचमार्क आंकड़े प्रतिस्पर्धा को दूर कर देते हैं।

क्यों? चूंकि हमने मूल रूप से किसी अन्य मशीन पर गणना की गई लुकअप तालिका में मूल्यों की गणना की थी। कमी के न्यायिक उपयोग (इनपुट मानों को 90 डिग्री से नीचे लाने) और ट्रिग गुण (तथ्य यह है कि कोसाइन साइन की एक चरण शिफ्ट है और अन्य तीन क्वाड्रंट पहले से संबंधित हैं), हमें लुकअप टेबल नीचे मिल गया 180 प्रविष्टियां (प्रति आधा डिग्री)।

सबसे अच्छा समाधान

उन है कि सुंदर हैं और कुटिल :-)

---

क्या इसके लायक है के लिए कर रहे हैं, निम्नलिखित सी कोड आप के लिए इस तरह के एक मेज, चार लाख से नीचे के सभी अभाज्य संख्या उत्पन्न होगा (उनमें से 283,000)।

#include <stdio.h> 

static unsigned char primeTbl[4000000]; 

int main (void) { 
    int i, j; 

    for (i = 0; i < sizeof(primeTbl); i++) 
     primeTbl[i] = 1; 

    primeTbl[0] = 0; 
    primeTbl[1] = 0; 
    for (i = 2; i < sizeof(primeTbl); i++) 
     if (primeTbl[i]) 
      for (j = i + i; j < sizeof(primeTbl); j += i) 
       primeTbl[j] = 0; 

    printf ("static unsigned char primeTbl[] = {"); 
    for (i = 0; i < sizeof(primeTbl); i++) { 
     if ((i % 50) == 0) { 
      printf ("\n "); 
     } 
     printf ("%d,", primeTbl[i]); 
    } 
    printf ("\n};\n"); 
    printf ("#define isPrime(x) " 
     "((x < sizeof(primeTbl) ? primeTbl[x] : isPrimeFn(x))\n"); 

    return 0; 
} 

आप सोलह लाख प्रविष्टियों (16M) को primeTbl मेज तक सामने लाना कर सकते हैं, तो आप उस एक लाख (पहले 1,031,130 अभाज्य संख्या) के ऊपर प्रधानमंत्री गिनती रखने के लिए काफी है मिल जाएगा।

अब कम भंडारण करने के तरीके हैं जैसे अजीब संख्याओं को संग्रहित करना और मैक्रो को समायोजित करने के लिए समायोजित करना, या हस्ताक्षरित वर्णों के बजाय थोड़ा मास्क का उपयोग करना। अगर स्मृति उपलब्ध है तो मैं खुद को एल्गोरिदम की सादगी पसंद करता हूं।

Answer 2

एकमात्र तरीका स्वयं को बेंचमार्क करना है। जब आप करते हैं, इसे लिखो, और इसे कहीं ऑनलाइन पोस्ट करें।

Answer 3

पूर्व गणना की धारणा पर एक प्रकार के रूप में, आप पहली बार सस्ते में देख सकते हैं कि उम्मीदवार संख्या p 2, 3, 5, 7, या 11 से विभाज्य है यदि नहीं, तो p प्रधानमंत्री यह घोषणा करते हैं 2 ^{पी -1} = 1 (मॉड पी)। यह किसी बिंदु पर असफल हो जाएगा, लेकिन यह 100 मिलियन तक काम करता है क्योंकि मैंने इसका परीक्षण किया (पूर्व-गणना)।

दूसरे शब्दों में, सभी छोटे-ish फर्मेट आधार से 2 छद्म अभाज्य संख्या 3 में से एक, 5, 7, या 11 से विभाज्य हैं

संपादित करें:

के रूप में सही ढंग से @ द्वारा नोट स्टारब्लू, उपरोक्त बस गलत है। मेरे कार्यक्रम में एक बग था। सबसे अच्छा मैं उपरोक्त में संशोधन कर सकता हूं:

यदि उम्मीदवार p 2, 3, 5, 7, या 11 द्वारा विभाजित है, तो इसे समग्र घोषित करें;
अन्य p {4181921, 4469471, 52560 9 1, 9006401, 9863461} में से एक है, इसे समग्र घोषित करें;
अन्य यदि p आधार 2 और 5 के लिए मिलर-राबिन परीक्षण पास करता है तो इसे प्रमुख घोषित करें;
अन्यथा इसे समग्र घोषित करें।

यह मैंने 10,000,000 से कम पूर्णांक के लिए परीक्षण किया। शायद आधार की एक अलग जोड़ी भी बेहतर करेगी।

कृपया मेरी गलतियों के लिए मेरी माफी स्वीकार करें।

संपादित करें 2:

ठीक है, ऐसा लगता है कि जानकारी मैं के बाद था Miller-Rabin algorithm के लिए विकिपीडिया पृष्ठ, खंड "Deterministic variants of the test" शीर्षक पर पहले से ही है।

Answer 4

मैं एक टायर दृष्टिकोण की सलाह देता हूं। सबसे पहले, सुनिश्चित करें कि कोई छोटा प्राइम कारक नहीं हैं। पहले 20 या 30 प्राइम्स द्वारा परीक्षण-विभाजन, हालांकि यदि आप एक चालाक दृष्टिकोण का उपयोग करते हैं तो आप जीसीडीएस का उपयोग करके आवश्यक डिवीजनों की संख्या को कम कर सकते हैं। यह चरण कंपोजिट्स का लगभग 9 0% फ़िल्टर करता है।

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

अंतिम साबित चरण इस बात पर निर्भर करता है कि आप कितना बड़ा जाना चाहते हैं। यदि आप एक छोटी सी सीमा में काम करने के इच्छुक हैं, तो 2-स्यूडोप्रिम्स की सूची पर एक बाइनरी खोज करें जो आप सबसे बड़ी अनुमति देते हैं। यदि यह 2^32 है, तो आपकी सूची में केवल 10,403 सदस्य होंगे, इसलिए लुकअप में केवल 14 प्रश्न लेना चाहिए।

यदि आप 2^64 तक जाना चाहते हैं, तो अब यह जांचने के लिए पर्याप्त है (Jan Feitisma के काम के लिए धन्यवाद) यह जांचने के लिए कि संख्या बीपीएसडब्ल्यू छद्मप्रवाह है या नहीं। (आप सभी अपवादों की 3 जीबी सूची भी डाउनलोड कर सकते हैं, उन परीक्षणों को हटा दें जो परीक्षण विभाजन हटा देंगे, और डिस्क-आधारित बाइनरी खोज लिखेंगे।) T. R. Nicely में एक अच्छा पृष्ठ है जो इस उचित रूप से कुशलता से कार्यान्वित करने का तरीका बताता है।

यदि आपको उच्च जाने की आवश्यकता है, तो उपरोक्त विधि को लागू करें और इसे पॉकलिंगटन-शैली परीक्षण के लिए उप-सूटिन के रूप में उपयोग करें। यह "छोटे-आश" की परिभाषा को फैलाता है; यदि आप इन तरीकों से अधिक जानकारी चाहते हैं, तो बस पूछें।