पुनरावृत्त लघुगणक

For संभाव्यता सिद्धांत में प्रमेय, see पुनरावृत्त लघुगणक का नियम.

कंप्यूटर विज्ञान में, $n$ का पुनरावृत्त लघुगणक लिखित हुआ log* $n$ (सामान्यतः लॉग स्टार पढ़ा जाता है), परिणाम $1$ से कम या उसके समान होने से पहले लघुगणक कार्य को पुनरावृति प्रयुक्त करने की संख्या है सबसे सरल औपचारिक परिभाषा इस पुनरावृत्ति संबंध का परिणाम है:

$\log ^{*}n:={\begin{cases}0&{\mbox{if }}n\leq 1;\\1+\log ^{*}(\log n)&{\mbox{if }}n>1\end{cases}}$

धनात्मक वास्तविक संख्याओं पर, निरंतर सुपर-लघुगणक (व्युत्क्रम चतुष्कोण) अनिवार्य रूप से समतुल्य है:

$\log ^{*}n=\lceil \mathrm {slog} _{e}(n)\rceil$

अथार्त आधार b पुनरावृत्त लघुगणक $\log ^{*}n=y$ है यदि n अंतराल $^{y-1}b<n\leq \ ^{y}b$ के अंदर स्थित है, जहां ${^{y}b}=\underbrace {b^{b^{\cdot ^{\cdot ^{b}}}}} _{y}$ _{y}} टेट्रेशन को दर्शाता है। चूँकि ऋणात्मक वास्तविक संख्याओं पर, लॉग-स्टार $0$ है, जबकि धनात्मक x के लिए $\lceil {\text{slog}}_{e}(-x)\rceil =-1$ है, इसलिए ऋणात्मक तर्कों के लिए दोनों फलन भिन्न हैं।

चित्र 1. बेस-ई पुनरावृत्त लघुगणक के लिए log* 4 = 2 प्रदर्शित करना है पुनरावृत्त लघुगणक का मान इनपुट n से अंतराल [0,1] तक वक्र y = log_b(x) पर "ज़िग-ज़ैगिंग" द्वारा पाया जा सकता है। इस स्थिति में, b = e. ज़िग-ज़ैगिंग में बिंदु (n, 0) से प्रारंभ करना और पुनरावृत्त रूप से (n, log_b(n) ),से (0, log_b(n) ), to (log_b(n), 0 ) तक जाना सम्मिलित है।

पुनरावृत्त लघुगणक किसी भी धनात्मक वास्तविक संख्या को स्वीकार करता है और एक पूर्णांक उत्पन्न करता है। ग्राफ़िक रूप से, इसे चित्र 1 में x-अक्ष पर अंतराल $[0,1]$ तक पहुंचने के लिए आवश्यक "ज़िग-ज़ैग" की संख्या के रूप में समझा जा सकता है।

कंप्यूटर विज्ञान में, lg* का उपयोग अधिकांशतः बाइनरी पुनरावृत्त लघुगणक को इंगित करने के लिए किया जाता है, जो प्राकृतिक लघुगणक (आधार ई के साथ) के अतिरिक्त बाइनरी लघुगणक (आधार $2$ के साथ) को पुनरावृत्त करता है।

गणितीय रूप से, पुनरावृत्त लघुगणक केवल आधार $2$ और आधार e के लिए ही नहीं, किन्तु $e^{1/e}\approx 1.444667$ लगभग 1.444667} से बड़े किसी भी आधार के लिए अच्छी तरह से परिभाषित है।

एल्गोरिदम का विश्लेषण

पुनरावृत्त लघुगणक एल्गोरिदम और कम्प्यूटेशनल जटिलता सिद्धांत के विश्लेषण में उपयोगी है, जो कुछ एल्गोरिदम के समय और स्थान जटिलता सीमा में दिखाई देता है:

• यूक्लिडियन न्यूनतम फैले हुए पेड़ को यादृच्छिक O(n log* n) समय को जानने वाले बिंदुओं के एक सेट के डेलाउने त्रिकोण का पता लगाया जाता है।
• पूर्णांक गुणन के लिए फ्यूरर का एल्गोरिदम: O(n log n 2^{O(lg* n)}).
• अनुमानित अधिकतम खोज (तत्व कम से कम माध्यिका जितना बड़ा):lg* n − 4 to lg* n + 2 समानांतर संचालन।
• एन-चक्र को 3-रंग देने के लिए रिचर्ड कोल और उजी विश्किन का वितरित एल्गोरिदम: O(log* n) सिंक्रोनस संचार राउंड।

पुनरावृत्त लघुगणक अत्यंत धीमी गति से बढ़ता है, लघुगणक की तुलना में बहुत धीमी गति से n के सभी मानो के लिए अभ्यास में कार्यान्वित एल्गोरिदम के चलने के समय की गणना करने के लिए प्रासंगिक (अथार्त, n ≤ 2⁶⁵⁵³⁶, जो ज्ञात ब्रह्मांड में परमाणुओं की अनुमानित संख्या से कहीं अधिक है), आधार 2 के साथ पुनरावृत्त लघुगणक का मान 5 से अधिक नहीं है।

आधार-2 पुनरावृत्त लघुगणक

x	lg* x
(−∞, 1]	0
(1, 2]	1
(2, 4]	2
(4, 16]	3
(16, 65536]	4
(65536, 265536]	5

उच्च आधार छोटे पुनरावृत्त लघुगणक देते हैं। वास्तव में, जटिलता सिद्धांत में सामान्यतः उपयोग किया जाने वाला एकमात्र फलन जो अधिक धीरे-धीरे बढ़ता है वह उलटा एकरमैन फलन है।

अन्य अनुप्रयोग

पुनरावृत्त लघुगणक सममित स्तर-सूचकांक अंकगणित में उपयोग किए जाने वाले सामान्यीकृत लघुगणक फलन से निकटता से संबंधित है। किसी संख्या की योगात्मक दृढ़ता, किसी को उसके डिजिटल रूट तक पहुंचने से पहले संख्या को उसके अंकों के योग से बदलने की संख्या $O(\log ^{*}n)$ है।

कम्प्यूटेशनल जटिलता सिद्धांत में, संथानम दर्शाता है कि कम्प्यूटेशनल संसाधन डीटाइम - एक नियतात्मक ट्यूरिंग मशीन के लिए गणना समय - और एनटाइम- एक गैर-नियतात्मक ट्यूरिंग मशीन के लिए गणना समय - $n{\sqrt {\log ^{*}n}}.$ तक भिन्न हैं।