पूर्णांक C++ में गुणा कैसे करते हैं?

Question

मैं सोच रहा था कि सी ++ में संख्याओं को गुणा करने के लिए किस प्रकार की विधि का उपयोग किया गया था। क्या यह पारंपरिक स्कूलबुक लंबी गुणा है? Fürer's algorithm? Toom-Cook?

मैं सोच रहा था क्योंकि मैं बहुत बड़ी संख्या में गुणा करने की आवश्यकता करने जा रहा हूँ और दक्षता के एक उच्च डिग्री की जरूरत है। इसलिए पारंपरिक स्कूलबुक लंबे गुणा O(n^2) बहुत अक्षम हो सकता है, और मुझे गुणा की एक और विधि का सहारा लेना होगा।

तो सी ++ का किस प्रकार का गुणा उपयोग करता है?

Answer 1

आप यहाँ कई महत्वपूर्ण बातें याद आ रही हो रहे हैं:

1. के बीच देशी गणित और bignum अंकगणित एक अंतर नहीं है।
2. आपको बिग्नम अंकगणित में रुचि हो रही है।
3. सी ++ bignum अंकगणित का समर्थन नहीं करता है। आदिम डेटाटाइप आमतौर पर देशी प्रोसेसर के लिए अंकगणित होते हैं।

बिग्नम (मनमाने ढंग से सटीक) अंकगणित प्राप्त करने के लिए, आपको इसे स्वयं लागू करने या पुस्तकालय का उपयोग करने की आवश्यकता है। (जैसे GMP) जावा के विपरीत, और सी # (दूसरों के बीच), सी ++ में मनमाने ढंग से सटीक अंकगणित के लिए लाइब्रेरी नहीं है।

उन फैंसी एल्गोरिदम के सभी:

• Karatsuba: O(n^1.585)
• Toom-कुक: < O(n^1.465)
• FFT आधारित: ~ O(n log(n))

ही लागू गणित जो लागू किया जाता है bignum लिए कर रहे हैं बिग्नम पुस्तकालयों में। प्रोसेसर अपने मूल अंकगणितीय परिचालनों के लिए क्या उपयोग करता है कुछ हद तक अप्रासंगिक है क्योंकि यह आमतौर पर निरंतर समय है।

---

किसी भी मामले में, मैं अनुशंसा नहीं करता कि आप एक बिग्नम लाइब्रेरी को लागू करने का प्रयास करें। मैंने इसे पहले किया है और यह काफी मांग है (विशेष रूप से गणित)। तो आप पुस्तकालय का उपयोग बंद कर रहे हैं।

Answer 2

यह सब लाइब्रेरी और कंपाइलर पर निर्भर करता है।

Answer 3

सी ++ पूर्णांक गुणा में चिप द्वारा संभाला जाता है। मानक भाषा में पर्ल के BigNum के बराबर नहीं है, हालांकि मुझे यकीन है कि इस तरह के पुस्तकालय मौजूद हैं।

Answer 4

"बहुत बड़ी संख्या" से आपका क्या मतलब है?

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

सबसे बड़ी संख्या है कि विभिन्न डेटा प्रकार द्वारा दर्शाया जा सकता विभिन्न कार्यान्वयन के बीच भिन्न हो सकते हैं, लेकिन कुछ विशिष्ट मूल्यों डबल के लिए लंबे, और 1.79769e + 308 के लिए के लिए पूर्णांक, 9223372036854775807 2147483647 हैं।

Answer 5

यह हार्डवेयर में किया जाता है। इसी कारण से बड़ी संख्या काम नहीं करेगी। 64 बिट हार्डवेयर में सबसे बड़ी संख्या सी ++ प्रतिनिधित्व कर सकती है 18446744073709551616 है। यदि आपको बड़ी संख्या की आवश्यकता है तो आपको मनमाने ढंग से सटीक पुस्तकालय की आवश्यकता है।

Answer 6

सादा C++ सीपीयू mult निर्देश का उपयोग करता है (bitshifts और परिवर्धन का उपयोग कर आपके CPU इस तरह के एक निर्देश नहीं है या कोर्स की किताब गुणा।)

अगर आप बड़ी संख्या के लिए तेजी से गुणा की जरूरत है, मैं जीएमपी पर रखने का सुझाव देते हैं (http://gmplib.org) और gmpxx.h

Answer 7

से C++ इंटरफ़ेस का उपयोग आप ग में मानक पूर्णांक गुणा बड़ी संख्या के साथ काम करते हैं ++ अब कार्य नहीं करेगा और आप एक पुस्तकालय जीएमपी http://gmplib.org/

भी तरह, मनमाने ढंग से सटीक गुणा प्रदान करने का उपयोग करना चाहिए,आपको अपने आवेदन (= समयपूर्व अनुकूलन) लिखने से पहले प्रदर्शन के बारे में चिंता नहीं करना चाहिए। ये गुणा तेजी से होंगे, और संभवतः आपके सॉफ़्टवेयर में कई अन्य घटक अधिक मंदी का कारण बनेंगे।

Answer 8

ये संख्याएं कितनी बड़ी हैं? यहां तक ​​कि पाइथन जैसी भाषाएं 1e100*1e100 भी मानक प्रोसेसर पर एक सेकंड में 3 मिलियन गुना अधिक मनमाने ढंग से सटीक पूर्णांक के साथ कर सकती हैं। यह 100 महत्वपूर्ण स्थानों पर गुणा है जो दूसरे के दस लाख से भी कम लेते हैं। इसे संदर्भ में रखने के लिए अवलोकन ब्रह्मांड में केवल 10^80 परमाणु हैं।

लिखें कि आप पहले क्या हासिल करना चाहते हैं, और यदि आवश्यक हो तो बाद में अनुकूलित करें।