चक्र का पता लगाना

कंप्यूटर विज्ञान में, चक्र का पता लगाने या चक्र की खोज पुनरावृत्त फ़ंक्शन मानों के अनुक्रम में एक चक्र खोजने की कलन विधि समस्या है।

किसी भी कार्य के लिए (गणित) $f$ जो एक परिमित सेट को मैप करता है $S$ स्वयं के लिए, और कोई प्रारंभिक मान $x 0$ में $S$ , पुनरावृत्त फ़ंक्शन मानों का क्रम

x_{0},\ x_{1}=f(x_{0}),\ x_{2}=f(x_{1}),\ \dots ,\ x_{i}=f(x_{i-1}),\ \dots

अंततः एक ही मूल्य का दो बार उपयोग करना चाहिए: अलग-अलग सूचकांकों की कुछ जोड़ी होनी चाहिए $i$ और $j$ ऐसा है कि $x i = x j$ . एक बार ऐसा होने के बाद, अनुक्रम को मूल्यों के समान अनुक्रम को दोहराते हुए आवधिक अनुक्रम जारी रखना चाहिए $x i$ को $x j - 1$ . साइकिल का पता लगाने की समस्या है $i$ और $j$ , दिया गया $f$ और $x 0$ .

चक्रों को जल्दी और कम स्मृति के साथ खोजने के लिए कई एल्गोरिदम ज्ञात हैं। रॉबर्ट डब्ल्यू फ़्लॉइड की साइकिल पहचान#Floyd's_tortoise_and_hare मूल्यों के अनुक्रम के माध्यम से अलग-अलग गति से दो पॉइंटर्स को तब तक घुमाती है जब तक कि वे दोनों समान मानों की ओर इशारा नहीं करते। वैकल्पिक रूप से, ब्रेंट का एल्गोरिथ्म घातीय खोज के विचार पर आधारित है। फ्लोयड और ब्रेंट के एल्गोरिदम दोनों ही स्मृति कोशिकाओं की एक निरंतर संख्या का उपयोग करते हैं, और कई प्रकार के फ़ंक्शन मूल्यांकन लेते हैं जो अनुक्रम की शुरुआत से पहली पुनरावृत्ति तक की दूरी के अनुपात में होते हैं। कई अन्य एल्गोरिदम कम फ़ंक्शन मूल्यांकन के लिए बड़ी मात्रा में मेमोरी का व्यापार करते हैं।

चक्र पहचान के अनुप्रयोगों में छद्म यादृच्छिक संख्या जेनरेटर और क्रिप्टोग्राफ़िक हैश फ़ंक्शन, कम्प्यूटेशनल संख्या सिद्धांत एल्गोरिदम, कंप्यूटर प्रोग्राम में अनंत लूप का पता लगाने और सेलुलर automaton में आवधिक कॉन्फ़िगरेशन, लिंक्ड सूची डेटा संरचनाओं के स्वचालित आकार विश्लेषण (सॉफ़्टवेयर) की गुणवत्ता का परीक्षण शामिल है, और डेटाबेस में लेन-देन प्रबंधक के लिए गतिरोध का पता लगाना।

उदाहरण

सेट से और सेट {0,1,2,3,4,5,6,7,8} और संबंधित कार्यात्मक ग्राफ के लिए एक फ़ंक्शन

आंकड़ा एक समारोह दिखाता है $f$ जो सेट को मैप करता है $S = {0,1,2,3,4,5,6,7,8}$ खुद को। अगर एक से शुरू होता है $x 0 = 2$ और बार-बार लागू होता है $f$ , मानों का क्रम देखता है

2, 0, 6, 3, 1, 6, 3, 1, 6, 3, 1, ....

इस मान क्रम में चक्र है $6, 3, 1$ .

परिभाषाएँ

होने देना $S$ कोई परिमित समुच्चय हो, $f$ कोई भी कार्य हो $S$ खुद के लिए, और $x 0$ का कोई भी तत्व हो $S$ . किसी के लिए $i > 0$ , होने देना $x i = f (x i - 1)$ . होने देना $μ$ सबसे छोटा इंडेक्स हो जैसे कि value $x μ$ मूल्यों के क्रम में अक्सर असीम रूप से प्रकट होता है $x i$ , और जाने $λ$ (लूप की लंबाई) सबसे छोटा सकारात्मक पूर्णांक हो जैसे कि $x μ = x λ + μ$ . चक्र का पता लगाने की समस्या खोजने का कार्य है $λ$ और $μ$ .^[1] एक ही समस्या ग्राफ सिद्धांत | ग्राफ-सैद्धांतिक रूप से, एक कार्यात्मक ग्राफ (यानी, एक निर्देशित ग्राफ जिसमें प्रत्येक शीर्ष पर एक एकल आउटगोइंग एज है) का निर्माण करके देखा जा सकता है, जिसके कोने तत्व हैं $S$ और जिसके किनारे किसी तत्व को संबंधित फ़ंक्शन मान पर मैप करते हैं, जैसा कि चित्र में दिखाया गया है। वर्टेक्स का सेट स्टार्टिंग वर्टेक्स से गम्यता $x 0$ Rho (अक्षर) जैसी आकृति के साथ एक सबग्राफ बनाएं ( $ρ$ ): लंबाई का पथ $μ$ से $x 0$ के एक चक्र (ग्राफ सिद्धांत) के लिए $λ$ शिखर।^[2]

कंप्यूटर प्रतिनिधित्व

आम तौर पर, $f$ को मानों की तालिका के रूप में निर्दिष्ट नहीं किया जाएगा, जैसा कि ऊपर चित्र में दिखाया गया है। बल्कि, एक साइकिल डिटेक्शन एल्गोरिद्म को मूल्यों के अनुक्रम तक पहुंच दी जा सकती है $x i$ , या गणना के लिए एक उपनेमका के लिए $f$ . कार्य खोजना है $λ$ और $μ$ अनुक्रम से कुछ मूल्यों की जांच करते समय या यथासंभव कुछ सबरूटीन कॉल करते हुए। आम तौर पर, चक्र पहचान समस्या के लिए एल्गोरिदम की अंतरिक्ष जटिलता भी महत्वपूर्ण है: हम पूरे अनुक्रम को स्टोर करने के लिए आवश्यक मेमोरी की मात्रा का उपयोग करते हुए समस्या को हल करना चाहते हैं।

कुछ अनुप्रयोगों में, और विशेष रूप से पूर्णांक गुणनखंडन के लिए पोलार्ड के rho एल्गोरिथम में, एल्गोरिथम की बहुत अधिक सीमित पहुंच है $S$ और करने के लिए $f$ . उदाहरण के लिए, पोलार्ड के आरओ एल्गोरिथम में, $S$ पूर्णांक मॉडुलो का सेट है जो संख्या का एक अज्ञात अभाज्य गुणनखंड है, इसलिए इसका आकार भी $S$ एल्गोरिथ्म के लिए अज्ञात है। ऐसे सीमित ज्ञान के साथ चक्र पहचान एल्गोरिदम का उपयोग करने की अनुमति देने के लिए, उन्हें निम्नलिखित क्षमताओं के आधार पर डिज़ाइन किया जा सकता है। प्रारंभ में, यह माना जाता है कि एल्गोरिथम की मेमोरी में एक वस्तु है जो शुरुआती मूल्य के लिए एक सूचक (कंप्यूटर प्रोग्रामिंग) का प्रतिनिधित्व करती है $x 0$ . किसी भी चरण में, यह तीन क्रियाओं में से एक कर सकता है: यह स्मृति में किसी अन्य वस्तु के लिए किसी भी सूचक को कॉपी कर सकता है, यह लागू हो सकता है $f$ और इसके किसी भी पॉइंटर को एक पॉइंटर द्वारा अनुक्रम में अगली वस्तु से बदलें, या यह निर्धारित करने के लिए एक सबरूटीन लागू कर सकता है कि इसके दो पॉइंटर्स अनुक्रम में समान मानों का प्रतिनिधित्व करते हैं या नहीं। समानता परीक्षण क्रिया में कुछ गैर-तुच्छ अभिकलन शामिल हो सकते हैं: उदाहरण के लिए, पोलार्ड के rho एल्गोरिथम में, यह परीक्षण द्वारा कार्यान्वित किया जाता है कि क्या दो संग्रहीत मानों के बीच के अंतर में कारक होने वाली संख्या के साथ एक गैर-तुच्छ सबसे बड़ा सामान्य विभाजक है।^[2]इस संदर्भ में, संगणना के सूचक मशीन मॉडल के अनुरूप, एक एल्गोरिथ्म जो केवल पॉइंटर कॉपी करने, अनुक्रम के भीतर उन्नति और समानता परीक्षणों का उपयोग करता है, को पॉइंटर एल्गोरिथम कहा जा सकता है।

एल्गोरिदम

यदि इनपुट गणना के लिए सबरूटीन के रूप में दिया गया है $f$ , चक्र का पता लगाने की समस्या को केवल उपयोग करके तुच्छ रूप से हल किया जा सकता है $λ + μ$ फ़ंक्शन एप्लिकेशन, केवल मानों के अनुक्रम की गणना करके $x i$ और इन मानों को संग्रहीत करने के लिए हैश तालिका जैसी डेटा संरचना का उपयोग करना और परीक्षण करना कि क्या प्रत्येक अनुवर्ती मान पहले ही संग्रहीत किया जा चुका है। हालाँकि, इस एल्गोरिथम की अंतरिक्ष जटिलता आनुपातिक है $λ + μ$ , अनावश्यक रूप से बड़ा। इसके अतिरिक्त, इस पद्धति को एक सूचक एल्गोरिथ्म के रूप में लागू करने के लिए मूल्यों की प्रत्येक जोड़ी के लिए समानता परीक्षण लागू करने की आवश्यकता होगी, जिसके परिणामस्वरूप कुल मिलाकर द्विघात समय होगा। इस प्रकार, इस क्षेत्र में अनुसंधान ने दो लक्ष्यों पर ध्यान केंद्रित किया है: इस सरल एल्गोरिथम की तुलना में कम जगह का उपयोग करना, और सूचक एल्गोरिदम खोजना जो कम समानता परीक्षणों का उपयोग करते हैं।

फ्लोयड का कछुआ और खरगोश

फ्लोयड का कछुआ और खरगोश चक्र पहचान एल्गोरिदम, अनुक्रम 2, 0, 6, 3, 1, 6, 3, 1, पर लागू होता है ...

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

एल्गोरिदम का नाम रॉबर्ट डब्ल्यू फ़्लॉइड के नाम पर रखा गया है, जिन्हें डोनाल्ड नुथ द्वारा इसके आविष्कार का श्रेय दिया गया था।^[3]^[4] हालांकि, फ़्लॉइड के प्रकाशित कार्य में एल्गोरिथम प्रकट नहीं होता है, और यह एक गलत विशेषता हो सकती है: फ़्लॉइड 1967 के पेपर में निर्देशित ग्राफ़ में सभी सरल चक्रों को सूचीबद्ध करने के लिए एल्गोरिथम का वर्णन करता है,^[5] लेकिन यह पेपर कार्यात्मक ग्राफ में चक्र खोजने की समस्या का वर्णन नहीं करता है जो कि इस आलेख का विषय है। वास्तव में, नुथ का बयान (1969 में), बिना किसी उद्धरण के, फ़्लॉइड के लिए इसका श्रेय, प्रिंट में पहली ज्ञात उपस्थिति है, और इस प्रकार यह एक गणितीय लोककथा हो सकती है, जो किसी एक व्यक्ति के लिए जिम्मेदार नहीं है।^[6] एल्गोरिथ्म में प्रमुख अंतर्दृष्टि इस प्रकार है। यदि कोई चक्र है, तो किसी भी पूर्णांक के लिए $i \geq μ$ और $k \geq 0$ , $x i = x i + kλ$ , कहाँ $λ$ पाए जाने वाले लूप की लंबाई है, $μ$ चक्र के पहले तत्व का सूचकांक है, और $k$ लूप की संख्या का प्रतिनिधित्व करने वाला एक पूर्ण पूर्णांक है। इसके आधार पर यह दिखाया जा सकता है $i = kλ \geq μ$ कुछ के लिए $k$ अगर और केवल अगर $x i = x 2 i$ (अगर $x i = x 2 i$ चक्र में, तो कुछ मौजूद है $k$ ऐसा है कि $2 i = i + kλ$ , जिसका तात्पर्य है $i = kλ$ ; और अगर कुछ हैं $i$ और $k$ ऐसा है कि $i = kλ$ , तब $2i = i + kλ$ और $x 2 i = x i + kλ$ ). इस प्रकार, एल्गोरिथ्म को केवल इस विशेष रूप के दोहराए गए मानों की जांच करने की आवश्यकता होती है, एक अवधि को खोजने के लिए अनुक्रम की शुरुआत से दुगुनी दूरी पर {{mvar|ν}एक पुनरावृत्ति का } जो कि एक गुणक है $λ$ . एक बार $ν$ पाया जाता है, एल्गोरिथ्म पहले दोहराए गए मान को खोजने के लिए इसके प्रारंभ से अनुक्रम को पुनः प्राप्त करता है $x μ$ अनुक्रम में, इस तथ्य का उपयोग करते हुए कि $λ$ विभाजित करता है $ν$ और इसलिए वह $x μ = x μ + v$ . अंत में, एक बार का मूल्य $μ$ ज्ञात है कि लंबाई ज्ञात करना तुच्छ है $λ$ सबसे छोटा दोहराव वाला चक्र, पहली स्थिति की खोज करके $μ + λ$ जिसके लिए $x μ + λ = x μ$ .

एल्गोरिथ्म इस प्रकार दिए गए अनुक्रम में दो बिंदुओं को बनाए रखता है, एक (कछुआ) पर $x i$ , और दूसरा (खरगोश) पर $x 2 i$ . एल्गोरिथ्म के प्रत्येक चरण में, यह बढ़ता है $i$ एक के बाद एक, कछुआ को एक कदम आगे और खरगोश को क्रम में दो कदम आगे बढ़ाते हुए, और फिर इन दो बिंदुओं पर अनुक्रम मानों की तुलना करता है। का सबसे छोटा मान $i > 0$ जिसके लिए कछुआ और खरगोश समान मूल्यों की ओर इशारा करते हैं, वांछित मूल्य है $ν$ .

निम्नलिखित पायथन (प्रोग्रामिंग भाषा) कोड दिखाता है कि इस विचार को एल्गोरिदम के रूप में कैसे कार्यान्वित किया जा सकता है।

def floyd(f, x0) -> tuple[int, int]:
    """Floyd's cycle detection algorithm."""
    # Main phase of algorithm: finding a repetition x_i = x_2i.
    # The hare moves twice as quickly as the tortoise and
    # the distance between them increases by 1 at each step.
    # Eventually they will both be inside the cycle and then,
    # at some point, the distance between them will be
    # divisible by the period λ.
    tortoise = f(x0) # f(x0) is the element/node next to x0.
    hare = f(f(x0))
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(f(hare))
  
    # At this point the tortoise position, ν, which is also equal
    # to the distance between hare and tortoise, is divisible by
    # the period λ. So hare moving in cycle one step at a time, 
    # and tortoise (reset to x0) moving towards the cycle, will 
    # intersect at the beginning of the cycle. Because the 
    # distance between them is constant at 2ν, a multiple of λ,
    # they will agree as soon as the tortoise reaches index μ.

    # Find the position μ of first repetition.    
    mu = 0
    tortoise = x0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)   # Hare and tortoise move at same speed
        mu += 1
 
    # Find the length of the shortest cycle starting from x_μ
    # The hare moves one step at a time while tortoise is still.
    # lam is incremented until λ is found.
    lam = 1
    hare = f(tortoise)
    while tortoise != hare:
        hare = f(hare)
        lam += 1
 
    return lam, mu

यह कोड केवल पॉइंटर्स, फ़ंक्शन मूल्यांकन और समानता परीक्षणों को संग्रहीत और कॉपी करके अनुक्रम तक पहुंचता है; इसलिए, यह एक पॉइंटर एल्गोरिथम के रूप में योग्य है। एल्गोरिथम उपयोग करता है $O (λ + μ)$ इन प्रकार के संचालन, और $O (1)$ स्टोरेज की जगह।^[7]

ब्रेंट का एल्गोरिदम

रिचर्ड ब्रेंट (वैज्ञानिक)|रिचर्ड पी. ब्रेंट ने एक वैकल्पिक चक्र पहचान एल्गोरिद्म का वर्णन किया है, जो कछुआ और खरगोश एल्गोरिथम की तरह, अनुक्रम में केवल दो पॉइंटर्स की आवश्यकता होती है।^[8] हालाँकि, यह एक अलग सिद्धांत पर आधारित है: दो की सबसे छोटी शक्ति की खोज करना $2 i$ जो दोनों से बड़ा है $λ$ और $μ$ . के लिए $i = 0, 1, 2, ...$ , एल्गोरिदम तुलना करता है $x 2 i -1$ दो की अगली शक्ति तक प्रत्येक बाद के अनुक्रम मान के साथ, जब यह एक मैच पाता है तो रुक जाता है। कछुआ और खरगोश एल्गोरिथम की तुलना में इसके दो फायदे हैं: यह सही लंबाई पाता है $λ$ बाद के चरण में इसे खोजने की आवश्यकता के बजाय सीधे चक्र का, और इसके चरणों में केवल एक मूल्यांकन शामिल है $f$ तीन के बजाय।^[9] निम्नलिखित पायथन कोड दिखाता है कि यह तकनीक अधिक विस्तार से कैसे काम करती है।

def brent(f, x0) -> tuple[int, int]:
    """Brent's cycle detection algorithm."""
    # main phase: search successive powers of two
    power = lam = 1
    tortoise = x0
    hare = f(x0)  # f(x0) is the element/node next to x0.
    while tortoise != hare:
        if power == lam:  # time to start a new power of two?
            tortoise = hare
            power *= 2
            lam = 0
        hare = f(hare)
        lam += 1

    # Find the position of the first repetition of length λ
    tortoise = hare = x0
    for i in range(lam):
    # range(lam) produces a list with the values 0, 1, ... , lam-1
        hare = f(hare)
    # The distance between the hare and tortoise is now λ.

    # Next, the hare and tortoise move at same speed until they agree
    mu = 0
    while tortoise != hare:
        tortoise = f(tortoise)
        hare = f(hare)
        mu += 1
 
    return lam, mu

कछुआ और खरगोश एल्गोरिथम की तरह, यह एक पॉइंटर एल्गोरिथम है जो उपयोग करता है $O (λ + μ)$ परीक्षण और कार्य मूल्यांकन और $O (1)$ स्टोरेज की जगह। यह दिखाना मुश्किल नहीं है कि फ़्लॉइड के एल्गोरिथम की तुलना में फ़ंक्शन मूल्यांकन की संख्या कभी भी अधिक नहीं हो सकती है। ब्रेंट का दावा है कि, औसत रूप से, उसका चक्र खोजने वाला एल्गोरिथ्म फ़्लॉइड की तुलना में लगभग 36% अधिक तेज़ी से चलता है और यह पोलार्ड आरओ एल्गोरिथम को लगभग 24% तक गति देता है। वह एल्गोरिथम के एक यादृच्छिक संस्करण के लिए एक औसत-केस जटिलता विश्लेषण भी करता है जिसमें दो पॉइंटर्स के धीमे द्वारा पता लगाए गए सूचकांकों का क्रम स्वयं दो की शक्तियां नहीं है, बल्कि दो की शक्तियों का एक यादृच्छिक गुणक है। हालांकि उनका मुख्य इरादा आवेदन पूर्णांक कारककरण एल्गोरिदम में था, ब्रेंट छद्म यादृच्छिक संख्या जनरेटर के परीक्षण में अनुप्रयोगों पर भी चर्चा करता है।^[8]

गोस्पर का एल्गोरिदम

बिल गोस्पर|आर. डब्ल्यू गोस्पर का एल्गोरिदम^[10]^[11] अवधि पाता है $\lambda$ , और शुरुआती बिंदु की निचली और ऊपरी सीमा, $\mu _{l}$ और $\mu _{u}$ , पहले चक्र का। निचली और ऊपरी सीमा के बीच का अंतर अवधि के समान क्रम का है, उदाहरण के लिए। $\mu _{l}+\lambda \sim \mu _{h}$ .

फायदे

गॉस्पर के एल्गोरिथ्म की मुख्य विशेषता यह है कि यह जनरेटर फ़ंक्शन का पुनर्मूल्यांकन करने के लिए कभी पीछे नहीं हटता है, और अंतरिक्ष और समय दोनों में किफायती है। इसे मोटे तौर पर ब्रेंट के एल्गोरिथम के समवर्ती संस्करण के रूप में वर्णित किया जा सकता है। जबकि ब्रेंट का एल्गोरिदम धीरे-धीरे कछुए और खरगोश के बीच के अंतर को बढ़ाता है, गोस्पर का एल्गोरिदम कई कछुओं का उपयोग करता है (कई पिछले मान सहेजे जाते हैं), जो मोटे तौर पर घातीय दूरी पर होते हैं। HAKMEM आइटम 132 में नोट के अनुसार, यह एल्गोरिदम किसी भी मूल्य की तीसरी घटना से पहले पुनरावृत्ति का पता लगाएगा, यानी चक्र को फिर से शुरू किया जाएगा सबसे दो बार। यह नोट यह भी बताता है कि यह स्टोर करने के लिए पर्याप्त है $\Theta (\log \lambda )$ पूर्व मान; हालाँकि, प्रदान किया गया कार्यान्वयन^[10]भंडार $\Theta (\log(\mu +\lambda ))$ मान। उदाहरण के लिए, मान लें कि फ़ंक्शन मान 32-बिट पूर्णांक हैं, और इसलिए चक्र का दूसरा पुनरावृत्ति अधिकतम 2 के बाद समाप्त होता है³² प्रारंभ से ही कार्य मूल्यांकन (अर्थात। $\mu +2\lambda \leq 2^{32}$ ). फिर गोस्पर का एल्गोरिदम चक्र को अधिकतम 2 के बाद ढूंढेगा³² फ़ंक्शन मूल्यांकन, 33 मानों के स्थान का उपभोग करते हुए (प्रत्येक मान 32-बिट पूर्णांक है)।

जटिलता

के उपर $i$ जनरेटर फ़ंक्शन का -th मूल्यांकन, एल्गोरिदम उत्पन्न मूल्य की तुलना करता है $O(\log i)$ पूर्व मान; उसका अवलोकन करो $i$ कम से कम तक जाता है $\mu +\lambda$ और अधिक से अधिक $\mu +2\lambda$ . इसलिए, इस एल्गोरिथम की समय जटिलता है $O((\mu +\lambda )\cdot \log(\mu +\lambda ))$ . चूंकि यह स्टोर करता है $\Theta (\log(\mu +\lambda ))$ मूल्य, इसकी अंतरिक्ष जटिलता है $\Theta (\log(\mu +\lambda ))$ . यह सामान्य धारणा के तहत है, जो इस पूरे लेख में मौजूद है, कि फ़ंक्शन मानों का आकार स्थिर है। इस धारणा के बिना, अंतरिक्ष जटिलता है $\Omega (\log ^{2}(\mu +\lambda ))$ चूंकि हमें कम से कम चाहिए $\mu +\lambda$ विशिष्ट मान और इस प्रकार प्रत्येक मान का आकार है $\Omega (\log(\mu +\lambda ))$ .

समय-अंतरिक्ष समझौता

कई लेखकों ने चक्र का पता लगाने के लिए तकनीकों का अध्ययन किया है जो फ़्लॉइड और ब्रेंट के तरीकों की तुलना में अधिक मेमोरी का उपयोग करते हैं, लेकिन चक्रों का अधिक तेज़ी से पता लगाते हैं। सामान्य तौर पर ये विधियाँ कई पूर्व-गणना अनुक्रम मानों को संग्रहीत करती हैं, और परीक्षण करती हैं कि क्या प्रत्येक नया मान पूर्व-गणना किए गए मानों में से एक के बराबर है। ऐसा जल्दी करने के लिए, वे आम तौर पर पहले से गणना किए गए मानों को संग्रहीत करने के लिए एक हैश टेबल या समान डेटा संरचना का उपयोग करते हैं, और इसलिए सूचक एल्गोरिदम नहीं होते हैं: विशेष रूप से, वे आमतौर पर पोलार्ड के आरओ एल्गोरिथ्म पर लागू नहीं किए जा सकते हैं। जहां ये विधियां भिन्न होती हैं, वे कैसे निर्धारित करते हैं कि कौन से मूल्यों को स्टोर करना है। Nivasch के बाद,^[12] हम इन तकनीकों का संक्षेप में सर्वेक्षण करते हैं।

ब्रेंट^[8]पहले से ही अपनी तकनीक की विविधताओं का वर्णन करता है जिसमें सहेजे गए अनुक्रम मानों के सूचकांक किसी संख्या की शक्तियां हैं $R$ दो के अलावा। चुनने के द्वारा $R$ एक के करीब एक संख्या होने के लिए, और अनुक्रम मानों को उन सूचकांकों पर संग्रहीत करना जो लगातार शक्तियों के अनुक्रम के पास हैं $R$ , एक साइकिल डिटेक्शन एल्गोरिथम कई प्रकार के फ़ंक्शन मूल्यांकन का उपयोग कर सकता है जो इष्टतम के मनमाने ढंग से छोटे कारक के भीतर है $λ + μ$ .^[13]^[14]
सेडगेविक, सिजमेंस्की और याओ^[15] उपयोग करने वाली विधि प्रदान करें $M$ मेमोरी सेल और केवल सबसे खराब स्थिति में आवश्यकता होती है $(\lambda +\mu )(1+cM^{-1/2})$ कार्य मूल्यांकन, कुछ स्थिर के लिए $c$ , जिसे वे इष्टतम दिखाते हैं। तकनीक में एक संख्यात्मक पैरामीटर बनाए रखना शामिल है $d$ , किसी तालिका में केवल उन स्थितियों को अनुक्रम में संग्रहीत करना जो गुणक हैं $d$ , और तालिका साफ़ करना और दोहरीकरण करना $d$ जब भी बहुत अधिक मान संग्रहीत किए गए हों।
कई लेखकों ने विशिष्ट बिंदु विधियों का वर्णन किया है जो उनके पदों के आधार पर (सेडगेविक एट अल की विधि में) के बजाय मूल्यों को शामिल करने वाले मानदंड के आधार पर तालिका में फ़ंक्शन मानों को संग्रहीत करते हैं। उदाहरण के लिए, शून्य मॉडुलो के बराबर मान कुछ मान $d$ स्टोर किया जा सकता है।^[16]^[17] अधिक सरलता से, Nivasch^[12]पहले देखे गए मूल्यों के एक यादृच्छिक नमूने को संग्रहीत करने के सुझाव के साथ डीपी वुड्रूफ़ को श्रेय देता है, प्रत्येक चरण पर एक उपयुक्त यादृच्छिक विकल्प बनाता है ताकि नमूना यादृच्छिक बना रहे।
निवासच^[12]एक एल्गोरिथ्म का वर्णन करता है जो मेमोरी की एक निश्चित मात्रा का उपयोग नहीं करता है, लेकिन जिसके लिए उपयोग की जाने वाली मेमोरी की अपेक्षित मात्रा (इस धारणा के तहत कि इनपुट फ़ंक्शन यादृच्छिक है) अनुक्रम लंबाई में लॉगरिदमिक है। इस तकनीक से किसी आइटम को मेमोरी टेबल में स्टोर किया जाता है, जब किसी बाद के आइटम का मान छोटा नहीं होता है। जैसा कि Nivasch दिखाता है, इस तकनीक वाली वस्तुओं को स्टैक (डेटा संरचना) का उपयोग करके बनाए रखा जा सकता है, और प्रत्येक क्रमिक अनुक्रम मान की तुलना केवल स्टैक के शीर्ष से की जानी चाहिए। एल्गोरिथम तब समाप्त हो जाता है जब सबसे छोटे मूल्य के साथ दोहराया अनुक्रम तत्व पाया जाता है। प्रत्येक स्टैक के भीतर मानों को पुन: क्रमित करने के लिए मूल्यों के यादृच्छिक क्रमपरिवर्तन का उपयोग करते हुए एक ही एल्गोरिथ्म को कई ढेरों के साथ चलाना, पिछले एल्गोरिदम के समान समय-अंतरिक्ष व्यापार की अनुमति देता है। हालाँकि, एकल स्टैक के साथ इस एल्गोरिथम का संस्करण भी पॉइंटर एल्गोरिथम नहीं है, यह निर्धारित करने के लिए आवश्यक तुलना के कारण कि दो में से कौन सा मान छोटा है।

कोई भी चक्र पहचान एल्गोरिदम जो अधिकतम स्टोर करता है $M$ इनपुट अनुक्रम से मान कम से कम प्रदर्शन करना चाहिए $(\lambda +\mu )\left(1+{\frac {1}{M-1}}\right)$ समारोह मूल्यांकन।^[18]^[19]

अनुप्रयोग

कई अनुप्रयोगों में साइकिल का पता लगाने का उपयोग किया गया है।

छद्म यादृच्छिक संख्या जनरेटर के चक्र की लंबाई निर्धारित करना इसकी ताकत का एक उपाय है। यह फ्लोयड की विधि का वर्णन करने में नुथ द्वारा उद्धृत अनुप्रयोग है।^[3]ब्रेंट^[8]इस तरीके से एक रैखिक सर्वांगसम जनित्र के परीक्षण के परिणामों का वर्णन करता है; इसकी अवधि विज्ञापित की तुलना में काफी कम निकली। अधिक जटिल जनरेटर के लिए, मूल्यों का क्रम जिसमें चक्र पाया जाना है, जनरेटर के आउटपुट का प्रतिनिधित्व नहीं कर सकता है, बल्कि इसकी आंतरिक स्थिति का प्रतिनिधित्व करता है।
कई संख्या सिद्धांत|संख्या-सैद्धांतिक एल्गोरिदम चक्र का पता लगाने पर आधारित हैं, जिसमें पूर्णांक गुणनखंडन के लिए पोलार्ड का rho एल्गोरिदम शामिल है^[20] और असतत लघुगणक समस्या के लिए उनका संबंधित पोलार्ड का कंगारू एल्गोरिथम।^[21]
क्रिप्टोग्राफी अनुप्रयोगों में, दो अलग-अलग मान x खोजने की क्षमता_μ−-1 और एक्स_λ+μ−-1 कुछ क्रिप्टोग्राफ़िक फ़ंक्शन ƒ द्वारा समान मान x पर मैप किया गया_μ ƒ में कमजोरी का संकेत दे सकता है। उदाहरण के लिए, Quisquater और Delescaille^[17]किसी संदेश की खोज में चक्र पहचान एल्गोरिदम लागू करें और डेटा एन्क्रिप्शन मानक कुंजी की एक जोड़ी जो उस संदेश को उसी एन्क्रिप्टेड मान पर मैप करती है; बर्ट कालिस्की, रॉन रिवेस्ट और एलन शर्मन^[22] डीईएस पर हमला करने के लिए चक्र पहचान एल्गोरिदम का भी उपयोग करें। क्रिप्टोग्राफ़िक हैश फ़ंक्शन में हैश टक्कर खोजने के लिए तकनीक का भी उपयोग किया जा सकता है।^[23]
साइकल डिटेक्शन कुछ प्रकार के कंप्यूटर प्रोग्रामों में अनंत लूपों की खोज के तरीके के रूप में सहायक हो सकता है।^[24]
सेलुलर ऑटोमेटन सिमुलेशन में ऑसिलेटर (सेलुलर ऑटोमेटन) ऑटोमेटन राज्यों के अनुक्रम में चक्र पहचान एल्गोरिदम को लागू करके पाया जा सकता है।^[12]*लिंक की गई सूची डेटा संरचनाओं का आकार विश्लेषण (सॉफ्टवेयर) उन संरचनाओं का उपयोग करके एक एल्गोरिथ्म की शुद्धता को सत्यापित करने के लिए एक तकनीक है। यदि सूची में कोई नोड उसी सूची में पहले के नोड को गलत तरीके से इंगित करता है, तो संरचना एक चक्र बनाएगी जिसे इन एल्गोरिदम द्वारा पता लगाया जा सकता है।^[25] सामान्य लिस्प में, एस-अभिव्यक्ति प्रिंटर, के नियंत्रण में होता है *print-circle* चर, परिपत्र सूची संरचना का पता लगाएं और इसे कॉम्पैक्ट रूप से प्रिंट करें।
टेस्के^[14]कम्प्यूटेशनल समूह सिद्धांत में अनुप्रयोगों का वर्णन करता है: अपने जनरेटर के एक सेट से एबेलियन समूह की संरचना का निर्धारण करना। कालिस्की एट अल के क्रिप्टोग्राफिक एल्गोरिदम।^[22]एक अज्ञात समूह की संरचना का अनुमान लगाने के प्रयास के रूप में भी देखा जा सकता है।
Fich (1981) आकाशीय यांत्रिकी के कंप्यूटर अनुकरण के लिए एक अनुप्रयोग का संक्षेप में उल्लेख करता है, जिसका श्रेय वह विलियम कहाँ को देती है। इस एप्लिकेशन में, एक कक्षीय प्रणाली के चरण स्थान में चक्र का पता लगाने का उपयोग यह निर्धारित करने के लिए किया जा सकता है कि क्या सिस्टम सिमुलेशन की सटीकता के भीतर आवधिक है।^[18]*मैंडेलब्रॉट सेट फ्रैक्टल जनरेशन में छवि निर्माण को गति देने के लिए कुछ प्रदर्शन तकनीकों का उपयोग किया जाता है। उनमें से एक को पीरियड चेकिंग कहा जाता है, जिसमें चक्रों को एक बिंदु कक्षा में खोजना शामिल है। यह लेख wikibooks:Fractals/Iterations_in_the_complex_plane/Mandelbrot_set/mandelbrot#Periodicity_checking तकनीक का वर्णन करता है। आप अन्य स्पष्टीकरण यहां पा सकते हैं। इस तकनीक को लागू करने के लिए कुछ साइकिल डिटेक्शन एल्गोरिदम को लागू करना होगा।

संदर्भ

↑ Joux, Antoine (2009), Algorithmic Cryptanalysis, CRC Press, p. 223, ISBN 9781420070033.
↑ ^2.0 ^2.1 Joux (2009, p. 224).
↑ ^3.0 ^3.1 Knuth, Donald E. (1969), The Art of Computer Programming, vol. II: Seminumerical Algorithms, Addison-Wesley, p. 7, exercises 6 and 7
↑ Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125, describes this algorithm and others
↑ Floyd, R.W. (1967), "Nondeterministic Algorithms", J. ACM, 14 (4): 636–644, doi:10.1145/321420.321422, S2CID 1990464
↑ The Hash Function BLAKE, by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), p. 21, footnote 8
↑ Joux (2009), Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225–226.
↑ ^8.0 ^8.1 ^8.2 ^8.3 Brent, R. P. (1980), "An improved Monte Carlo factorization algorithm" (PDF), BIT Numerical Mathematics , 20 (2): 176–184, doi:10.1007/BF01933190, S2CID 17181286.
↑ Joux (2009), Section 7.1.2, Brent's cycle-finding algorithm, pp. 226–227.
↑ ^10.0 ^10.1 "संग्रहीत प्रति". Archived from the original on 2016-04-14. Retrieved 2017-02-08.
↑ "Hakmem -- Flows and Iterated Functions -- Draft, Not Yet Proofed".
↑ ^12.0 ^12.1 ^12.2 ^12.3 Nivasch, Gabriel (2004), "Cycle detection using a stack", Information Processing Letters, 90 (3): 135–140, doi:10.1016/j.ipl.2004.01.016.
↑ Schnorr, Claus P.; Lenstra, Hendrik W. (1984), "A Monte Carlo factoring algorithm with linear storage", Mathematics of Computation, 43 (167): 289–311, doi:10.2307/2007414, hdl:1887/3815, JSTOR 2007414.
↑ ^14.0 ^14.1 Teske, Edlyn (1998), "A space-efficient algorithm for group structure computation", Mathematics of Computation, 67 (224): 1637–1663, Bibcode:1998MaCom..67.1637T, doi:10.1090/S0025-5718-98-00968-5.
↑ Sedgewick, Robert; Szymanski, Thomas G.; Yao, Andrew C.-C. (1982), "The complexity of finding cycles in periodic functions", SIAM Journal on Computing, 11 (2): 376–390, doi:10.1137/0211030.
↑ van Oorschot, Paul C.; Wiener, Michael J. (1999), "Parallel collision search with cryptanalytic applications", Journal of Cryptology, 12 (1): 1–28, doi:10.1007/PL00003816, S2CID 5091635.
↑ ^17.0 ^17.1 Quisquater, J.-J.; Delescaille, J.-P., "How easy is collision search? Application to DES", Advances in Cryptology – EUROCRYPT '89, Workshop on the Theory and Application of Cryptographic Techniques, Lecture Notes in Computer Science, vol. 434, Springer-Verlag, pp. 429–434, doi:10.1007/3-540-46885-4_43.
↑ ^18.0 ^18.1 Fich, Faith Ellen (1981), "Lower bounds for the cycle detection problem", Proc. 13th ACM Symposium on Theory of Computing, pp. 96–105, doi:10.1145/800076.802462, S2CID 119742106.
↑ Allender, Eric W.; Klawe, Maria M. (1985), "Improved lower bounds for the cycle detection problem", Theoretical Computer Science, 36 (2–3): 231–237, doi:10.1016/0304-3975(85)90044-1.
↑ Pollard, J. M. (1975), "A Monte Carlo method for factorization", BIT, 15 (3): 331–334, doi:10.1007/BF01933667, S2CID 122775546.
↑ Pollard, J. M. (1978), "Monte Carlo methods for index computation $(mod p$ )", Mathematics of Computation, American Mathematical Society, 32 (143): 918–924, doi:10.2307/2006496, JSTOR 2006496, S2CID 235457090.
↑ ^22.0 ^22.1 Kaliski, Burton S., Jr.; Rivest, Ronald L.; Sherman, Alan T. (1988), "Is the Data Encryption Standard a group? (Results of cycling experiments on DES)", Journal of Cryptology, 1 (1): 3–36, doi:10.1007/BF00206323, S2CID 17224075.
↑ Joux (2009), Section 7.5, Collisions in hash functions, pp. 242–245.
↑ Van Gelder, Allen (1987), "Efficient loop detection in Prolog using the tortoise-and-hare technique", Journal of Logic Programming, 4 (1): 23–31, doi:10.1016/0743-1066(87)90020-3.
↑ Auguston, Mikhail; Hon, Miu Har (1997), "Assertions for Dynamic Shape Analysis of List Data Structures", AADEBUG '97, Proceedings of the Third International Workshop on Automatic Debugging, Linköping Electronic Articles in Computer and Information Science, Linköping University, pp. 37–42.

बाहरी संबंध

Gabriel Nivasch, The Cycle Detection Problem and the Stack Algorithm
Tortoise and Hare, Portland Pattern Repository
Floyd's Cycle Detection Algorithm (The Tortoise and the Hare)
Brent's Cycle Detection Algorithm (The Teleporting Turtle)

[1] Joux, Antoine (2009), Algorithmic Cryptanalysis, CRC Press, p. 223, ISBN 9781420070033.

[j224-2] 2.0 ^2.1 Joux (2009, p. 224).

[knuth-3] 3.0 ^3.1 Knuth, Donald E. (1969), The Art of Computer Programming, vol. II: Seminumerical Algorithms, Addison-Wesley, p. 7, exercises 6 and 7

[4] Handbook of Applied Cryptography, by Alfred J. Menezes, Paul C. van Oorschot, Scott A. Vanstone, p. 125, describes this algorithm and others

[5] Floyd, R.W. (1967), "Nondeterministic Algorithms", J. ACM, 14 (4): 636–644, doi:10.1145/321420.321422, S2CID 1990464

[6] The Hash Function BLAKE, by Jean-Philippe Aumasson, Willi Meier, Raphael C.-W. Phan, Luca Henzen (2015), p. 21, footnote 8

[7] Joux (2009), Section 7.1.1, Floyd's cycle-finding algorithm, pp. 225–226.

[brent-8] 8.0 ^8.1 ^8.2 ^8.3 Brent, R. P. (1980), "An improved Monte Carlo factorization algorithm" (PDF), BIT Numerical Mathematics , 20 (2): 176–184, doi:10.1007/BF01933190, S2CID 17181286.

[9] Joux (2009), Section 7.1.2, Brent's cycle-finding algorithm, pp. 226–227.

[gosper-impl-10] 10.0 ^10.1 "संग्रहीत प्रति". Archived from the original on 2016-04-14. Retrieved 2017-02-08.

[11] "Hakmem -- Flows and Iterated Functions -- Draft, Not Yet Proofed".

[nivasch-12] 12.0 ^12.1 ^12.2 ^12.3 Nivasch, Gabriel (2004), "Cycle detection using a stack", Information Processing Letters, 90 (3): 135–140, doi:10.1016/j.ipl.2004.01.016.

[13] Schnorr, Claus P.; Lenstra, Hendrik W. (1984), "A Monte Carlo factoring algorithm with linear storage", Mathematics of Computation, 43 (167): 289–311, doi:10.2307/2007414, hdl:1887/3815, JSTOR 2007414.

[teske-14] 14.0 ^14.1 Teske, Edlyn (1998), "A space-efficient algorithm for group structure computation", Mathematics of Computation, 67 (224): 1637–1663, Bibcode:1998MaCom..67.1637T, doi:10.1090/S0025-5718-98-00968-5.

[15] Sedgewick, Robert; Szymanski, Thomas G.; Yao, Andrew C.-C. (1982), "The complexity of finding cycles in periodic functions", SIAM Journal on Computing, 11 (2): 376–390, doi:10.1137/0211030.

[16] van Oorschot, Paul C.; Wiener, Michael J. (1999), "Parallel collision search with cryptanalytic applications", Journal of Cryptology, 12 (1): 1–28, doi:10.1007/PL00003816, S2CID 5091635.

[qd-17] 17.0 ^17.1 Quisquater, J.-J.; Delescaille, J.-P., "How easy is collision search? Application to DES", Advances in Cryptology – EUROCRYPT '89, Workshop on the Theory and Application of Cryptographic Techniques, Lecture Notes in Computer Science, vol. 434, Springer-Verlag, pp. 429–434, doi:10.1007/3-540-46885-4_43.

[fich-18] 18.0 ^18.1 Fich, Faith Ellen (1981), "Lower bounds for the cycle detection problem", Proc. 13th ACM Symposium on Theory of Computing, pp. 96–105, doi:10.1145/800076.802462, S2CID 119742106.

[19] Allender, Eric W.; Klawe, Maria M. (1985), "Improved lower bounds for the cycle detection problem", Theoretical Computer Science, 36 (2–3): 231–237, doi:10.1016/0304-3975(85)90044-1.

[20] Pollard, J. M. (1975), "A Monte Carlo method for factorization", BIT, 15 (3): 331–334, doi:10.1007/BF01933667, S2CID 122775546.

[21] Pollard, J. M. (1978), "Monte Carlo methods for index computation $(mod p$ )", Mathematics of Computation, American Mathematical Society, 32 (143): 918–924, doi:10.2307/2006496, JSTOR 2006496, S2CID 235457090.

[krs-22] 22.0 ^22.1 Kaliski, Burton S., Jr.; Rivest, Ronald L.; Sherman, Alan T. (1988), "Is the Data Encryption Standard a group? (Results of cycling experiments on DES)", Journal of Cryptology, 1 (1): 3–36, doi:10.1007/BF00206323, S2CID 17224075.

[23] Joux (2009), Section 7.5, Collisions in hash functions, pp. 242–245.

[24] Van Gelder, Allen (1987), "Efficient loop detection in Prolog using the tortoise-and-hare technique", Journal of Logic Programming, 4 (1): 23–31, doi:10.1016/0743-1066(87)90020-3.

[25] Auguston, Mikhail; Hon, Miu Har (1997), "Assertions for Dynamic Shape Analysis of List Data Structures", AADEBUG '97, Proceedings of the Third International Workshop on Automatic Debugging, Linköping Electronic Articles in Computer and Information Science, Linköping University, pp. 37–42.

[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]