अतीत में, इस प्रश्न का उत्तर एक ठोस, "नहीं" था। लेकिन 2017 तक, स्थिति बदल रही है।
लेकिन इससे पहले कि मैं जारी, कुछ पृष्ठभूमि शब्दावली के लिए समय:
- पूर्ण वर्ड अंकगणित
- आंशिक वर्ड अंकगणित
पूर्ण वर्ड अंकगणित:
यह मानक प्रतिनिधित्व है जहां संख्या संग्रहित है बेस 2 या 2 32-बिट या 64-बिट पूर्णांक की सरणी का उपयोग करते हुए। कई बिग्नम पुस्तकालयों और अनुप्रयोगों (जीएमपी समेत) इस प्रतिनिधित्व का उपयोग करते हैं।
पूर्ण-शब्द प्रतिनिधित्व में, प्रत्येक पूर्णांक का अद्वितीय प्रतिनिधित्व होता है। तुलना जैसे संचालन आसान हैं। लेकिन वाहक-प्रचार की आवश्यकता के कारण सामान जैसी चीजें अधिक कठिन होती हैं।
यह कैर्री-प्रचार है जो बिग्नम अंकगणित को सदिश बनाने के लिए लगभग असंभव बनाता है।
आंशिक-वर्ड अंकगणित
यह एक कम इस्तेमाल किया प्रतिनिधित्व जहां नंबर एक आधार हार्डवेयर शब्द-आकार से कम उपयोग करता है। उदाहरण के लिए, प्रत्येक 64-बिट शब्द में केवल 60 बिट डालें। या दशमलव अंकगणितीय के लिए 32-बिट शब्द-आकार के साथ आधार 1,000,000,000 का उपयोग करना।
जीएमपी के लेखक इसे "नाखून" कहते हैं जहां "नाखून" शब्द का अप्रयुक्त हिस्सा है।
अतीत में, आंशिक-शब्द अंकगणित का उपयोग ज्यादातर गैर-बाइनरी अड्डों में काम करने वाले अनुप्रयोगों तक ही सीमित था। लेकिन आजकल, यह और अधिक महत्वपूर्ण हो रहा है कि यह वाहक प्रसार को देरी होने की अनुमति देता है। पूर्ण वर्ड अंकगणित साथ
समस्याएं:
vectorizing पूर्ण शब्द अंकगणित ऐतिहासिक रूप से एक खो कारण रहा है:
- SSE/AVX2 कैरी-प्रसार के लिए कोई समर्थन नहीं है।
- एसएसई/एवीएक्स 2 में 128-बिट एड/सब नहीं है।
- SSE/AVX2 कोई 64 x 64-बिट पूर्णांक गुणा है। *
* AVX512-डीक्यू गुणा एक कम आधा 64x64-बिट कहते हैं। लेकिन अभी भी कोई ऊपरी आधा निर्देश नहीं है।
इसके अलावा, 86/64 bignums के लिए विशेष अदिश निर्देश के बहुत सारे है:
- ऐड-साथ-कैरी:
adc, adcx, adox।
- डबल-शब्द गुणा: सिंगल-ऑपरेंड
mul और mulx।
इस के प्रकाश में, सिग्ड के लिए x64 पर स्केलर को हरा करने के लिए सिग्नल के लिए बिग्नम-एड और बिग्नम-गुणा दोनों मुश्किल हैं। निश्चित रूप से एसएसई या एवीएक्स के साथ नहीं।
AVX2 के साथ, SIMD-गुणा bignum यदि आप डेटा को पुनर्व्यवस्थित 4 SIMD गलियों में से प्रत्येक में एक ही लंबाई की 4 अलग (और स्वतंत्र) पलता की "ऊर्ध्वाधर vectorization" सक्षम करने के लिए अदिश के साथ लगभग प्रतिस्पर्धी है।
AVX512 फिर से लंबवत वेक्टरलाइजेशन मानते हुए सिम के पक्ष में चीजों को और अधिक टिप देगा।
लेकिन अधिकांश भाग के लिए, बिग्नम का "क्षैतिज वेक्टरेशन" काफी हद तक खो गया है जब तक कि उनमें से कई (एक ही आकार के) नहीं हैं और उन्हें "लंबवत" बनाने के लिए उन्हें स्थानांतरित करने की लागत का खर्च उठा सकते हैं।
आंशिक-वर्ड अंकगणित
आंशिक-शब्द गणित के साथ
के vectorization, अतिरिक्त "कील" बिट्स आप देरी करने के लिए कैरी-प्रसार करने के लिए सक्षम।
तब तक जब तक आप शब्द को ओवरफ़्लो नहीं करते हैं, सिमड ऐड/सब सीधे किया जा सकता है। कई कार्यान्वयन में, आंशिक-शब्द प्रतिनिधित्व शब्दों को नकारात्मक होने की अनुमति देने के लिए हस्ताक्षरित पूर्णांक का उपयोग करता है।
क्योंकि (आमतौर पर) कैरेट करने की आवश्यकता नहीं होती है, आंशिक शब्दों पर सिमड एड/सब लंबवत और क्षैतिज-वेक्टरीकृत बिग्नम दोनों पर समान रूप से कुशलता से किया जा सकता है।
क्षैतिज-वेक्टरीकृत बिग्नम पर कैरेट अभी भी सस्ता है क्योंकि आप केवल अगले लेन पर नाखूनों को स्थानांतरित करते हैं।नाखून बिट्स को पूरी तरह से साफ़ करने के लिए एक पूर्ण कैरआउट और एक अनूठा प्रतिनिधित्व प्राप्त करने के लिए आम तौर पर तब तक जरूरी नहीं है जब तक आपको लगभग दो संख्याओं की तुलना करने की आवश्यकता न हो।
गुणात्मक आंशिक शब्द अंकगणित के साथ अधिक जटिल है क्योंकि आपको नाखून बिट्स से निपटने की आवश्यकता है। लेकिन ऐड/सब के साथ, यह क्षैतिज-वेक्टरीकृत बिग्नम पर कुशलतापूर्वक ऐसा करने के लिए संभव है।
AVX512-IFMA (कैननलेक प्रोसेसर के साथ आने) में ऐसे निर्देश होंगे जो 52 x 52-बिट गुणा (पूर्णतः एफपीयू हार्डवेयर का उपयोग करके) के 104 बिट्स देते हैं। यह आंशिक-शब्द प्रस्तुतिकरणों के साथ बहुत अच्छी तरह से खेलेंगे जो प्रति शब्द 52 बिट्स का उपयोग करते हैं।
बड़े गुणा FFTs का उपयोग कर
बहुत बड़ी bignums के लिए, गुणा सबसे अधिक कुशलता से Fast-Fourier Transforms (FFTs) उपयोग किया जाता है।
एफएफटी पूरी तरह से वेक्टरिज़ेबल हैं क्योंकि वे स्वतंत्र double एस पर काम करते हैं। यह संभव है क्योंकि मूल रूप से, एफएफटी का प्रतिनिधित्व करते हुए प्रतिनिधित्व आंशिक शब्द प्रतिनिधित्व है।
संक्षेप में, बिग्नम अंकगणित का वेक्टरराइजेशन संभव है। लेकिन बलिदान किया जाना चाहिए।
यदि आप उम्मीद करते हैं कि एसएसई/एवीएक्स कुछ मौजूदा बिग्नम कोड को प्रस्तुत करने में सक्षम हो, तो प्रतिनिधित्व और/या डेटा लेआउट में मौलिक परिवर्तन किए बिना, ऐसा होने की संभावना नहीं है।
लेकिन फिर भी, bignum अंकगणित वेक्टरize संभव है।
प्रकटीकरण:
मैं y-cruncher के लेखक जो बड़ी संख्या में arihmetic के बहुत करता हूँ।
हैसल/ब्रॉडवेल में एमएलएक्स, एडीसीएक्स, एडीओएक्स के लिए तत्पर हैं ... –
ग्रेट उत्तर। मुझे लगता है कि मैं उन लोगों में से एक हूं जिन्होंने कोशिश की और असफल रहा। –
लेकिन मुझे "कोई 128-बिट पूर्णांक जोड़ें/उप" के बारे में बिंदु नहीं समझा। यह समस्या क्यों है? सामान्य उद्देश्य/स्केलर रजिस्टरों के पास हार्डवेयर भी नहीं है। ऐसा करने का तरीका अलग-अलग सिम रजिस्टरों में दो स्टोर हाय और कम है। –