एक्सपोनिएशन करने के लिए सबसे तेज़ एल्गोरिदम क्या है?

Question

एक्सपोनिएशन करने के लिए सबसे तेज़ एल्गोरिदम क्या है? चलो सादगी के लिए प्राकृतिक संख्या अड्डों और घाटियों को मानते हैं।

एक कुशल गणित पुस्तकालय का उपयोग क्या होगा?

(जब मैं इसके लिए खोज, मैं सिर्फ परिणाम ऐसे एल्गोरिदम घातीय समय में चलाने के लिए संबंधित मिलता है।)

Answer 1

छोटे घातांक के लिए अजगर द्विआधारी घातांक (बराबरी से घातांक का एक प्रकार) के रूप में लाइन में देखा जा सकता का उपयोग करता है 2874 of http://svn.python.org/view/python/trunk/Objects/longobject.c?view=markup&pathrev=65518

बड़े एक्सपोनेंट्स के लिए यह 2^5-आर्य एक्सपोनेंटिएशन (स्क्वायरिंग द्वारा एक्सपोनेंटिएशन का एक वैकल्पिक प्रकार) का उपयोग करता है।

यदि आप केवल परिणाम के सबसे महत्वपूर्ण अंकों की परवाह करते हैं, तो आप x^y = exp (y * log (x)) की बहुत तेज़ी से गणना कर सकते हैं।

यदि आप केवल परिणाम के कम से कम महत्वपूर्ण अंकों (जैसे प्रोग्रामिंग प्रतियोगिता के लिए) की परवाह करते हैं, तो आप एक्सपोनेंट मॉड्यूलो को कुछ मान एम की गणना कर सकते हैं। उदाहरण के लिए, पायथन कमांड पाउ (एक्स, वाई, 1000) वाई की शक्ति के लिए x के अंतिम 3 अंक की गणना करें। यह स्क्वायरिंग विधि द्वारा एक्सपोनिएशन द्वारा किया जाता है, लेकिन ध्यान दें कि यह पूर्ण परिणाम की गणना करने से बहुत तेज हो सकता है क्योंकि यह सुनिश्चित करता है कि मध्यवर्ती संख्या एम

अतिरिक्त मोड़ के रूप में (यदि आप केवल कम से कम हस्ताक्षरकर्ता अंकों में रुचि रखते हैं), आप एक्सपोनेंट के आकार को कम करने के लिए यूलर के प्रमेय http://en.wikipedia.org/wiki/Euler%27s_theorem का उपयोग कर सकते हैं।

Answer 2

आप किसी दिए गए प्राकृतिक संख्या यू और किसी दिए गए इनपुट मीटर है, तो यू गणना करने के लिए^m आप निम्नलिखित एल्गोरिथ्म

q = m; 
prod = 1; 
current = u; 
while q > 0 do 
    if (q mod 2) = 1 then // detects the 1s in the binary expression of m 
      prod = current * prod; // picks up the relevant power 
      q--; 
    endif 
current = current * current; // u^i -> u^(2*i) 
q = q div 2 
enddo 

output = prod; 

तो बुनियादी तौर पर अगर आप लागू हो सकते हैं, मान लीजिए कि, यू^23 आप 23 से बाइनरी में कनवर्ट करें -> 10111 (बेस 2) फिर आपको^^ 23 = u^16 * u^4 * u^2 * u^1 (कोई यू^8 नहीं मिला है क्योंकि 2 अंकों से बाएं से दाएं 0 है)

जटिलता है हे (लॉग (एम)) या हे (एन) यदि आप n पर विचार के लिए लॉग इन होने के लिए (एम) _10 + 1

Answer 3

उपरोक्त सभी बाइनरी विधियों के साथ समस्या यह है कि वे केवल पूर्णांक तक ही सीमित हैं। यदि "एक्सपोनेंटिएशन" से आपका मतलब है कि ई^एक्स फ़ंक्शन की गणना करें, मैंने जो सबसे अच्छा देखा है वह पावर श्रृंखला है जो त्वरित रूप से एकत्र हो जाती है, और बहुपद, तर्कसंगत, या पैड अनुमान जो सीमित सीमा से मान्य हैं।

निश्चित रूप से एक बात: यदि आपको e^x से 96 दशमलव स्थानों के लिए एक बिजली तेज एल्गोरिदम मिल जाता है, तो आपको लॉग की गणना करने के लिए एक तेज तरीका भी मिलेगा (न्यूटन-रैफसन द्वारा)। वास्तव में, न्यूटन-रैफसन चौकोर रूप से अभिसरण करते हैं, इसलिए आप प्रत्येक पुनरावृत्ति के साथ अपने लॉग में परिशुद्धता के अंकों की संख्या दोगुना करते हैं। यह फर्थ दिनों में यूसीएलए के नाट ग्रॉसमैन का पसंदीदा था।

चार-बेंजर कैलकुलेटर के दिनों में, मैं e^x = (1 + x/1024)^10 का उपयोग करता था। निश्चित रूप से एक्स बहुत बड़े या बहुत छोटे के लिए टूट जाता है, लेकिन आप देख सकते हैं कि यह क्यों काम करता है। यदि आपके पास स्क्वायर रूट बटन है, तो आप लॉगरिदम प्राप्त करने के लिए इस विचार को उलट सकते हैं। लेकिन आपको घातीय कार्य के लिए वर्ग रूट की आवश्यकता नहीं है।

मुझे आश्चर्य है कि अगर वहाँ एजीएम एल्गोरिथ्म कि घातीय समारोह कर सकता है ... हममम के कुछ उलट है ....