लॉग फ़ंक्शन की जटिलता क्या है?

Question

लॉग बेस 10 फ़ंक्शन की जटिलता क्या है?

Answer 1

यह वास्तव में डोमेन के आधार पर निर्भर करता है कि आप किस मान को लॉगेरिथम की गणना करना चाहते हैं।

आईईईई युगल के लिए, कई प्रोसेसर एक असेंबली निर्देश में लॉगरिदम ले सकते हैं; उदाहरण के लिए x86 में FYL2X और FYL2XP1 निर्देश हैं। हालांकि आम तौर पर इन की तरह निर्देश केवल कुछ निश्चित आधार में लघुगणक ले जाएगा, वे इस तथ्य का उपयोग करके मनमाने ढंग से अड्डों में लघुगणक लेने के लिए है कि

लॉग _एक ख = लोग इन _ग ख/log _{इस्तेमाल किया जा सकता सी}

बस दो लॉगरिदम लेकर और अपना भाग्य ढूंढकर।

सामान्य पूर्णांक (मनमानी परिशुद्धता के लिए) के लिए, आप केवल ओ (लॉग लॉग एन) अंकगणितीय परिचालनों का उपयोग करके लॉगरिदम लेने के लिए बाइनरी खोज के साथ बार-बार स्क्वायरिंग का उपयोग कर सकते हैं (प्रत्येक बार जब आप एक संख्या को चौकोर करते हैं जिसे आप एक्सपोनेंट को दोगुना करते हैं, जिसका अर्थ है इससे पहले कि आप इसके मूल्य को पार कर चुके हैं और बाइनरी खोज कर सकते हैं, आप केवल संख्या लॉग लॉग एन बार स्क्वायर कर सकते हैं)। some cute tricks with Fibonacci numbers का उपयोग करके, आप इसे केवल ओ (लॉग एन) स्पेस में कर सकते हैं। यदि आप binary logarithm की गणना कर रहे हैं, तो कुछ प्यारी चालें हैं जिन्हें आप कम समय में मूल्य की गणना करने के लिए बिट शिफ्ट के साथ उपयोग कर सकते हैं (हालांकि एसिम्प्टोटिक जटिलता समान है)।

मनमाना वास्तविक संख्या के लिए तर्क कठिन है। आप एक निश्चित परिशुद्धता के भीतर लॉगरिदम की गणना करने के लिए न्यूटन की विधि या टेलर श्रृंखला का उपयोग कर सकते हैं, हालांकि मैं कबूल करता हूं कि मैं ऐसा करने के तरीकों से परिचित नहीं हूं। हालांकि, आपको शायद ही कभी ऐसा करने की आवश्यकता है क्योंकि अधिकांश वास्तविक संख्या आईईईई युगल हैं और उस मामले में बेहतर एल्गोरिदम (या हार्डवेयर निर्देश भी) हैं।

आशा है कि इससे मदद मिलती है!