बाइनरी लघुगणक

log 2 x

का ग्राफ धनात्मक वास्तविक संख्या के फलन

x

के रूप में

गणित में, द्विआधारी लघुगणक ( $log 2 n$ ) वह घातांक है जिस तक संख्या {{math|2} को $n$ मान प्राप्त करने के लिए उठाया जाना चाहिए। अर्थात्, किसी भी वास्तविक संख्या $x$ के लिए,

x=\log _{2}n\quad \Longleftrightarrow \quad 2^{x}=n.

उदाहरण के लिए, $1$ का द्विआधारी लघुगणक $0$ है , $2$ का द्विआधारी लघुगणक $1$ है , $4$ का द्विआधारी लघुगणक $2$ है, और $32$ का द्विआधारी लघुगणक $5$ है।

द्विआधारी लघुगणक आधार $2$ का लघुगणक है और दो फलन की घातांक का व्युत्क्रम फलन है। $log 2$ के साथ-साथ द्विआधारी लघुगणक के लिए वैकल्पिक अंकन $lb$ है (आईएसओ 31-11 और आईएसओ 80000-2 द्वारा पसंदीदा अंकन)।

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

द्विआधारी लघुगणक मानक सी गणितीय फलन और अन्य गणितीय सॉफ्टवेयर पैकेजों में सम्मिलित हैं। द्विआधारी लघुगणक का पूर्णांक भाग एक पूर्णांक मान पर पहले समुच्चय ऑपरेशन खोज का उपयोग करके या फ्लोटिंग पॉइंट मान के घातांक को देखकर पाया जा सकता है। लघुगणक के भिन्नात्मक भाग की कुशलता से गणना की जा सकती है।

इतिहास

लियोनहार्ड यूलर 1739 में संगीत सिद्धांत के लिए द्विआधारी लघुगणक लागू करने वाले पहले व्यक्ति थे।

प्राचीन काल से दो की घातांक ज्ञात है; उदाहरण के लिए, वे यूक्लिड के तत्वों, प्रॉप्स IX.32 (दो की घातांक के गुणनखंडन पर) और IX.36 (यूक्लिड-यूलर प्रमेय का आधा, सम पूर्ण संख्याओं की संरचना पर) में दिखाई देते हैं। और दो की घातांक का द्विआधारी लघुगणक दो की घातांक के क्रमबद्ध क्रम में इसकी स्थिति है। इस आधार पर, माइकल स्टिफेल को 1544 में द्विआधारी लघुगणक की पहली ज्ञात तालिका प्रकाशित करने का श्रेय दिया जाता है। उनकी पुस्तक अरिथमेटिका इंटेग्रा में कई तालिकाएँ हैं जो पूर्णांक को उनकी दो की संबंधित घातांक के साथ दिखाती हैं। इन तालिकाओं की पंक्तियों को उलटने से उन्हें द्विआधारी लघुगणक की तालिकाओं के रूप में व्याख्या करने की अनुमति मिलती है।^[1]^[2]

स्टिफ़ेल से पहले, 8वीं शताब्दी के जैन गणितज्ञ वीरसेना को द्विआधारी लघुगणक के अग्रदूत के रूप में श्रेय दिया जाता है। वीरसेना की अर्धचेड़ा की अवधारणा को परिभाषित किया गया है कि किसी संख्या को कितनी बार दो से समान रूप से विभाजित किया जा सकता है। यह परिभाषा एक ऐसे फलन को उदित होती है जो दो की घात पर द्विआधारी लघुगणक के साथ मेल खाता है,^[3] लेकिन यह अन्य पूर्णांकों के लिए अलग है, जो लघुगणक के अतिरिक्त 2-एडिक ऑर्डर देता है^[4]

द्विआधारी लघुगणक का आधुनिक रूप, किसी भी संख्या (न केवल दो की घात) पर लागू होने पर 1739 में लियोनहार्ड यूलर द्वारा स्पष्ट रूप से विचार किया गया था। यूलर ने सूचना सिद्धांत और कंप्यूटर विज्ञान में उनके अनुप्रयोगों के बनने से बहुत पहले, संगीत सिद्धांत के लिए द्विआधारी लघुगणक के अनुप्रयोग की स्थापना ज्ञात की थी। इस क्षेत्र में अपने काम के हिस्से के रूप में, यूलर ने 1 से 8 तक पूर्णांकों के द्विआधारी लघुगणकों की तालिका प्रकाशित की, जो सटीकता के सात दशमलव अंकों तक है।^[5]^[6]

परिभाषा और गुण

द्विआधारी लघुगणक फलन को दो फलन की घात के व्युत्क्रम फलन के रूप में परिभाषित किया जा सकता है, जो धनात्मक वास्तविक संख्याओं पर कड़ाई से बढ़ता हुआ फलन है और इसलिए इसका अनूठा व्युत्क्रम होता है।^[7] वैकल्पिक रूप से, इसे $ln n /ln 2$ परिभाषित किया जा सकता है , जहाँ $ln$ प्राकृतिक लघुगणक है, जिसे इसके किसी भी मानक तरीके से परिभाषित किया गया है। इस परिभाषा में समिश्र लघुगणक का उपयोग करने से द्विआधारी लघुगणक को समिश्र संख्याओं तक बढ़ाया जा सकता है।^[8]

अन्य लघुगणकों की तरह, द्विआधारी लघुगणक निम्नलिखित समीकरणों का पालन करता है, जिसका उपयोग उन सूत्रों को सरल बनाने के लिए किया जा सकता है जो गुणन या घातांक के साथ द्विआधारी लघुगणकों को जोड़ते हैं:^[9]

\log _{2}xy=\log _{2}x+\log _{2}y

\log _{2}{\frac {x}{y}}=\log _{2}x-\log _{2}y

\log _{2}x^{y}=y\log _{2}x.

अधिक जानकारी के लिए, लघुगणकीय सर्वसमिकाओं की सूची देखें।

अंकन पद्धति

गणित में, किसी संख्या का द्विआधारी लघुगणक $n$ को अधिकांशतः इस रूप $log 2 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 का उपयोग द्विआधारी लघुगणक के लिए नहीं किया जाना चाहिए, क्योंकि यह सामान्य लघुगणक $log 10 n$ के लिए आरक्षित है।^[23]^[24]^[25]

अनुप्रयोग

सूचना सिद्धांत

किसी धनात्मक पूर्णांक $n$ के द्विआधारी निरूपण में अंकों (बिट्स) की संख्या $1 + log 2 n$ का अभिन्न अंग है, अर्थात^[12]

\lfloor \log _{2}n\rfloor +1.

बिट को सूचना की मौलिक इकाइयां बनाने के लिए सूचना सिद्धांत में, स्व-सूचना और सूचना एन्ट्रॉपी की मात्रा की परिभाषा अधिकांशतः द्विआधारी लघुगणक के साथ व्यक्त की जाती है। इन इकाइयों के साथ, शैनन-हार्टले प्रमेय चैनल की सूचना क्षमता को इसके संकेत रव अनुपात के द्विआधारी लघुगणक, प्लस वन के रूप में व्यक्त करता है। हालाँकि, प्राकृतिक लघुगणक और नेट (यूनिट) का उपयोग इन परिभाषाओं के लिए वैकल्पिक संकेतन में भी किया जाता है।^[26]

साहचर्य (कॉम्बिनेटरिक्स)

एक पूर्ण बाइनरी ट्री की संरचना के साथ एक 16-खिलाड़ी एकल उन्मूलन ब्रैकेट (टूर्नामेंट)। पेड़ की ऊंचाई (टूर्नामेंट के दौरों की संख्या) खिलाड़ियों की संख्या का द्विआधारी लघुगणक है, जो एक पूर्णांक तक वक्रण है।

हालांकि प्राकृतिक लघुगणक शुद्ध गणित के कई क्षेत्रों जैसे संख्या सिद्धांत और गणितीय विश्लेषण में द्विआधारी लघुगणक से अधिक महत्वपूर्ण है,^[27] कॉम्बिनेटरिक्स में द्विआधारी लघुगणक के कई अनुप्रयोग हैं:

हर बाइनरी ट्री के साथ $n$ पर्ण की ऊँचाई कम से कम $log 2 n$ होती है , समानता के साथ जब $n$ दो की घातांक है और ट्री पूर्ण बाइनरी ट्री है।^[28] संबंधित रूप से, $n$ उपनदी धाराओं के साथ नदी तंत्र (रिवर सिस्टम) की स्ट्रालर संख्या अधिकतम $log 2 n + 1$ ^[29]
$n$ अलग-अलग समुच्चय वाले समुच्चय के प्रत्येक परिवार में कम से कम $log 2 n$ तत्व संघ में होते हैं, समानता के साथ जब वर्ग पावर समुच्चय होता है।^[30]
प्रत्येक आंशिक घन के साथ $n$ कोने में कम से कम सममितीय आयाम होता है $log 2 n$ , और अधिक से अधिक है $.mw-parser-output .sfrac{white-space:nowrap}.mw-parser-output .sfrac.tion,.mw-parser-output .sfrac .tion{display:inline-block;vertical-align:-0.5em;font-size:85%;text-align:center}.mw-parser-output .sfrac .num,.mw-parser-output .sfrac .den{display:block;line-height:1em;margin:0 0.1em}.mw-parser-output .sfrac .den{border-top:1px solid}.mw-parser-output .sr-only{border:0;clip:rect(0,0,0,0);height:1px;margin:-1px;overflow:hidden;padding:0;position:absolute;width:1px}1/2 n log2 n$ किनारे, समानता के साथ जब आंशिक घन हाइपरक्यूब ग्राफ है।^[31]
रैमसे के प्रमेय के अनुसार, हर $n$ -वर्टेक्स अप्रत्यक्ष ग्राफ में या तो एक क्लिक (ग्राफ सिद्धांत) या आकार लॉगरिदमिक का स्वतंत्र समुच्चय (ग्राफ सिद्धांत) $n$ है, सटीक आकार जिसकी गारंटी दी जा सकती है, ज्ञात नहीं है, लेकिन इसके आकार पर ज्ञात सर्वोत्तम सीमाओं में द्विआधारी लघुगणक सम्मिलित हैं। विशेष रूप से, सभी ग्राफ़ में कम से कम आकार का समूह या स्वतंत्र समुच्चय होता है $1 / 2 log 2 n (1 - o (1))$ और लगभग सभी ग्राफ़ों में $2 log 2 n (1 + o (1))$ से बड़े आकार का एक समूह या स्वतंत्र समुच्चय नहीं होता है।^[32]
यादृच्छिक फेरबदल के गिल्बर्ट-शैनन-रीड्स मॉडल के गणितीय विश्लेषण से, कोई यह दिखा सकता है कि राइफल फेरबदल का उपयोग करके कार्ड के n-कार्ड डेक को कितनी बार घुमाने की आवश्यकता होती है, क्रमपरिवर्तन पर वितरण प्राप्त करने के लिए जो करीब है समान रूप से यादृच्छिक, लगभग है $3 / 2 log 2 n$ . यह गणना एक सिफारिश के लिए आधार बनाती है कि 52-कार्ड डेक को सात बार फेरना चाहिए।^[33]

अभिकलनात्मक जटिलता

एक क्रमबद्ध सरणी में द्विआधारी खोज, एक कलन विधि जिसकी समय जटिलता में द्विआधारी लघुगणक सम्मिलित है

कलन विधि के विश्लेषण में द्विआधारी लघुगणक भी अधिकांशतः दिखाई देता है,^[19]न केवल कलन विधि में द्विआधारी नंबर अंकगणित के लगातार उपयोग के कारण, बल्कि इसलिए भी कि द्विआधारी लघुगणक दो-तरफ़ा द्विभाजन के आधार पर कलन विधि के विश्लेषण में होते हैं।^[14] यदि प्रारम्भ में कोई समस्या है $n$ इसके समाधान के लिए विकल्प, और कलन विधि का प्रत्येक पुनरावृत्ति विकल्पों की संख्या को दो के कारक से कम कर देता है, फिर एकल विकल्प का चयन करने के लिए आवश्यक पुनरावृत्तियों की संख्या फिर से अभिन्न अंग $log 2 n$ है। इस विचार का उपयोग कई कलन विधि और आंकड़ा संरचनाओं के विश्लेषण में किया जाता है। उदाहरण के लिए, द्विआधारी खोज में, हल की जाने वाली समस्या का आकार प्रत्येक पुनरावृत्ति के साथ आधा हो जाता है, और इसलिए मोटे तौर पर $log 2 n$ आकार की समस्या का समाधान प्राप्त करने के लिए पुनरावृत्तियों $n$ की आवश्यकता होती है,^[34] इसी तरह, पूरी तरह से संतुलित द्विआधारी सर्च ट्री युक्त $n$ तत्वों की ऊंचाई $log 2 (n + 1) - 1$ है।^[35]

कलन विधि का चलने का समय सामान्यतः बिग ओ अंकन पद्धति में व्यक्त किया जाता है, जिसका उपयोग उनके निरंतर कारकों और निचले क्रम के शब्दों को छोड़कर अभिव्यक्ति को सरल बनाने के लिए किया जाता है। क्योंकि अलग-अलग आधारों में लघुगणक एक दूसरे से केवल एक स्थिर कारक द्वारा भिन्न होते हैं, कलन विधि जो चलते हैं $O (log 2 n)$ समय में चलते हैं, उन्हें $O (log 13 n)$ समय में चलाने के लिए भी कहा जा सकता है। इसलिए $O (log n)$ या $O (n log n)$ जैसे भावों में लघुगणक का आधार महत्वपूर्ण नहीं है और इसे छोड़ा जा सकता है।^[11]^[36] हालाँकि, लघुगणक के लिए जो समयबद्ध घातांक में दिखाई देते हैं, लघुगणक के आधार को छोड़ा नहीं जा सकता है। उदाहरण के लिए, $O (2 log 2 n)$ के समान नहीं है $O (2 ln n)$ क्योंकि पूर्व $O (n)$ के बराबर है और बाद वाला $O (n 0.6931...)$ .

के बराबर है।

रनिंग टाइम $O (n log n)$ के साथ कलन विधि को कभी-कभी रैखिकगणक कहा जाता है।^[37] रनिंग टाइम के साथ कलन विधि के कुछ उदाहरण $O (log n)$ या $O (n log n)$ हैं:

क्विक सॉर्ट और अन्य तुलना सॉर्ट कलन विधि^[38]
संतुलित द्विआधारी सर्च ट्री में खोज^[39]
वर्ग करके घातांक^[40]
सबसे लंबे समय तक बढ़ने वाला क्रम^[41]

द्विआधारी लघुगणक भी कुछ विभाजित और जीत कलन विधि के लिए समय सीमा के घातांक में होते हैं, जैसे गुणा करने के लिए करत्सुबा कलन विधि $n$ -बिट संख्या समय में $O (n log 23)$ ,^[42]और गुणा करने के लिए स्ट्रैसन एल्गोरिथ्म $n \times n$ समय में मेट्रिसेस $O (n log 27)$ हैं^[43] इन चल रहे समयों में द्विआधारी लघुगणक की घटना को मास्टर प्रमेय (कलन विधि का विश्लेषण) के संदर्भ में विभाजन और जीत पुनरावृत्ति के लिए मास्टर प्रमेय समझाया जा सकता है |

जैव सूचना विज्ञान

लगभग 8700 जीनों के लिए एक माइक्रोएरे। इन जीनों की अभिव्यक्ति दरों की तुलना द्विआधारी लघुगणक का उपयोग करके की जाती है।

जैव सूचना विज्ञान में, माइक्रोएरे का उपयोग यह मापने के लिए किया जाता है कि जैविक सामग्री के नमूने में कितनी तीव्रता से विभिन्न जीन व्यक्त किए गए हैं। एक जीन की अभिव्यक्ति की विभिन्न दरों की तुलना अधिकांशतः अभिव्यक्ति दरों के अनुपात के द्विआधारी लघुगणक का उपयोग करके की जाती है: दो अभिव्यक्ति दरों के लॉग अनुपात को दो दरों के अनुपात के द्विआधारी लघुगणक के रूप में परिभाषित किया जाता है। द्विआधारी लघुगणक अभिव्यक्ति दरों की सुविधाजनक तुलना की अनुमति देते हैं: दोगुनी अभिव्यक्ति दर को $1$ लॉग अनुपात द्वारा वर्णित किया जा सकता है, एक आधी अभिव्यक्ति दर को लॉग $-1$ अनुपात द्वारा वर्णित किया जा सकता है, और एक अपरिवर्तित अभिव्यक्ति दर को को एक द्वारा वर्णित किया जा सकता है। उदाहरण के लिए शून्य का लॉग अनुपात है।^[44]

इस तरह से प्राप्त आंकड़ा बिंदुओं को अधिकांशतः स्कैटर प्लॉट के रूप में देखा जाता है जिसमें एक या दोनों समन्वय अक्ष तीव्रता अनुपात के द्विआधारी लघुगणक होते हैं, या एमए प्लॉट और आरए क्षेत्र जैसे दृश्यकरण में जो इन लॉग अनुपात स्कैटरप्लॉट को घुमाते और मापक्रम करते हैं।^[45]

संगीत सिद्धांत

संगीत सिद्धांत में, अंतराल (संगीत) या दो स्वरों के बीच अवधारणात्मक अंतर उनकी आवृत्तियों के अनुपात से निर्धारित होता है। छोटे द्वयंक और भाजक के साथ तर्कसंगत संख्या अनुपात से आने वाले अंतराल को विशेष रूप से सुरीले रूप में माना जाता है। इन अंतरालों में सबसे सरल और सबसे महत्वपूर्ण सप्तक है, जिसका आवृत्ति अनुपात $2:1$ . सप्तक की संख्या जिसके द्वारा दो स्वर भिन्न होते हैं, उनके आवृत्ति अनुपात का द्विआधारी लघुगणक होता है।^[46]

ट्यूनिंग सिस्टम और संगीत सिद्धांत के अन्य पहलुओं का अध्ययन करने के लिए जो स्वरों के बीच बेहतर भेद की आवश्यकता होती है, अंतराल के आकार का माप होना सहायक होता है जो सप्तक से बेहतर होता है और गुणात्मक (आवृत्ति के रूप में) के अतिरिक्त योगात्मक होता है। अनुपात हैं)। अर्थात्, यदि स्वर $x$ , $y$ , और $z$ स्वरों का आरोही क्रम बनाते हैं, तो $x$ को $y$ के अंतराल का माप और $y$ को $z$ के अंतराल का माप $x$ को $z$ के अंतराल के माप के बराबर होना चाहिए। ऐसा माप सेंट (संगीत) द्वारा दिया जाता है, जो सप्तक को 1200 समान अंतरालों (प्रत्येक 100 सेंट के 12 सेमीटोन) में विभाजित करता है। गणितीय रूप से $f 1$ और $f 2$ , आवृत्तियों के साथ दिए गए स्वर, $f 1$ को $f 2$ के अंतराल में सेंट की संख्या है^[46]: $\left|1200\log _{2}{\frac {f_{1}}{f_{2}}}\right|.$

एक हजार सप्तक को उसी तरह परिभाषित किया गया है, लेकिन 1200 के अतिरिक्त 1000 के गुणक के साथ परिभाषित किया गया है।^[47]

स्पोर्ट्स शेड्यूलिंग

प्रत्येक खेल या मैच में दो खिलाड़ियों या टीमों को सम्मिलित करने वाले प्रतिस्पर्धी खेलों और खेलों में, द्विआधारी लघुगणक विजेता को निर्धारित करने के लिए आवश्यक एकल-उन्मूलन टूर्नामेंट में आवश्यक पूर्णंक की संख्या को इंगित करता है। उदाहरण के लिए, $4$ खिलाड़ियों के टूर्नामेंट में विजेता का निर्धारण करने के लिए $log 2 4 = 2$ पूर्णंक की आवश्यकता होती है, $32$ टीमों के एक टूर्नामेंट के लिए $log 2 32 = 5$ पूर्णंक की आवश्यकता होती है, आदि। इस मामले में, $n$ खिलाड़ी/टीम जहां $n$ 2 की घातांक नहीं है, $log 2 n$ पूर्णंक अप किया गया है क्योंकि कम से कम पूर्णंक होना आवश्यक है जिसमें सभी शेष प्रतियोगी नहीं खेलते हैं। उदाहरण के लिए, $log 26$ लगभग $2.585$ है, जो $3$ तक पूर्णंक करता है, यह दर्शाता है कि $6$ टीमों के एक टूर्नामेंट के लिए $3$ पूर्णंक की आवश्यकता होती है (या तो दो टीमें पहले पूर्णंक से बाहर हो जाती हैं, या एक टीम दूसरे पूर्णंक से बाहर हो जाती है)। स्विस-सिस्टम टूर्नामेंट में स्पष्ट विजेता का निर्धारण करने के लिए समान संख्या में पूर्णंक भी आवश्यक हैं।^[48]

छायाचित्र (फोटोग्राफी)

फ़ोटोग्राफ़ी में, अनावृत्ति मान को वेबर-फेचनर कानून के अनुसार, फिल्म या सेंसर तक पहुँचने वाले प्रकाश की मात्रा के द्विआधारी लघुगणक के संदर्भ में मापा जाता है, जो प्रकाश के लिए मानव दृश्य प्रणाली के लघुगणकीय प्रतिक्रिया का वर्णन करता है। अनावृत्ति का सिंगल स्टॉप आधार - $2$ लघुगणकीय पैमाने पर एक इकाई है।^[49]^[50] अधिक सटीक रूप से, छायाचित्र के अनावृत्ति मान को इस रूप में परिभाषित किया गया है

\log _{2}{\frac {N^{2}}{t}}

जहाँ $N$ अनावृत्ति के दौरान लेंस के द्वारक को मापने वाला f संख्या है, और $t$ अनावृत्ति के सेकंड की संख्या है।^[51]

प्रकाश-संवेदनशील सामग्री या डिजिटल सेंसर की गतिशील रेंज को व्यक्त करने के लिए द्विआधारी लघुगणक (स्टॉप के रूप में व्यक्त) का उपयोग डेन्सिटोमीटरी में भी किया जाता है।^[52]

गणना

HP-35 वैज्ञानिक कैलकुलेटर (1972)। लॉग और ln कुंजियाँ शीर्ष पंक्ति में हैं; कोई log₂ key नहीं है।

अन्य आधारों से रूपांतरण

प्राकृतिक लघुगणक ( $ln$ ) या सामान्य लघुगणक ( $log$ या $log 10$ ) फलन का उपयोग करना उन कैलकुलेटर $log 2 n$ की गणना करने का एक आसान तरीका है, जो अधिकांश वैज्ञानिक कैलकुलेटर पर पाए जाते हैं। लघुगणक आधार को $e$ या $10$ को $2$ सूत्रों का उपयोग कर सकते हैं:^[50]^[53]

\log _{2}n={\frac {\ln n}{\ln 2}}={\frac {\log _{10}n}{\log _{10}2}},

या लगभग

\log _{2}n\approx 1.442695\ln n\approx 3.321928\log _{10}n.

पूर्णांक गोलाई

द्विआधारी लघुगणक को पूर्णांकों से और पूर्णांकों को ऊपर या नीचे वक्रण करके फलन में बनाया जा सकता है। पूर्णांक द्विआधारी लघुगणक के ये दो रूप इस सूत्र द्वारा संबंधित हैं:

\lfloor \log _{2}(n)\rfloor =\lceil \log _{2}(n+1)\rceil -1,{\text{ if }}n\geq 1.

^[54]

$\lfloor \log _{2}(0)\rfloor =-1$ परिभाषा को परिभाषित करके बढ़ाया जा सकता है, इस तरह विस्तारित, यह फलन 32-बिट अहस्ताक्षरित द्विआधारी प्रतिनिधित्व के अग्रणी शून्यों की संख्या $x$ , $nlz(x)$ से संबंधित है , .

\lfloor \log _{2}(n)\rfloor =31-\operatorname {nlz} (n).

^[54]

पूर्णांक द्विआधारी लघुगणक को को इनपुट में सबसे महत्वपूर्ण $1$ बिट के शून्य-आधारित सूचकांक के रूप में व्याख्या किया जा सकता है। इस अर्थ में यह पहले समुच्चय ऑपरेशन का पूरक है, जो कम से कम महत्वपूर्ण $1$ बिट की अनुक्रमणिका पाता है। कई हार्डवेयर प्लेटफॉर्म में अग्रणी शून्यों की संख्या, या समतुल्य संक्रियाओं को खोजने के लिए समर्थन सम्मिलित है, जिसका उपयोग द्विआधारी लघुगणक को जल्दी से खोजने के लिए किया जा सकता है। लिनक्स कर्नेल^[55] और libc सॉफ़्टवेयर लाइब्रेरी के कुछ संस्करणों में fls और flsl द्विआधारी लघुगणक (एक पूर्णांक, प्लस वन) तक की गणना भी की जाती है।

पुनरावर्ती सन्निकटन

एक सामान्य धनात्मक वास्तविक संख्या के लिए, द्विआधारी लघुगणक की गणना दो भागों में की जा सकती है।^[56] सबसे पहले, एक पूर्णांक भाग की गणना करता है, $\lfloor \log _{2}x\rfloor$ (लघुगणक की विशेषता कहा जाता है)। यह समस्या को कम कर देता है जहां लघुगणक का तर्क प्रतिबंधित सीमा, अंतराल $[1, 2)$ में है, भिन्नात्मक भाग (लघुगणक का अपूर्णांश) की गणना के दूसरे चरण को सरल बनाना (लघुगणक का मंटिसा) है। किसी भी $x > 0$ के लिए, एक अद्वितीय पूर्णांक $n$ सम्मिलित है जैसे कि $2 n \leq x < 2 n +1$ , या समकक्ष $1 \leq 2 - n x < 2$ , अब लघुगणक का पूर्णांक भाग केवल $n$ है, और भिन्नात्मक भाग $log 2 (2 - n x)$ है^[56] दूसरे शब्दों में:

\log _{2}x=n+\log _{2}y\quad {\text{where }}y=2^{-n}x{\text{ and }}y\in [1,2)

सामान्यीकृत फ्लोटिंग पॉइंट नंबरों के लिए, पूर्णांक भाग फ्लोटिंग पॉइंट घातांक द्वारा दिया जाता है,^[57] और पूर्णांकों के लिए इसे अग्रणी शून्य ऑपरेशन करके निर्धारित किया जा सकता है।^[58] समिश्र संख्या और निहित प्रकार के रूपांतरण जैसे कि मैटलैब तर्क का समर्थन करने वाले कंप्यूटिंग वातावरण में log2 फलन को ऋणात्मक संख्या होने की अनुमति एक समिश्र संख्या लौटाती है।^[59]

संदर्भ

↑ Groza, Vivian Shaw; Shelley, Susanne M. (1972), Precalculus mathematics, New York: Holt, Rinehart and Winston, p. 182, ISBN 978-0-03-077670-0.
↑ Stifel, Michael (1544), Arithmetica integra (in Latina), p. 31. A copy of the same table with two more entries appears on p. 237, and another copy extended to negative powers appears on p. 249b.
↑ Joseph, G. G. (2011), The Crest of the Peacock: Non-European Roots of Mathematics (3rd ed.), Princeton University Press, p. 352.
↑ See, e.g., Shparlinski, Igor (2013), Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness, Progress in Computer Science and Applied Logic, vol. 22, Birkhäuser, p. 35, ISBN 978-3-0348-8037-4.
↑ Euler, Leonhard (1739), "Chapter VII. De Variorum Intervallorum Receptis Appelationibus", Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae (in Latina), Saint Petersburg Academy, pp. 102–112.
↑ Tegg, Thomas (1829), "Binary logarithms", London encyclopaedia; or, Universal dictionary of science, art, literature and practical mechanics: comprising a popular view of the present state of knowledge, Volume 4, pp. 142–143.
↑ Batschelet, E. (2012), Introduction to Mathematics for Life Scientists, Springer, p. 128, ISBN 978-3-642-96080-2.
↑ For instance, Microsoft Excel provides the IMLOG2 function for complex binary logarithms: see Bourg, David M. (2006), Excel Scientific and Engineering Cookbook, O'Reilly Media, p. 232, ISBN 978-0-596-55317-3.
↑ Kolman, Bernard; Shapiro, Arnold (1982), "11.4 Properties of Logarithms", Algebra for College Students, Academic Press, pp. 334–335, ISBN 978-1-4832-7121-7.
↑ For instance, this is the notation used in the Encyclopedia of Mathematics and The Princeton Companion to Mathematics.
↑ ^{Jump up to: 11.0} ^11.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990], Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 34, 53–54, ISBN 0-262-03293-7
↑ ^{Jump up to: 12.0} ^12.1 Sedgewick, Robert; Wayne, Kevin Daniel (2011), Algorithms, Addison-Wesley Professional, p. 185, ISBN 978-0-321-57351-3.
↑ The Chicago Manual of Style (25th ed.), University of Chicago Press, 2003, p. 530.
↑ ^{Jump up to: 14.0} ^14.1 Knuth, Donald E. (1997), Fundamental Algorithms, The Art of Computer Programming, vol. 1 (3rd ed.), Addison-Wesley Professional, ISBN 978-0-321-63574-7, p. 11. The same notation was in the 1973 2nd edition of the same book (p. 23) but without the credit to Reingold.
↑ Trucco, Ernesto (1956), "A note on the information content of graphs", Bull. Math. Biophys., 18 (2): 129–135, doi:10.1007/BF02477836, MR 0077919.
↑ Mitchell, John N. (1962), "Computer multiplication and division using binary logarithms", IRE Transactions on Electronic Computers, EC-11 (4): 512–517, doi:10.1109/TEC.1962.5219391.
↑ Fiche, Georges; Hebuterne, Gerard (2013), Mathematics for Engineers, John Wiley & Sons, p. 152, ISBN 978-1-118-62333-6, In the following, and unless otherwise stated, the notation $log x$ always stands for the logarithm to the base $2$ of $x$ .
↑ Cover, Thomas M.; Thomas, Joy A. (2012), Elements of Information Theory (2nd ed.), John Wiley & Sons, p. 33, ISBN 978-1-118-58577-1, Unless otherwise specified, we will take all logarithms to base $2$ .
↑ ^{Jump up to: 19.0} ^19.1 Goodrich, Michael T.; Tamassia, Roberto (2002), Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, p. 23, One of the interesting and sometimes even surprising aspects of the analysis of data structures and algorithms is the ubiquitous presence of logarithms ... As is the custom in the computing literature, we omit writing the base $b$ of the logarithm when $b = 2$ .
↑ ^{Jump up to: 20.0} ^20.1 ^20.2 Tafel, Hans Jörg (1971), Einführung in die digitale Datenverarbeitung [Introduction to digital information processing] (in Deutsch), Munich: Carl Hanser Verlag, pp. 20–21, ISBN 3-446-10569-7
↑ Tietze, Ulrich; Schenk, Christoph (1999), Halbleiter-Schaltungstechnik (in Deutsch) (1st corrected reprint, 11th ed.), Springer Verlag, p. 1370, ISBN 3-540-64192-0
↑ Bauer, Friedrich L. (2009), Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum, Springer Science & Business Media, p. 54, ISBN 978-3-642-02991-2.
↑ For DIN 1302 see Brockhaus Enzyklopädie in zwanzig Bänden [Brockhaus Encyclopedia in Twenty Volumes] (in Deutsch), vol. 11, Wiesbaden: F.A. Brockhaus, 1970, p. 554, ISBN 978-3-7653-0000-4.
↑ For ISO 31-11 see Thompson, Ambler; Taylor, Barry M (March 2008), Guide for the Use of the International System of Units (SI) — NIST Special Publication 811, 2008 Edition — Second Printing (PDF), NIST, p. 33.
↑ For ISO 80000-2 see "Quantities and units – Part 2: Mathematical signs and symbols to be used in the natural sciences and technology" (PDF), International Standard ISO 80000-2 (1st ed.), December 1, 2009, Section 12, Exponential and logarithmic functions, p. 18.
↑ Van der Lubbe, Jan C. A. (1997), Information Theory, Cambridge University Press, p. 3, ISBN 978-0-521-46760-5.
↑ Stewart, Ian (2015), Taming the Infinite, Quercus, p. 120, ISBN 9781623654733, in advanced mathematics and science the only logarithm of importance is the natural logarithm.
↑ Leiss, Ernst L. (2006), A Programmer's Companion to Algorithm Analysis, CRC Press, p. 28, ISBN 978-1-4200-1170-8.
↑ Devroye, L.; Kruszewski, P. (1996), "On the Horton–Strahler number for random tries", RAIRO Informatique Théorique et Applications, 30 (5): 443–456, doi:10.1051/ita/1996300504431, MR 1435732.
↑ Equivalently, a family with $k$ distinct elements has at most $2 k$ distinct sets, with equality when it is a power set.
↑ Eppstein, David (2005), "The lattice dimension of a graph", European Journal of Combinatorics, 26 (5): 585–592, arXiv:cs.DS/0402028, doi:10.1016/j.ejc.2004.05.001, MR 2127682, S2CID 7482443.
↑ Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. (1980), Ramsey Theory, Wiley-Interscience, p. 78.
↑ Bayer, Dave; Diaconis, Persi (1992), "Trailing the dovetail shuffle to its lair", The Annals of Applied Probability, 2 (2): 294–313, doi:10.1214/aoap/1177005705, JSTOR 2959752, MR 1161056.
↑ Mehlhorn, Kurt; Sanders, Peter (2008), "2.5 An example – binary search", Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, pp. 34–36, ISBN 978-3-540-77977-3.
↑ Roberts, Fred; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, p. 206, ISBN 978-1-4200-9983-6.
↑ Sipser, Michael (2012), "Example 7.4", Introduction to the Theory of Computation (3rd ed.), Cengage Learning, pp. 277–278, ISBN 9781133187790.
↑ Sedgewick & Wayne (2011), p. 186.
↑ Cormen et al., p. 156; Goodrich & Tamassia, p. 238.
↑ Cormen et al., p. 276; Goodrich & Tamassia, p. 159.
↑ Cormen et al., pp. 879–880; Goodrich & Tamassia, p. 464.
↑ Edmonds, Jeff (2008), How to Think About Algorithms, Cambridge University Press, p. 302, ISBN 978-1-139-47175-6.
↑ Cormen et al., p. 844; Goodrich & Tamassia, p. 279.
↑ Cormen et al., section 28.2.
↑ Causton, Helen; Quackenbush, John; Brazma, Alvis (2009), Microarray Gene Expression Data Analysis: A Beginner's Guide, John Wiley & Sons, pp. 49–50, ISBN 978-1-4443-1156-3.
↑ Eidhammer, Ingvar; Barsnes, Harald; Eide, Geir Egil; Martens, Lennart (2012), Computational and Statistical Methods for Protein Quantification by Mass Spectrometry, John Wiley & Sons, p. 105, ISBN 978-1-118-49378-6.
↑ ^{Jump up to: 46.0} ^46.1 Campbell, Murray; Greated, Clive (1994), The Musician's Guide to Acoustics, Oxford University Press, p. 78, ISBN 978-0-19-159167-9.
↑ Randel, Don Michael, ed. (2003), The Harvard Dictionary of Music (4th ed.), The Belknap Press of Harvard University Press, p. 416, ISBN 978-0-674-01163-2.
↑ France, Robert (2008), Introduction to Physical Education and Sport Science, Cengage Learning, p. 282, ISBN 978-1-4180-5529-5.
↑ Allen, Elizabeth; Triantaphillidou, Sophie (2011), The Manual of Photography, Taylor & Francis, p. 228, ISBN 978-0-240-52037-7.
↑ ^{Jump up to: 50.0} ^50.1 Davis, Phil (1998), Beyond the Zone System, CRC Press, p. 17, ISBN 978-1-136-09294-7.
↑ Allen & Triantaphillidou (2011), p. 235.
↑ Zwerman, Susan; Okun, Jeffrey A. (2012), Visual Effects Society Handbook: Workflow and Techniques, CRC Press, p. 205, ISBN 978-1-136-13614-6.
↑ Bauer, Craig P. (2013), Secret History: The Story of Cryptology, CRC Press, p. 332, ISBN 978-1-4665-6186-1.
↑ ^{Jump up to: 54.0} ^54.1 Warren Jr., Henry S. (2002), Hacker's Delight (1st ed.), Addison Wesley, p. 215, ISBN 978-0-201-91465-8
↑ fls, Linux kernel API, kernel.org, retrieved 2010-10-17.
↑ ^{Jump up to: 56.0} ^56.1 Majithia, J. C.; Levan, D. (1973), "A note on base-2 logarithm computations", Proceedings of the IEEE, 61 (10): 1519–1520, doi:10.1109/PROC.1973.9318.
↑ Stephenson, Ian (2005), "9.6 Fast Power, Log2, and Exp2 Functions", Production Rendering: Design and Implementation, Springer-Verlag, pp. 270–273, ISBN 978-1-84628-085-6.
↑
Warren Jr., Henry S. (2013) [2002], "11-4: Integer Logarithm", Hacker's Delight (2nd ed.), Addison Wesley – Pearson Education, Inc., p. 291, ISBN 978-0-321-84268-8, 0-321-84268-5.</रेफरी> परिणाम का भिन्नात्मक भाग है log₂ y और केवल प्रारंभिक गुणन और विभाजन का उपयोग करके, पुनरावृत्त रूप से गणना की जा सकती है।आंशिक भाग की गणना के लिए एल्गोरिथम को स्यूडोकोड में निम्नानुसार वर्णित किया जा सकता है:
1. वास्तविक संख्या से प्रारंभ करें $y$ आधे खुले अंतराल में $[1, 2)$ . अगर $y = 1$ , तब एल्गोरिथ्म किया जाता है, और भिन्नात्मक भाग शून्य होता है।
2. नहीं तो चौकोर $y$ परिणाम तक बार-बार $z$ अन्तराल में है $[2, 4)$ . होने देना $m$ आवश्यक वर्गों की संख्या हो। वह है, $z = y 2 m$ साथ $m$ ऐसा चुना $z$ में है $[2, 4)$ .
3. दोनों पक्षों का लघुगणक लेना और कुछ बीजगणित करना: ${\begin{aligned}\log _{2}z&=2^{m}\log _{2}y\\\log _{2}y&={\frac {\log _{2}z}{2^{m}}}\\&={\frac {1+\log _{2}(z/2)}{2^{m}}}\\&=2^{-m}+2^{-m}\log _{2}(z/2).\end{aligned}}$
4. फिर एक बार $z /2$ अंतराल में एक वास्तविक संख्या है $[1, 2)$ . चरण 1 पर लौटें और के बाइनरी लघुगणक की गणना करें $z /2$ उसी विधि का उपयोग करना।
इसका परिणाम निम्नलिखित पुनरावर्ती सूत्रों द्वारा व्यक्त किया जाता है, जिसमें $m_{i}$ $m_{i}$ एल्गोरिथ्म के i-वें पुनरावृत्ति में आवश्यक वर्गों की संख्या है:
${\begin{aligned}\log _{2}x&=n+2^{-m_{1}}\left(1+2^{-m_{2}}\left(1+2^{-m_{3}}\left(1+\cdots \right)\right)\right)\\&=n+2^{-m_{1}}+2^{-m_{1}-m_{2}}+2^{-m_{1}-m_{2}-m_{3}}+\cdots \end{aligned}}$
${\begin{aligned}\log _{2}x&=n+2^{-m_{1}}\left(1+2^{-m_{2}}\left(1+2^{-m_{3}}\left(1+\cdots \right)\right)\right)\\&=n+2^{-m_{1}}+2^{-m_{1}-m_{2}}+2^{-m_{1}-m_{2}-m_{3}}+\cdots \end{aligned}}$
विशेष मामले में जहां चरण 1 में भिन्नात्मक भाग शून्य पाया जाता है, यह किसी बिंदु पर समाप्त होने वाला परिमित अनुक्रम है। अन्यथा, यह एक अनंत श्रृंखला है जो अनुपात परीक्षण के अनुसार अभिसरण श्रृंखला है, क्योंकि प्रत्येक शब्द पिछले एक से सख्ती से कम है (चूंकि प्रत्येक m_i > 0). व्यावहारिक उपयोग के लिए, अनुमानित परिणाम तक पहुंचने के लिए इस अनंत श्रृंखला को छोटा किया जाना चाहिए। यदि श्रृंखला को बाद में छोटा कर दिया जाता है i-वाँ पद, तो परिणाम में त्रुटि से कम है 2^{−(m₁ + m₂ + ⋯ + m_i)}. === सॉफ्टवेयर पुस्तकालय समर्थन === log2 ई> फ़ंक्शन मानक सी गणितीय कार्यों में शामिल है। इस फ़ंक्शन का डिफ़ॉल्ट संस्करण डबल सटीक तर्क लेता है लेकिन इसके वेरिएंट तर्क को एकल-परिशुद्धता या लंबा डबल होने की अनुमति देते हैं।<ref>"7.12.6.10 The log2 functions", ISO/IEC 9899:1999 specification (PDF), p. 226.
↑ Redfern, Darren; Campbell, Colin (1998), The Matlab® 5 Handbook, Springer-Verlag, p. 141, ISBN 978-1-4612-2170-8.

बाहरी संबंध

Weisstein, Eric W., "Binary Logarithm", MathWorld
Anderson, Sean Eron (December 12, 2003), "Find the log base 2 of an N-bit integer in O(lg(N)) operations", Bit Twiddling Hacks, Stanford University, retrieved 2015-11-25
Feynman and the Connection Machine

[1] Groza, Vivian Shaw; Shelley, Susanne M. (1972), Precalculus mathematics, New York: Holt, Rinehart and Winston, p. 182, ISBN 978-0-03-077670-0.

[2] Stifel, Michael (1544), Arithmetica integra (in Latina), p. 31. A copy of the same table with two more entries appears on p. 237, and another copy extended to negative powers appears on p. 249b.

[3] Joseph, G. G. (2011), The Crest of the Peacock: Non-European Roots of Mathematics (3rd ed.), Princeton University Press, p. 352.

[4] See, e.g., Shparlinski, Igor (2013), Cryptographic Applications of Analytic Number Theory: Complexity Lower Bounds and Pseudorandomness, Progress in Computer Science and Applied Logic, vol. 22, Birkhäuser, p. 35, ISBN 978-3-0348-8037-4.

[5] Euler, Leonhard (1739), "Chapter VII. De Variorum Intervallorum Receptis Appelationibus", Tentamen novae theoriae musicae ex certissismis harmoniae principiis dilucide expositae (in Latina), Saint Petersburg Academy, pp. 102–112.

[6] Tegg, Thomas (1829), "Binary logarithms", London encyclopaedia; or, Universal dictionary of science, art, literature and practical mechanics: comprising a popular view of the present state of knowledge, Volume 4, pp. 142–143.

[7] Batschelet, E. (2012), Introduction to Mathematics for Life Scientists, Springer, p. 128, ISBN 978-3-642-96080-2.

[8] For instance, Microsoft Excel provides the IMLOG2 function for complex binary logarithms: see Bourg, David M. (2006), Excel Scientific and Engineering Cookbook, O'Reilly Media, p. 232, ISBN 978-0-596-55317-3.

[9] Kolman, Bernard; Shapiro, Arnold (1982), "11.4 Properties of Logarithms", Algebra for College Students, Academic Press, pp. 334–335, ISBN 978-1-4832-7121-7.

[10] For instance, this is the notation used in the Encyclopedia of Mathematics and The Princeton Companion to Mathematics.

[clrs-11] {Jump up to: 11.0} ^11.1 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990], Introduction to Algorithms (2nd ed.), MIT Press and McGraw-Hill, pp. 34, 53–54, ISBN 0-262-03293-7

[sw11-12] {Jump up to: 12.0} ^12.1 Sedgewick, Robert; Wayne, Kevin Daniel (2011), Algorithms, Addison-Wesley Professional, p. 185, ISBN 978-0-321-57351-3.

[13] The Chicago Manual of Style (25th ed.), University of Chicago Press, 2003, p. 530.

[knuth-14] {Jump up to: 14.0} ^14.1 Knuth, Donald E. (1997), Fundamental Algorithms, The Art of Computer Programming, vol. 1 (3rd ed.), Addison-Wesley Professional, ISBN 978-0-321-63574-7, p. 11. The same notation was in the 1973 2nd edition of the same book (p. 23) but without the credit to Reingold.

[15] Trucco, Ernesto (1956), "A note on the information content of graphs", Bull. Math. Biophys., 18 (2): 129–135, doi:10.1007/BF02477836, MR 0077919.

[16] Mitchell, John N. (1962), "Computer multiplication and division using binary logarithms", IRE Transactions on Electronic Computers, EC-11 (4): 512–517, doi:10.1109/TEC.1962.5219391.

[17] Fiche, Georges; Hebuterne, Gerard (2013), Mathematics for Engineers, John Wiley & Sons, p. 152, ISBN 978-1-118-62333-6, In the following, and unless otherwise stated, the notation $log x$ always stands for the logarithm to the base $2$ of $x$ .

[18] Cover, Thomas M.; Thomas, Joy A. (2012), Elements of Information Theory (2nd ed.), John Wiley & Sons, p. 33, ISBN 978-1-118-58577-1, Unless otherwise specified, we will take all logarithms to base $2$ .

[gt02-19] {Jump up to: 19.0} ^19.1 Goodrich, Michael T.; Tamassia, Roberto (2002), Algorithm Design: Foundations, Analysis, and Internet Examples, John Wiley & Sons, p. 23, One of the interesting and sometimes even surprising aspects of the analysis of data structures and algorithms is the ubiquitous presence of logarithms ... As is the custom in the computing literature, we omit writing the base $b$ of the logarithm when $b = 2$ .

[Tafel_1971-20] {Jump up to: 20.0} ^20.1 ^20.2 Tafel, Hans Jörg (1971), Einführung in die digitale Datenverarbeitung [Introduction to digital information processing] (in Deutsch), Munich: Carl Hanser Verlag, pp. 20–21, ISBN 3-446-10569-7

[Tietze_Schenk_1999-21] Tietze, Ulrich; Schenk, Christoph (1999), Halbleiter-Schaltungstechnik (in Deutsch) (1st corrected reprint, 11th ed.), Springer Verlag, p. 1370, ISBN 3-540-64192-0

[Bauer_2009-22] Bauer, Friedrich L. (2009), Origins and Foundations of Computing: In Cooperation with Heinz Nixdorf MuseumsForum, Springer Science & Business Media, p. 54, ISBN 978-3-642-02991-2.

[23] For DIN 1302 see Brockhaus Enzyklopädie in zwanzig Bänden [Brockhaus Encyclopedia in Twenty Volumes] (in Deutsch), vol. 11, Wiesbaden: F.A. Brockhaus, 1970, p. 554, ISBN 978-3-7653-0000-4.

[24] For ISO 31-11 see Thompson, Ambler; Taylor, Barry M (March 2008), Guide for the Use of the International System of Units (SI) — NIST Special Publication 811, 2008 Edition — Second Printing (PDF), NIST, p. 33.

[25] For ISO 80000-2 see "Quantities and units – Part 2: Mathematical signs and symbols to be used in the natural sciences and technology" (PDF), International Standard ISO 80000-2 (1st ed.), December 1, 2009, Section 12, Exponential and logarithmic functions, p. 18.

[26] Van der Lubbe, Jan C. A. (1997), Information Theory, Cambridge University Press, p. 3, ISBN 978-0-521-46760-5.

[27] Stewart, Ian (2015), Taming the Infinite, Quercus, p. 120, ISBN 9781623654733, in advanced mathematics and science the only logarithm of importance is the natural logarithm.

[28] Leiss, Ernst L. (2006), A Programmer's Companion to Algorithm Analysis, CRC Press, p. 28, ISBN 978-1-4200-1170-8.

[29] Devroye, L.; Kruszewski, P. (1996), "On the Horton–Strahler number for random tries", RAIRO Informatique Théorique et Applications, 30 (5): 443–456, doi:10.1051/ita/1996300504431, MR 1435732.

[30] Equivalently, a family with $k$ distinct elements has at most $2 k$ distinct sets, with equality when it is a power set.

[31] Eppstein, David (2005), "The lattice dimension of a graph", European Journal of Combinatorics, 26 (5): 585–592, arXiv:cs.DS/0402028, doi:10.1016/j.ejc.2004.05.001, MR 2127682, S2CID 7482443.

[32] Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. (1980), Ramsey Theory, Wiley-Interscience, p. 78.

[33] Bayer, Dave; Diaconis, Persi (1992), "Trailing the dovetail shuffle to its lair", The Annals of Applied Probability, 2 (2): 294–313, doi:10.1214/aoap/1177005705, JSTOR 2959752, MR 1161056.

[34] Mehlhorn, Kurt; Sanders, Peter (2008), "2.5 An example – binary search", Algorithms and Data Structures: The Basic Toolbox (PDF), Springer, pp. 34–36, ISBN 978-3-540-77977-3.

[35] Roberts, Fred; Tesman, Barry (2009), Applied Combinatorics (2nd ed.), CRC Press, p. 206, ISBN 978-1-4200-9983-6.

[36] Sipser, Michael (2012), "Example 7.4", Introduction to the Theory of Computation (3rd ed.), Cengage Learning, pp. 277–278, ISBN 9781133187790.

[37] Sedgewick & Wayne (2011), p. 186.

[38] Cormen et al., p. 156; Goodrich & Tamassia, p. 238.

[39] Cormen et al., p. 276; Goodrich & Tamassia, p. 159.

[40] Cormen et al., pp. 879–880; Goodrich & Tamassia, p. 464.

[41] Edmonds, Jeff (2008), How to Think About Algorithms, Cambridge University Press, p. 302, ISBN 978-1-139-47175-6.

[42] Cormen et al., p. 844; Goodrich & Tamassia, p. 279.

[43] Cormen et al., section 28.2.

[44] Causton, Helen; Quackenbush, John; Brazma, Alvis (2009), Microarray Gene Expression Data Analysis: A Beginner's Guide, John Wiley & Sons, pp. 49–50, ISBN 978-1-4443-1156-3.

[45] Eidhammer, Ingvar; Barsnes, Harald; Eide, Geir Egil; Martens, Lennart (2012), Computational and Statistical Methods for Protein Quantification by Mass Spectrometry, John Wiley & Sons, p. 105, ISBN 978-1-118-49378-6.

[mga-46] {Jump up to: 46.0} ^46.1 Campbell, Murray; Greated, Clive (1994), The Musician's Guide to Acoustics, Oxford University Press, p. 78, ISBN 978-0-19-159167-9.

[47] Randel, Don Michael, ed. (2003), The Harvard Dictionary of Music (4th ed.), The Belknap Press of Harvard University Press, p. 416, ISBN 978-0-674-01163-2.

[48] France, Robert (2008), Introduction to Physical Education and Sport Science, Cengage Learning, p. 282, ISBN 978-1-4180-5529-5.

[49] Allen, Elizabeth; Triantaphillidou, Sophie (2011), The Manual of Photography, Taylor & Francis, p. 228, ISBN 978-0-240-52037-7.

[btzs-50] {Jump up to: 50.0} ^50.1 Davis, Phil (1998), Beyond the Zone System, CRC Press, p. 17, ISBN 978-1-136-09294-7.

[51] Allen & Triantaphillidou (2011), p. 235.

[52] Zwerman, Susan; Okun, Jeffrey A. (2012), Visual Effects Society Handbook: Workflow and Techniques, CRC Press, p. 205, ISBN 978-1-136-13614-6.

[53] Bauer, Craig P. (2013), Secret History: The Story of Cryptology, CRC Press, p. 332, ISBN 978-1-4665-6186-1.

[Warren_2002-54] {Jump up to: 54.0} ^54.1 Warren Jr., Henry S. (2002), Hacker's Delight (1st ed.), Addison Wesley, p. 215, ISBN 978-0-201-91465-8

[55] s, Linux kernel API, kernel.org, retrieved 2010-10-17.

[ml73-56] {Jump up to: 56.0} ^56.1 Majithia, J. C.; Levan, D. (1973), "A note on base-2 logarithm computations", Proceedings of the IEEE, 61 (10): 1519–1520, doi:10.1109/PROC.1973.9318.

[57] Stephenson, Ian (2005), "9.6 Fast Power, Log2, and Exp2 Functions", Production Rendering: Design and Implementation, Springer-Verlag, pp. 270–273, ISBN 978-1-84628-085-6.

[Warren_2013-58] Warren Jr., Henry S. (2013) [2002], "11-4: Integer Logarithm", Hacker's Delight (2nd ed.), Addison Wesley – Pearson Education, Inc., p. 291, ISBN 978-0-321-84268-8, 0-321-84268-5.</रेफरी> परिणाम का भिन्नात्मक भाग है $log 2 y$ और केवल प्रारंभिक गुणन और विभाजन का उपयोग करके, पुनरावृत्त रूप से गणना की जा सकती है।आंशिक भाग की गणना के लिए एल्गोरिथम को स्यूडोकोड में निम्नानुसार वर्णित किया जा सकता है:
वास्तविक संख्या से प्रारंभ करें $y$ आधे खुले अंतराल में $[1, 2)$ . अगर $y = 1$ , तब एल्गोरिथ्म किया जाता है, और भिन्नात्मक भाग शून्य होता है।

नहीं तो चौकोर $y$ परिणाम तक बार-बार $z$ अन्तराल में है $[2, 4)$ . होने देना $m$ आवश्यक वर्गों की संख्या हो। वह है, $z = y 2 m$ साथ $m$ ऐसा चुना $z$ में है $[2, 4)$ .

दोनों पक्षों का लघुगणक लेना और कुछ बीजगणित करना: ${\begin{aligned}\log _{2}z&=2^{m}\log _{2}y\\\log _{2}y&={\frac {\log _{2}z}{2^{m}}}\\&={\frac {1+\log _{2}(z/2)}{2^{m}}}\\&=2^{-m}+2^{-m}\log _{2}(z/2).\end{aligned}}$

फिर एक बार $z /2$ अंतराल में एक वास्तविक संख्या है $[1, 2)$ . चरण 1 पर लौटें और के बाइनरी लघुगणक की गणना करें $z /2$ उसी विधि का उपयोग करना।
इसका परिणाम निम्नलिखित पुनरावर्ती सूत्रों द्वारा व्यक्त किया जाता है, जिसमें $m_{i}$ एल्गोरिथ्म के i-वें पुनरावृत्ति में आवश्यक वर्गों की संख्या है: ${\begin{aligned}\log _{2}x&=n+2^{-m_{1}}\left(1+2^{-m_{2}}\left(1+2^{-m_{3}}\left(1+\cdots \right)\right)\right)\\&=n+2^{-m_{1}}+2^{-m_{1}-m_{2}}+2^{-m_{1}-m_{2}-m_{3}}+\cdots \end{aligned}}$ विशेष मामले में जहां चरण 1 में भिन्नात्मक भाग शून्य पाया जाता है, यह किसी बिंदु पर समाप्त होने वाला परिमित अनुक्रम है। अन्यथा, यह एक अनंत श्रृंखला है जो अनुपात परीक्षण के अनुसार अभिसरण श्रृंखला है, क्योंकि प्रत्येक शब्द पिछले एक से सख्ती से कम है (चूंकि प्रत्येक $m i > 0$ ). व्यावहारिक उपयोग के लिए, अनुमानित परिणाम तक पहुंचने के लिए इस अनंत श्रृंखला को छोटा किया जाना चाहिए। यदि श्रृंखला को बाद में छोटा कर दिया जाता है $i$ -वाँ पद, तो परिणाम में त्रुटि से कम है $2 -(m 1 + m 2 + \dots + m i)$ . === सॉफ्टवेयर पुस्तकालय समर्थन === log2 ई> फ़ंक्शन मानक सी गणितीय कार्यों में शामिल है। इस फ़ंक्शन का डिफ़ॉल्ट संस्करण डबल सटीक तर्क लेता है लेकिन इसके वेरिएंट तर्क को एकल-परिशुद्धता या लंबा डबल होने की अनुमति देते हैं।<ref>"7.12.6.10 The log2 functions", ISO/IEC 9899:1999 specification (PDF), p. 226.

[59] वास्तविक संख्या से प्रारंभ करें $y$ आधे खुले अंतराल में $[1, 2)$ . अगर $y = 1$ , तब एल्गोरिथ्म किया जाता है, और भिन्नात्मक भाग शून्य होता है।

[60] नहीं तो चौकोर $y$ परिणाम तक बार-बार $z$ अन्तराल में है $[2, 4)$ . होने देना $m$ आवश्यक वर्गों की संख्या हो। वह है, $z = y 2 m$ साथ $m$ ऐसा चुना $z$ में है $[2, 4)$ .

[61] दोनों पक्षों का लघुगणक लेना और कुछ बीजगणित करना: ${\begin{aligned}\log _{2}z&=2^{m}\log _{2}y\\\log _{2}y&={\frac {\log _{2}z}{2^{m}}}\\&={\frac {1+\log _{2}(z/2)}{2^{m}}}\\&=2^{-m}+2^{-m}\log _{2}(z/2).\end{aligned}}$

[62] फिर एक बार $z /2$ अंतराल में एक वास्तविक संख्या है $[1, 2)$ . चरण 1 पर लौटें और के बाइनरी लघुगणक की गणना करें $z /2$ उसी विधि का उपयोग करना।

[59] Redfern, Darren; Campbell, Colin (1998), The Matlab® 5 Handbook, Springer-Verlag, p. 141, ISBN 978-1-4612-2170-8.

[64] वास्तविक संख्या से प्रारंभ करें $y$ आधे खुले अंतराल में $[1, 2)$ . अगर $y = 1$ , तब एल्गोरिथ्म किया जाता है, और भिन्नात्मक भाग शून्य होता है।

[65] नहीं तो चौकोर $y$ परिणाम तक बार-बार $z$ अन्तराल में है $[2, 4)$ . होने देना $m$ आवश्यक वर्गों की संख्या हो। वह है, $z = y 2 m$ साथ $m$ ऐसा चुना $z$ में है $[2, 4)$ .

[66] दोनों पक्षों का लघुगणक लेना और कुछ बीजगणित करना: ${\begin{aligned}\log _{2}z&=2^{m}\log _{2}y\\\log _{2}y&={\frac {\log _{2}z}{2^{m}}}\\&={\frac {1+\log _{2}(z/2)}{2^{m}}}\\&=2^{-m}+2^{-m}\log _{2}(z/2).\end{aligned}}$

[67] फिर एक बार $z /2$ अंतराल में एक वास्तविक संख्या है $[1, 2)$ . चरण 1 पर लौटें और के बाइनरी लघुगणक की गणना करें $z /2$ उसी विधि का उपयोग करना।

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[28]

[29]

[30]

[31]

[32]

[33]

[34]

[35]

[36]

[37]

[38]

[39]

[40]

[41]

[42]

[43]

[44]

[45]

[46]

[47]

[48]

[49]

[50]

[51]

[52]

[53]

[54]

[55]

[56]

[57]

[58]

[59]

Anonymous

Search

बाइनरी लघुगणक

Namespaces

More

Page actions

Contents

इतिहास

परिभाषा और गुण

अंकन पद्धति

अनुप्रयोग

सूचना सिद्धांत

साहचर्य (कॉम्बिनेटरिक्स)

अभिकलनात्मक जटिलता

जैव सूचना विज्ञान

संगीत सिद्धांत

स्पोर्ट्स शेड्यूलिंग

छायाचित्र (फोटोग्राफी)

गणना

अन्य आधारों से रूपांतरण

पूर्णांक गोलाई

पुनरावर्ती सन्निकटन

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

बाइनरी लघुगणक

इतिहास

परिभाषा और गुण

अंकन पद्धति

अनुप्रयोग

सूचना सिद्धांत

साहचर्य (कॉम्बिनेटरिक्स)

अभिकलनात्मक जटिलता

जैव सूचना विज्ञान

संगीत सिद्धांत

स्पोर्ट्स शेड्यूलिंग

छायाचित्र (फोटोग्राफी)

गणना

अन्य आधारों से रूपांतरण

पूर्णांक गोलाई

पुनरावर्ती सन्निकटन

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Categories