Calculating the floor of y**(1/m)

तकनीकी सारांश: $y^{1/m}$ के फ्लोर (Floor) की गणना करना

समस्या विवरण
यह शोध पत्र एक प्राकृतिक संख्या $y$ के $m$-वें मूल के पूर्णांक फ्लोर (integer floor), जिसे $\lfloor y^{1/m} \rfloor$ के रूप में दर्शाया गया है, को निर्धारित करने की कम्प्यूटेशनल समस्या पर आधारित है, जहाँ $y > 2$ और $m > 1$ है। यह गणना संख्या सिद्धांत (number theory) में एक मौलिक चरण है, विशेष रूप से यह पहचानने के लिए कि क्या एक प्राकृतिक संख्या $y$ एक पूर्ण घात (perfect power) है (अर्थात, क्या ऐसे प्राकृतिक नंबर $x$ और $m > 1$ मौजूद हैं कि $y = x^m$ हो)। जबकि पारंपरिक दृष्टिकोण $x$ को $[2, \lg y]$ की सीमा के भीतर खोजने के लिए बाइनरी सर्च (binary search) का उपयोग करते हैं, लेखक का कहना है कि अंकगणित के बिट मॉडल (bit model) में ऐसे तरीके कम्प्यूटेशनल रूप से कुशल नहीं हैं, हालांकि वे व्यावहारिक हैं।

कार्यप्रणाली (Methodology)
शोध पत्र न्यूटन-रैप्सन विधि (Newton-Raphson method) पर आधारित दो अलग-अलग एल्गोरिदम प्रस्तावित करता है, जो वास्तविक-संख्या मूल खोजने (real-number root finding) से पूर्णांक अंकगणित (integer arithmetic) में अनुकूलित हैं। दोनों एल्गोरिदम का लक्ष्य एक प्रारंभिक अनुमान $x_0$ को तब तक परिष्कृत करना है जब तक कि अभिसरण (convergence) न हो जाए, जिससे $x = \lfloor y^{1/m} \rfloor$ प्राप्त हो सके।

• एल्गोरिदम 1 (प्रत्यक्ष अनुकूलन - Direct Adaptation):
  यह दृष्टिकोण $f(x) = y - x^m = 0$ के लिए मानक न्यूटन-रैप्सन पुनरावृत्ति (iteration) को संशोधित करता है। वास्तविक-मान वाले अपडेट स्टेप $x_{i+1} = x_i + \frac{y - x_i^m}{m x_i^{m-1}}$ को भिन्न (fraction) पर फ्लोर फंक्शन लागू करके पूर्णांक अंकगणित में परिवर्तित किया जाता है:
  $$x_{i+1} = x_i + \left\lfloor \frac{y - x_i^m}{m x_i^{m-1}} \right\rfloor$$
  प्रारंभिक मान $x_0$ को $y$ के लघुगणक (logarithm) से प्राप्त किया जाता है ताकि यह सुनिश्चित हो सके कि $x_0 \ge y^{1/m}$। अभिसरण विश्लेषण जटिल है, जो तीन मामलों में अंतर करता है:

1. एक घटती हुई अनुक्रम (decreasing sequence) जो स्थिर होती है ($x_{n+1} = x_n$)।
2. एक घटती हुई अनुक्रम जो "फ्लिप" (flip) होकर बढ़ती है ($x_{n+1} > x_n$)।
3. निरंतर गिरावट (Continued decrease)।
   एल्गोरिदम तब समाप्त होता है जब कोई फ्लिप या दोहराव (repeat) होता है, जिसके बाद समाधान को $x_n$ या $x_n + 1$ के रूप में निर्धारित किया जाता है, जिसकी पुष्टि इस जाँच से की जाती है कि $x_n^m \le y < (x_n+1)^m$।

• एल्गोरिदम 2 (परिमार्जित पूर्णांक पुनरावृत्ति - Refined Integer Recurrence):
  यह दृष्टिकोण न्यूटन-रैप्सन सूत्र के एक अलग बीजगणितीय पुनर्गठन का उपयोग करता है:
  $$x_{i+1} = \left\lfloor \frac{(m-1)x_i + \lfloor y/x_i^{m-1} \rfloor}{m} \right\rfloor$$
  यह सूत्र पूर्णांक अखंडता बनाए रखने के लिए $\lfloor \lfloor x \rfloor + m/n \rfloor = \lfloor x + m/n \rfloor$ के गुण का लाभ उठाता है। प्रारंभिक मान $x_0$ को $2^{\lceil (\lfloor \lg y \rfloor + 1)/m \rceil}$ के रूप में चुना जाता है, जो सुनिश्चित करता है कि $x_0 \ge y^{1/m}$।
  एल्गोरिदम 2 के लिए अभिसरण प्रमाण अधिक सुव्यवस्थित है। यह स्थापित करता है कि अनुक्रम गैर-बढ़ता (non-increasing) रहता है जब तक कि $x_i > y^{1/m}$ हो। एल्गोरिदम तब रुक जाता है जब $x_{i+1} \ge x_i$ होता है, जिस बिंदु पर प्रमाण यह दर्शाता है कि $x_i$ का मान $\lfloor y^{1/m} \rfloor$ के बराबर होना चाहिए।

मुख्य योगदान

1. पूर्णांक न्यूटन-रैप्सन सूत्र (Integer Newton-Raphson Formulations): शोध पत्र $\lfloor y^{1/m} \rfloor$ की गणना के लिए न्यूटन-रैपसन विधि के दो विशिष्ट पूर्णांक-आधारित अनुकूलन प्रस्तुत करता है।
2. अभिसरण प्रमाण (Convergence Proofs): दोनों एल्गोरिदम के लिए कठोर गणितीय प्रमाण प्रदान किए गए हैं, जो यह स्थापित करते हैं कि वे सही पूर्णांक फ्लोर मान पर अभिसरित होते हैं। प्रमाण वास्तविक मूल $Y = y^{1/m}$ के सापेक्ष अनुक्रम के व्यवहार का विश्लेषण करते हैं, जिसमें उन मामलों को भी संभाला जाता है जहाँ अनुक्रम ओवरशूट (overshoot) करता है या स्थिर होता है।
3. प्रारंभिक मान का चयन (Initial Value Selection): दोनों एल्गोरिदम में $x_0$ के लिए विशिष्ट, कम्प्यूटेशनल रूप से कुशल विधियाँ (बिट शिफ्ट और लघुगणक का उपयोग करके) शामिल हैं जो गारंटी देती हैं कि अनुक्रम वास्तविक मूल के ऊपर या उसके बराबर से शुरू हो।

परिणाम
शोध पत्र $y$ और $m$ के विभिन्न मानों (जैसे, $y=108, m=8$; $y=96889010407, m=13$) का उपयोग करके दोनों एल्गोरिदम के लिए दृष्टांत उदाहरण प्रदान करता है।

• दोनों एल्गोरिदम सफलतापूर्वक सही पूर्णांक मूल पर अभिसरित होते हैं।
• प्रदान किए गए उदाहरणों में, एल्गोरिदम 1 को आमतौर पर एल्गोरिदम 2 की तुलना में कम पुनरावृत्तियों (iterations) की आवश्यकता होती है। उदाहरण के लिए, $y=52523350144$ और $m=7$ के मामले में, एल्गोरिदम 1 4 चरणों (32, 34, 34) में अभिसरित होता है, जबकि एल्गोरिदम 2 7 चरणों (64, 54, 46, 40, 36, 34, 34) में लेता है।
• लेखक बाद के उदाहरणों में प्रदर्शन के अंतर का श्रेय एल्गोरिदम 1 में प्रारंभिक मान $x_0$ के अधिक लक्षित चयन को देते हैं।

महत्व और दावे
शोध पत्र स्पष्ट रूप से कहता है कि पूर्णांक समस्याओं के लिए न्यूटन-रैप्सन का उपयोग करने की तकनीकें नवीन नहीं हैं, और मौजूदा साहित्य (विशेष रूप से संदर्भ [2]) का हवाला देता है। फलस्वरूप, लेखक इन विशिष्ट विधियों और उनके विस्तृत प्रमाणों के लिए इन विधियों का एक "अभिलेखागार संदर्भ" (archival reference) प्रदान करने का इरादा रखते हैं। यह कार्य पूर्ण घात पहचान के लिए न्यूटन-रैप्सन के अनुकूलन को औपचारिक रूप देने का कार्य करता है, जो बिट-जटिलता मॉडल (bit-complexity models) में बाइनरी सर्च के लिए एक संभावित रूप से अधिक कुशल विकल्प प्रदान करता है, हालांकि शोध पत्र स्थापित विधियों पर श्रेष्ठता के दावों के संबंध में विनम्र बना हुआ है।