स्क्वायरिंग एन-बिट int बनाम दो एन-बिट इन्स गुणा

Question

अस्वीकरण: गृहकार्य प्रश्न। मैं एक संकेत की तलाश में हूं ...

प्रोफेसर एफ लेक अपनी कक्षा को बताता है कि यह दो एन-बिट पूर्णांक गुणा करने के बजाय एन-बिट पूर्णांक को स्क्वायर करने के लिए असंवेदनशील रूप से तेज़ है। क्या उन्हें विश्वास करना चाहिए?

मेरा मानना ​​है कि दो एन-बिट इनट्स को शिफ्ट/एड के माध्यम से गुणा करना एक ओ (एन) ऑपरेशन है, लेकिन मैं नहीं देख सकता कि एन-बिट int squaring क्यों अलग होगा। क्या मैं कुछ भूल रहा हूँ?

Answer 1

इन कार्यों को पूरा करने के लिए कंप्यूटर को आवश्यक कदमों पर विचार करें। याद रखें कि कंप्यूटर लोगों से काफी अलग काम करते हैं।

Answer 2

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

एक स्क्वायरिंग एल्गोरिदम केवल 2^n संभावित इनपुट को संभालने की आवश्यकता है, हालांकि इसे दो इनपुट के साथ एक गुणा एल्गोरिदम के रूप में मॉडलिंग किया जा सकता है।

मेरा अनुमान है कि जेनेरिक गुणा एल्गोरिदम अनुकूलित करने का कोई तरीका होगा जब आप जानते हैं कि दोनों इनपुट समान होंगे, लेकिन मुझे इसके बारे में सोचना होगा। यही लाइन मैं जांच कर रही होगी, वैसे भी है ...

Answer 3

के बाद से आप केवल एक संकेत था, इस सवाल का जवाब इस समीकरण से आता है: (a + b)^2 = a^2 + b^2 + 2*a*b

पहेली खराब मत के लिए, मैं पूरा समाधान separately पोस्ट किया है :)

Answer 4

पुनर्लेखित: यह एकमात्र सुधार है जिसे मैं दो एन-बिट संख्याओं को एक साथ गुणा करने पर एन-बिट संख्या को स्क्वायर करने में देख सकता हूं। यह ओ (एन^2) बनाम ओ (एन) में तरह से असंभव रूप से बेहतर नहीं हो सकता है जो आमतौर पर कंप्यूटर विज्ञान में उपयोग किया जाता है। हालांकि, अगर हम इसे असंवेदनशील रूप से लेते हैं जिसका अर्थ है जटिलता (गुणात्मक स्थिरांक समेत), तो यह उस परिभाषा को फिट करेगा। वैसे भी, ऐसा करने के लिए मैं यह देख सकता हूं कि इसे ले जाएं या छोड़ दें।

मान लें कि हमारे पास दो एन-बिट संख्याएं हैं, x और y। हम उन्हें एक साथ जोड़ सकते हैं (x*y) ए * एन^2 + ओ (एन) संचालन के साथ शिफ्ट-एंड-एड विधि के साथ जहां ए स्थिर है। दूसरा शब्द, ओ (एन) शब्द, बड़े पर्याप्त एन के लिए उपेक्षा किया जा सकता है, इसलिए संचालन की संख्या अनिवार्य रूप से ए * एन^2 है।

अब हम x^2 की गणना करते हैं। अगर हम a परिभाषित उस में x सेट है, तो

x = a + b 

x^2 = (a + b)^2 = a^2 + b^2 + 2*a*b 

हालांकि

के केवल निचले एन/2 बिट्स के लिए केवल ऊपरी एन/2 x यह में स्थापित है और b के टुकड़े के लिए, याद रखें कि हम गुणा कर सकते हैं ए * एन^2 संचालन के साथ एक एन-बिट संख्या। * को गुणा करने के लिए हमें केवल ए * (एन/2)^2 = ए * एन/4 ऑपरेशंस करना होगा। बी * बी और ए * बी के लिए भी यही है। हम हे ध्यान नहीं देते हैं (एन) के संचालन, तो x^2 = (a + b)^2

A*N^2/4 + A*N^2/4 + A*N^2/4 = (3/4)*A*N^2 

आपरेशनों में गणना की जाती है जो निश्चित रूप से मानक एक से बेहतर है * द्वारा एक * एन^2 दो मनमाना एन-बिट नंबर गुणा करने के लिए एन^2/4। हम a^2 और b^2 के साथ एक ही ऑपरेशन दोहराकर इस पर और सुधार कर सकते हैं। कुछ बिंदु पर यह करने के लिए फायदेमंद नहीं होगा। यह एक बड़ा सुधार नहीं है, लेकिन यह सब मुझे मिल सकता है। यदि यह मायने रखता है या नहीं तो आप खुद के लिए निर्णय ले सकते हैं।

Answer 5

यहां a hint है।

और यहां मेरा समाधान है SECRET कोड में: Fdhnevat zrnaf lbh bayl unir gb qb bar vavgvny एसजी, abg gjb, fb vg'f snfgre।

Answer 6

कल्पना कीजिए कि वर्ग वास्तव में असंवेदनशील रूप से तेज़ है। तो अगर आप एक * ख है, तो आप गणना कर सकते हैं:

 
a = m + n 
b = m - n 

तो इस समीकरण प्रणाली को सुलझाने देता है:

 
m = (a+b)/2 
n = (a-b)/2 

लेकिन तब हम

 
a * b = (m+n)*(m-n) = m² - n² 

या मध्यवर्ती चर के बिना है:

 
a * b = ((a+b)² - (a-b)²)/4 

तो आप कर सकते हैं दो स्क्वायरिंग ऑपरेशंस द्वारा किसी भी गुणा को प्रतिस्थापित करें (और कुछ जोड़ों और विभाजन 4 से थोड़ा सा है, जो कि थोड़ा सा शिफ्ट है, और इन्हें एसिम्प्टोटिकल जटिलता के लिए अनदेखा किया जा सकता है)। इसलिए गुणा की जटिलता स्क्वायरिंग की जटिलता से दोगुनी है। बेशक, "दो बार" एक स्थिर कारक है, जिसका अर्थ है कि दोनों के पास एसिम्प्टोटिकल जटिलता है।