बाइनरी लघुगणक
गणित में, द्विआधारी लघुगणक (log2 n) वह घातांक है जिस तक संख्या {{math|2} को n मान प्राप्त करने के लिए उठाया जाना चाहिए। अर्थात्, किसी भी वास्तविक संख्या x के लिए,
उदाहरण के लिए, 1 का द्विआधारी लघुगणक 0 है , 2 का द्विआधारी लघुगणक 1 है , 4 का द्विआधारी लघुगणक 2 है, और 32 का द्विआधारी लघुगणक 5 है।
द्विआधारी लघुगणक आधार 2 का लघुगणक है और दो फलन की घातांक का व्युत्क्रम फलन है। log2 के साथ-साथ द्विआधारी लघुगणक के लिए वैकल्पिक अंकन lb है (आईएसओ 31-11 और आईएसओ 80000-2 द्वारा पसंदीदा अंकन)।
ऐतिहासिक रूप से, लियोनहार्ड यूलर द्वारा द्विआधारी लघुगणक का पहला प्रयोग संगीत सिद्धांत में था: दो संगीत स्वरों के आवृत्ति अनुपात के द्विआधारी लघुगणक सप्तक की संख्या देता है जिसके द्वारा स्वर भिन्न होते हैं। द्विआधारी लघुगणक में किसी संख्या के प्रतिनिधित्व की लंबाई, या सूचना सिद्धांत में संदेश को एन्कोड करने के लिए आवश्यक द्वयंक की संख्या की गणना करने के लिए द्विआधारी लघुगणक का उपयोग किया जा सकता है। कंप्यूटर विज्ञान में, वे द्विआधारी खोज और संबंधित कलन विधि के लिए आवश्यक चरणों की संख्या की गणना करते हैं। अन्य क्षेत्र जिसमें द्विआधारी लघुगणक का अधिकांशतः उपयोग किया जाता है, इसमें क्रमचय-संचय, जैव सूचना विज्ञान, स्पोर्ट्स टूर्नामेंट के डिजाइन और छायाचित्र )(फोटोग्राफी) सम्मिलित हैं।
द्विआधारी लघुगणक मानक सी गणितीय फलन और अन्य गणितीय सॉफ्टवेयर पैकेजों में सम्मिलित हैं। द्विआधारी लघुगणक का पूर्णांक भाग एक पूर्णांक मान पर पहले समुच्चय ऑपरेशन खोज का उपयोग करके या फ्लोटिंग पॉइंट मान के घातांक को देखकर पाया जा सकता है। लघुगणक के भिन्नात्मक भाग की कुशलता से गणना की जा सकती है।
इतिहास
प्राचीन काल से दो की घातांक ज्ञात है; उदाहरण के लिए, वे यूक्लिड के तत्वों, प्रॉप्स IX.32 (दो की घातांक के गुणनखंडन पर) और IX.36 (यूक्लिड-यूलर प्रमेय का आधा, सम पूर्ण संख्याओं की संरचना पर) में दिखाई देते हैं। और दो की घातांक का द्विआधारी लघुगणक दो की घातांक के क्रमबद्ध क्रम में इसकी स्थिति है। इस आधार पर, माइकल स्टिफेल को 1544 में द्विआधारी लघुगणक की पहली ज्ञात तालिका प्रकाशित करने का श्रेय दिया जाता है। उनकी पुस्तक अरिथमेटिका इंटेग्रा में कई तालिकाएँ हैं जो पूर्णांक को उनकी दो की संबंधित घातांक के साथ दिखाती हैं। इन तालिकाओं की पंक्तियों को उलटने से उन्हें द्विआधारी लघुगणक की तालिकाओं के रूप में व्याख्या करने की अनुमति मिलती है।[1][2]
स्टिफ़ेल से पहले, 8वीं शताब्दी के जैन गणितज्ञ वीरसेना को द्विआधारी लघुगणक के अग्रदूत के रूप में श्रेय दिया जाता है। वीरसेना की अर्धचेड़ा की अवधारणा को परिभाषित किया गया है कि किसी संख्या को कितनी बार दो से समान रूप से विभाजित किया जा सकता है। यह परिभाषा एक ऐसे फलन को उदित होती है जो दो की घात पर द्विआधारी लघुगणक के साथ मेल खाता है,[3] लेकिन यह अन्य पूर्णांकों के लिए अलग है, जो लघुगणक के अतिरिक्त 2-एडिक ऑर्डर देता है[4]
द्विआधारी लघुगणक का आधुनिक रूप, किसी भी संख्या (न केवल दो की घात) पर लागू होने पर 1739 में लियोनहार्ड यूलर द्वारा स्पष्ट रूप से विचार किया गया था। यूलर ने सूचना सिद्धांत और कंप्यूटर विज्ञान में उनके अनुप्रयोगों के बनने से बहुत पहले, संगीत सिद्धांत के लिए द्विआधारी लघुगणक के अनुप्रयोग की स्थापना ज्ञात की थी। इस क्षेत्र में अपने काम के हिस्से के रूप में, यूलर ने 1 से 8 तक पूर्णांकों के द्विआधारी लघुगणकों की तालिका प्रकाशित की, जो सटीकता के सात दशमलव अंकों तक है।[5][6]
परिभाषा और गुण
द्विआधारी लघुगणक फलन को दो फलन की घात के व्युत्क्रम फलन के रूप में परिभाषित किया जा सकता है, जो धनात्मक वास्तविक संख्याओं पर कड़ाई से बढ़ता हुआ फलन है और इसलिए इसका अनूठा व्युत्क्रम होता है।[7] वैकल्पिक रूप से, इसे ln n/ln 2 परिभाषित किया जा सकता है , जहाँ ln प्राकृतिक लघुगणक है, जिसे इसके किसी भी मानक तरीके से परिभाषित किया गया है। इस परिभाषा में समिश्र लघुगणक का उपयोग करने से द्विआधारी लघुगणक को समिश्र संख्याओं तक बढ़ाया जा सकता है।[8]
अन्य लघुगणकों की तरह, द्विआधारी लघुगणक निम्नलिखित समीकरणों का पालन करता है, जिसका उपयोग उन सूत्रों को सरल बनाने के लिए किया जा सकता है जो गुणन या घातांक के साथ द्विआधारी लघुगणकों को जोड़ते हैं:[9]
अधिक जानकारी के लिए, लघुगणकीय सर्वसमिकाओं की सूची देखें।
अंकन पद्धति
गणित में, किसी संख्या का द्विआधारी लघुगणक n को अधिकांशतः इस रूप log2 n में लिखा जाता है .[10] हालाँकि, विशेष रूप से अनुप्रयोग क्षेत्रों में इस फलन के लिए कई अन्य अंकन पद्धति का उपयोग या प्रस्तावित किया गया है।
कुछ लेखक द्विआधारी लघुगणक को lg n इस रूप में लिखते हैं,[11][12] स्टाइल का शिकागो मैनुअल में सूचीबद्ध अंकन[13] डोनाल्ड नुथ इस अंकन का श्रेय एडवर्ड रींगोल्ड के सुझाव को देते हैं,[14] लेकिन सूचना सिद्धांत और कंप्यूटर विज्ञान दोनों में इसका उपयोग रींगोल्ड के सक्रिय होने से पहले का है।[15][16] द्विआधारी लघुगणक को log n इस रूप में भी लिखा गया है पूर्व कथन के साथ कि लघुगणक के लिए व्यतिक्रम आधार 2 है[17][18][19] एक अन्य अंकन जो अधिकांशतः एक ही कार्य के लिए उपयोग किया जाता है (विशेष रूप से जर्मन वैज्ञानिक साहित्य में) ld n,[20][21][22] लैटिन लॉगरिथमस डुअलिस[20]या लॉगरिथमस डायडिस से है।[20]डीआईएन 1302,आईएसओ 31-11 और आईएसओ 80000-2 मानक एक और अंकन की अनुशंसा करते हैं, एलबी एन। इन मानकों के अनुसार, lg n का उपयोग द्विआधारी लघुगणक के लिए नहीं किया जाना चाहिए, क्योंकि यह सामान्य लघुगणक log10 n के लिए आरक्षित है।[23][24][25]
अनुप्रयोग
सूचना सिद्धांत
किसी धनात्मक पूर्णांक n के द्विआधारी निरूपण में अंकों (बिट्स) की संख्या 1 + log2 n का अभिन्न अंग है, अर्थात[12]
बिट को सूचना की मौलिक इकाइयां बनाने के लिए सूचना सिद्धांत में, स्व-सूचना और सूचना एन्ट्रॉपी की मात्रा की परिभाषा अधिकांशतः द्विआधारी लघुगणक के साथ व्यक्त की जाती है। इन इकाइयों के साथ, शैनन-हार्टले प्रमेय चैनल की सूचना क्षमता को इसके संकेत रव अनुपात के द्विआधारी लघुगणक, प्लस वन के रूप में व्यक्त करता है। हालाँकि, प्राकृतिक लघुगणक और नेट (यूनिट) का उपयोग इन परिभाषाओं के लिए वैकल्पिक संकेतन में भी किया जाता है।[26]
साहचर्य (कॉम्बिनेटरिक्स)
हालांकि प्राकृतिक लघुगणक शुद्ध गणित के कई क्षेत्रों जैसे संख्या सिद्धांत और गणितीय विश्लेषण में द्विआधारी लघुगणक से अधिक महत्वपूर्ण है,[27] कॉम्बिनेटरिक्स में द्विआधारी लघुगणक के कई अनुप्रयोग हैं:
- हर बाइनरी ट्री के साथ n पर्ण की ऊँचाई कम से कम log2 n होती है , समानता के साथ जब n दो की घातांक है और ट्री पूर्ण बाइनरी ट्री है।[28] संबंधित रूप से, n उपनदी धाराओं के साथ नदी तंत्र (रिवर सिस्टम) की स्ट्रालर संख्या अधिकतम log2 n + 1[29]
- n अलग-अलग समुच्चय वाले समुच्चय के प्रत्येक परिवार में कम से कम log2 n तत्व संघ में होते हैं, समानता के साथ जब वर्ग पावर समुच्चय होता है।[30]
- प्रत्येक आंशिक घन के साथ n कोने में कम से कम सममितीय आयाम होता है log2 n, और अधिक से अधिक है 1/2 n log2 n किनारे, समानता के साथ जब आंशिक घन हाइपरक्यूब ग्राफ है।[31]
- रैमसे के प्रमेय के अनुसार, हर n-वर्टेक्स अप्रत्यक्ष ग्राफ में या तो एक क्लिक (ग्राफ सिद्धांत) या आकार लॉगरिदमिक का स्वतंत्र समुच्चय (ग्राफ सिद्धांत) n है, सटीक आकार जिसकी गारंटी दी जा सकती है, ज्ञात नहीं है, लेकिन इसके आकार पर ज्ञात सर्वोत्तम सीमाओं में द्विआधारी लघुगणक सम्मिलित हैं। विशेष रूप से, सभी ग्राफ़ में कम से कम आकार का समूह या स्वतंत्र समुच्चय होता है 1/2 log2 n (1 − o(1)) और लगभग सभी ग्राफ़ों में 2 log2 n (1 + o(1)) से बड़े आकार का एक समूह या स्वतंत्र समुच्चय नहीं होता है।[32]
- यादृच्छिक फेरबदल के गिल्बर्ट-शैनन-रीड्स मॉडल के गणितीय विश्लेषण से, कोई यह दिखा सकता है कि राइफल फेरबदल का उपयोग करके कार्ड के n-कार्ड डेक को कितनी बार घुमाने की आवश्यकता होती है, क्रमपरिवर्तन पर वितरण प्राप्त करने के लिए जो करीब है समान रूप से यादृच्छिक, लगभग है 3/2 log2 n. यह गणना एक सिफारिश के लिए आधार बनाती है कि 52-कार्ड डेक को सात बार फेरना चाहिए।[33]
अभिकलनात्मक जटिलता
कलन विधि के विश्लेषण में द्विआधारी लघुगणक भी अधिकांशतः दिखाई देता है,[19]न केवल कलन विधि में द्विआधारी नंबर अंकगणित के लगातार उपयोग के कारण, बल्कि इसलिए भी कि द्विआधारी लघुगणक दो-तरफ़ा द्विभाजन के आधार पर कलन विधि के विश्लेषण में होते हैं।[14] यदि प्रारम्भ में कोई समस्या है n इसके समाधान के लिए विकल्प, और कलन विधि का प्रत्येक पुनरावृत्ति विकल्पों की संख्या को दो के कारक से कम कर देता है, फिर एकल विकल्प का चयन करने के लिए आवश्यक पुनरावृत्तियों की संख्या फिर से अभिन्न अंगlog2 n है। इस विचार का उपयोग कई कलन विधि और आंकड़ा संरचनाओं के विश्लेषण में किया जाता है। उदाहरण के लिए, द्विआधारी खोज में, हल की जाने वाली समस्या का आकार प्रत्येक पुनरावृत्ति के साथ आधा हो जाता है, और इसलिए मोटे तौर पर log2 n आकार की समस्या का समाधान प्राप्त करने के लिए पुनरावृत्तियों n की आवश्यकता होती है,[34] इसी तरह, पूरी तरह से संतुलित द्विआधारी सर्च ट्री युक्त n तत्वों की ऊंचाई log2(n + 1) − 1 है।[35]
कलन विधि का चलने का समय सामान्यतः बिग ओ अंकन पद्धति में व्यक्त किया जाता है, जिसका उपयोग उनके निरंतर कारकों और निचले क्रम के शब्दों को छोड़कर अभिव्यक्ति को सरल बनाने के लिए किया जाता है। क्योंकि अलग-अलग आधारों में लघुगणक एक दूसरे से केवल एक स्थिर कारक द्वारा भिन्न होते हैं, कलन विधि जो चलते हैं O(log2 n) समय में चलते हैं, उन्हें O(log13 n) समय में चलाने के लिए भी कहा जा सकता है। इसलिए O(log n) या O(n log n) जैसे भावों में लघुगणक का आधार महत्वपूर्ण नहीं है और इसे छोड़ा जा सकता है।[11][36] हालाँकि, लघुगणक के लिए जो समयबद्ध घातांक में दिखाई देते हैं, लघुगणक के आधार को छोड़ा नहीं जा सकता है। उदाहरण के लिए, O(2log2 n) के समान नहीं है O(2ln n) क्योंकि पूर्व O(n) के बराबर है और बाद वाला O(n0.6931...).
के बराबर है।
रनिंग टाइमO(n log n) के साथ कलन विधि को कभी-कभी रैखिकगणक कहा जाता है।[37] रनिंग टाइम के साथ कलन विधि के कुछ उदाहरण O(log n) या O(n log n) हैं:
- क्विक सॉर्ट और अन्य तुलना सॉर्ट कलन विधि[38]
- संतुलित द्विआधारी सर्च ट्री में खोज[39]
- वर्ग करके घातांक[40]
- सबसे लंबे समय तक बढ़ने वाला क्रम[41]
द्विआधारी लघुगणक भी कुछ विभाजित और जीत कलन विधि के लिए समय सीमा के घातांक में होते हैं, जैसे गुणा करने के लिए करत्सुबा कलन विधि n-बिट संख्या समय में O(nlog2 3),[42]और गुणा करने के लिए स्ट्रैसन एल्गोरिथ्म n × n समय में मेट्रिसेस O(nlog2 7) हैं[43] इन चल रहे समयों में द्विआधारी लघुगणक की घटना को मास्टर प्रमेय (कलन विधि का विश्लेषण) के संदर्भ में विभाजन और जीत पुनरावृत्ति के लिए मास्टर प्रमेय समझाया जा सकता है |
जैव सूचना विज्ञान
जैव सूचना विज्ञान में, माइक्रोएरे का उपयोग यह मापने के लिए किया जाता है कि जैविक सामग्री के नमूने में कितनी तीव्रता से विभिन्न जीन व्यक्त किए गए हैं। एक जीन की अभिव्यक्ति की विभिन्न दरों की तुलना अधिकांशतः अभिव्यक्ति दरों के अनुपात के द्विआधारी लघुगणक का उपयोग करके की जाती है: दो अभिव्यक्ति दरों के लॉग अनुपात को दो दरों के अनुपात के द्विआधारी लघुगणक के रूप में परिभाषित किया जाता है। द्विआधारी लघुगणक अभिव्यक्ति दरों की सुविधाजनक तुलना की अनुमति देते हैं: दोगुनी अभिव्यक्ति दर को 1 लॉग अनुपात द्वारा वर्णित किया जा सकता है, एक आधी अभिव्यक्ति दर को लॉग −1अनुपात द्वारा वर्णित किया जा सकता है, और एक अपरिवर्तित अभिव्यक्ति दर को को एक द्वारा वर्णित किया जा सकता है। उदाहरण के लिए शून्य का लॉग अनुपात है।[44]
इस तरह से प्राप्त आंकड़ा बिंदुओं को अधिकांशतः स्कैटर प्लॉट के रूप में देखा जाता है जिसमें एक या दोनों समन्वय अक्ष तीव्रता अनुपात के द्विआधारी लघुगणक होते हैं, या एमए प्लॉट और आरए क्षेत्र जैसे दृश्यकरण में जो इन लॉग अनुपात स्कैटरप्लॉट को घुमाते और मापक्रम करते हैं।[45]
संगीत सिद्धांत
संगीत सिद्धांत में, अंतराल (संगीत) या दो स्वरों के बीच अवधारणात्मक अंतर उनकी आवृत्तियों के अनुपात से निर्धारित होता है। छोटे द्वयंक और भाजक के साथ तर्कसंगत संख्या अनुपात से आने वाले अंतराल को विशेष रूप से सुरीले रूप में माना जाता है। इन अंतरालों में सबसे सरल और सबसे महत्वपूर्ण सप्तक है, जिसका आवृत्ति अनुपात 2:1. सप्तक की संख्या जिसके द्वारा दो स्वर भिन्न होते हैं, उनके आवृत्ति अनुपात का द्विआधारी लघुगणक होता है।[46]
ट्यूनिंग सिस्टम और संगीत सिद्धांत के अन्य पहलुओं का अध्ययन करने के लिए जो स्वरों के बीच बेहतर भेद की आवश्यकता होती है, अंतराल के आकार का माप होना सहायक होता है जो सप्तक से बेहतर होता है और गुणात्मक (आवृत्ति के रूप में) के अतिरिक्त योगात्मक होता है। अनुपात हैं)। अर्थात्, यदि स्वर x, y, और z स्वरों का आरोही क्रम बनाते हैं, तो x को y के अंतराल का माप और y को z के अंतराल का माप x को z के अंतराल के माप के बराबर होना चाहिए। ऐसा माप सेंट (संगीत) द्वारा दिया जाता है, जो सप्तक को 1200 समान अंतरालों (प्रत्येक 100 सेंट के 12 सेमीटोन) में विभाजित करता है। गणितीय रूप से f1 और f2, आवृत्तियों के साथ दिए गए स्वर, f1 को f2 के अंतराल में सेंट की संख्या है[46]:
एक हजार सप्तक को उसी तरह परिभाषित किया गया है, लेकिन 1200 के अतिरिक्त 1000 के गुणक के साथ परिभाषित किया गया है।[47]
स्पोर्ट्स शेड्यूलिंग
प्रत्येक खेल या मैच में दो खिलाड़ियों या टीमों को सम्मिलित करने वाले प्रतिस्पर्धी खेलों और खेलों में, द्विआधारी लघुगणक विजेता को निर्धारित करने के लिए आवश्यक एकल-उन्मूलन टूर्नामेंट में आवश्यक पूर्णंक की संख्या को इंगित करता है। उदाहरण के लिए, 4 खिलाड़ियों के टूर्नामेंट में विजेता का निर्धारण करने के लिए log2 4 = 2 पूर्णंक की आवश्यकता होती है, 32 टीमों के एक टूर्नामेंट के लिए log2 32 = 5 पूर्णंक की आवश्यकता होती है, आदि। इस मामले में, n खिलाड़ी/टीम जहां n 2 की घातांक नहीं है, log2 n पूर्णंक अप किया गया है क्योंकि कम से कम पूर्णंक होना आवश्यक है जिसमें सभी शेष प्रतियोगी नहीं खेलते हैं। उदाहरण के लिए, log2 6 लगभग 2.585 है, जो 3 तक पूर्णंक करता है, यह दर्शाता है कि 6 टीमों के एक टूर्नामेंट के लिए 3 पूर्णंक की आवश्यकता होती है (या तो दो टीमें पहले पूर्णंक से बाहर हो जाती हैं, या एक टीम दूसरे पूर्णंक से बाहर हो जाती है)। स्विस-सिस्टम टूर्नामेंट में स्पष्ट विजेता का निर्धारण करने के लिए समान संख्या में पूर्णंक भी आवश्यक हैं।[48]
छायाचित्र (फोटोग्राफी)
फ़ोटोग्राफ़ी में, अनावृत्ति मान को वेबर-फेचनर कानून के अनुसार, फिल्म या सेंसर तक पहुँचने वाले प्रकाश की मात्रा के द्विआधारी लघुगणक के संदर्भ में मापा जाता है, जो प्रकाश के लिए मानव दृश्य प्रणाली के लघुगणकीय प्रतिक्रिया का वर्णन करता है। अनावृत्ति का सिंगल स्टॉप आधार -2 लघुगणकीय पैमाने पर एक इकाई है।[49][50] अधिक सटीक रूप से, छायाचित्र के अनावृत्ति मान को इस रूप में परिभाषित किया गया है
जहाँ N अनावृत्ति के दौरान लेंस के द्वारक को मापने वाला