फ़्लोटिंग प्वाइंट स्क्वायर रूट निर्धारित करना

Question

मैं फ़्लोटिंग पॉइंट नंबर के वर्ग रूट को कैसे निर्धारित करूं? क्या न्यूटन-रैफसन विधि एक अच्छा तरीका है? मेरे पास कोई हार्डवेयर वर्ग रूट नहीं है। मेरे पास हार्डवेयर डिवाइड भी नहीं है (लेकिन मैंने फ्लोटिंग पॉइंट डिवाइड लागू किया है)।

यदि संभव हो, तो मैं जितना संभव हो उतना विभाजन की संख्या को कम करना पसंद करूंगा क्योंकि वे इतने महंगे हैं।

इसके अलावा, पुनरावृत्तियों की कुल संख्या को कम करने के लिए प्रारंभिक अनुमान क्या होना चाहिए ???

आपको बहुत बहुत धन्यवाद!

Answer 1

जब आप स्क्वायर रूट की गणना करने के लिए न्यूटन-रैफसन का उपयोग करते हैं, तो आप वास्तव में पारस्परिक वर्ग रूट खोजने के लिए पुनरावृत्ति का उपयोग करना चाहते हैं (जिसके बाद आप केवल इनपुट द्वारा गुणा कर सकते हैं - गोल करने के लिए कुछ देखभाल के साथ - वर्ग रूट का उत्पादन)।

अधिक सटीक: हम फ़ंक्शन f(x) = x^-2 - n का उपयोग करते हैं। जाहिर है, अगर f(x) = 0, तो x = 1/sqrt(n)।यह न्यूटन यात्रा को जन्म देता है:

x_(i+1) = x_i - f(x_i)/f'(x_i) 
     = x_i - (x_i^-2 - n)/(-2x_i^-3) 
     = x_i + (x_i - nx_i^3)/2 
     = x_i*(3/2 - 1/2 nx_i^2) 

ध्यान दें कि (वर्गमूल के लिए यात्रा के विपरीत), पारस्परिक वर्गमूल के लिए इस यात्रा नहीं डिवीजनों शामिल है, तो यह आम तौर पर और अधिक कुशल है।

मैंने आपके प्रश्न में विभाजित किया है कि आपको पहिया को फिर से आविष्कार करने के बजाय मौजूदा सॉफ्ट-फ्लोट पुस्तकालयों को देखना चाहिए। वह सलाह यहां भी लागू होती है। यह फ़ंक्शन पहले से ही मौजूदा सॉफ्ट-फ्लोट पुस्तकालयों में लागू किया जा चुका है।

---

संपादित करें: sqrt(612): प्रश्नकर्ता अभी भी भ्रमित हो रहा है, तो चलो एक उदाहरण भी काम करें। 6121.1953125 x 2^9 (या b1.0011001 x 2^9 है, यदि आप बाइनरी पसंद करते हैं)। f * 2^(2m) के रूप में इनपुट लिखने के लिए एक्सपोनेंट (9) के भी हिस्से को खींचें, जहां m एक पूर्णांक है और f सीमा [1,4) में है। फिर हम होगा:

sqrt(n) = sqrt(f * 2^2m) = sqrt(f)*2^m 

हमारे उदाहरण के लिए इस कमी को लागू करने देता है f = 1.1953125 * 2 = 2.390625 (b10.011001) और m = 4। अब 0.5 के शुरुआती अनुमान का उपयोग करके x = 1/sqrt(f) खोजने के लिए न्यूटन-रैफसन पुनरावृत्ति करें (जैसा कि मैंने एक टिप्पणी में देखा है, यह अनुमान सभी f के लिए अभिसरण करता है, लेकिन आप प्रारंभिक अनुमान के रूप में रैखिक अनुमान का उपयोग करके काफी बेहतर कर सकते हैं):

x_0 = 0.5 
x_1 = x_0*(3/2 - 1/2 * 2.390625 * x_0^2) 
    = 0.6005859... 
x_2 = x_1*(3/2 - 1/2 * 2.390625 * x_1^2) 
    = 0.6419342... 
x_3 = 0.6467077... 
x_4 = 0.6467616... 

तो प्रारंभिक अनुमान के साथ भी (अपेक्षाकृत खराब), हम 1/sqrt(f) = 0.6467616600226026 के वास्तविक मूल्य पर तेजी से अभिसरण प्राप्त करते हैं। जाहिर है sqrt (612) = २४.७३८६३३ ...

, अगर आप सही राउंडिंग चाहते हैं, सावधान विश्लेषण की जरूरत है सुनिश्चित करें कि आप:

अब हम बस अंतिम परिणाम को इकट्ठा:

sqrt(f) = x_n * f = 1.5461646... 
sqrt(n) = sqrt(f) * 2^m = 24.738633... 

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

यदि आप स्पष्ट रूप से अवशिष्ट की जांच किए बिना गोल करने को सही करना चाहते हैं, तो आपको 2p + 2 बिट्स (जहां पी स्रोत और गंतव्य प्रकार की सटीकता है) की सटीकता के लिए sqrt (f) की गणना करने की आवश्यकता है। हालांकि, आप एसकर्ट (एफ) को पी बिट्स, स्क्वायर जो मूल्य से थोड़ा अधिक कंप्यूटिंग करने की रणनीति भी ले सकते हैं, और अगर आवश्यक हो तो पीछे की ओर एक को समायोजित कर सकते हैं (जो अक्सर सस्ता होता है)।

वर्ग अच्छा है कि यह एक यूनरी फ़ंक्शन है, जो कमोडिटी हार्डवेयर पर एकल-सटीक व्यवहार्यता के लिए संपूर्ण परीक्षण करता है।

आप ओएस एक्स सॉफ्ट-फ्लोट sqrtf opensource.apple.com पर फ़ंक्शन पा सकते हैं, जो ऊपर वर्णित एल्गोरिदम का उपयोग करता है (मैंने लिखा है, जैसा कि होता है)। यह एपीएसएल के तहत लाइसेंस प्राप्त है, जो आपकी आवश्यकताओं के लिए उपयुक्त हो सकता है या नहीं।

Answer 2

सबसे आसान लागू करने के लिए (आप भी एक कैलकुलेटर में यह लागू कर सकते हैं):

def sqrt(x, TOL=0.000001): 
    y=1.0 
    while(abs(x/y -y) > TOL): 
     y= (y+x/y)/2.0 
    return y 

यह Raphson न्यूटन बिल्कुल बराबर है:

y (नया) = y - च (y)/च '(y)

च (y) = y^2-एक्स और च' (y) = 2y

स्थानापन्न इन मूल्यों:

वाई (नया) = वाई - (वाई^2-एक्स)/2y = (वाई^2 + एक्स)/2y = (वाई + एक्स/वाई)/2

यदि विभाजन महंगा है तो आपको विचार करना चाहिए: http://en.wikipedia.org/wiki/Shifting_nth-root_algorithm ।

स्थानांतरण एल्गोरिदम:।

हमें आप दो नंबर ए और बी ऐसी है कि कम से कम महत्वपूर्ण अंकों (1 के बराबर) ख से बड़ा है और ख के लिए केवल एक बिट के बराबर है है मान लेते हैं (उदाहरण के लिए एक = 1000 और ख = 10)। चलो एस (बी) = log_2 (बी) (जो बी में थोड़ा मूल्य 1 का स्थान है)।

मान लें कि हम पहले से ही^2 के मान को जानते हैं। अब (ए + बी)^2 = ए^2 + 2 एबी + बी^2। एक^2 पहले से ही ज्ञात है, 2ab: शिफ्ट ए द्वारा एस (बी) +1, बी^2: शिफ्ट बी द्वारा बी (बी)।

एल्गोरिथ्म:

Initialize a such that a has only one bit equal to one and a^2<= n < (2*a)^2. 
Let q=s(a).  
b=a 
sqra = a*a 

For i = q-1 to -10 (or whatever significance you want): 
    b=b/2 
    sqrab = sqra + 2ab + b^2 
    if sqrab > n: 
     continue 
    sqra = sqrab 
    a=a+b 

n=612 
a=10000 (16) 

sqra = 256 

Iteration 1: 
    b=01000 (8) 
    sqrab = (a+b)^2 = 24^2 = 576 
    sqrab < n => a=a+b = 24 

Iteration 2: 
    b = 4 
    sqrab = (a+b)^2 = 28^2 = 784 
    sqrab > n => a=a 

Iteration 3: 
    b = 2 
    sqrab = (a+b)^2 = 26^2 = 676 
    sqrab > n => a=a 

Iteration 4: 
    b = 1 
    sqrab = (a+b)^2 = 25^2 = 625 
    sqrab > n => a=a 

Iteration 5: 
    b = 0.5 
    sqrab = (a+b)^2 = 24.5^2 = 600.25 
    sqrab < n => a=a+b = 24.5 

Iteration 6: 
    b = 0.25 
    sqrab = (a+b)^2 = 24.75^2 = 612.5625 
    sqrab < n => a=a 


Iteration 7: 
    b = 0.125 
    sqrab = (a+b)^2 = 24.625^2 = 606.390625 
    sqrab < n => a=a+b = 24.625 

and so on. 

Answer 3

रेंज [1,4) पर वर्गमूल के एक अच्छा सन्निकटन

def sqrt(x): 
    y = x*-0.000267 
    y = x*(0.004686+y) 
    y = x*(-0.034810+y) 
    y = x*(0.144780+y) 
    y = x*(-0.387893+y) 
    y = x*(0.958108+y) 
    return y+0.315413 

है अपने चल बिन्दु संख्या सामान्यीकृत करें तो अपूर्णांश रेंज [1,4) में है, पर उपरोक्त एल्गोरिथ्म का उपयोग यह, और फिर एक्सपोनेंट को 2 से विभाजित करें। कहीं भी कोई फ़्लोटिंग पॉइंट डिवीजन नहीं।

उसी CPU समय बजट के साथ आप शायद अधिक बेहतर कर सकते हैं, लेकिन यह एक अच्छा प्रारंभिक बिंदु जैसा प्रतीत होता है।

Answer 4

शायद (अभी भी) inverse square root और कोड की 10 पंक्तियों को खोजने के लिए सबसे तेज़ कार्यान्वयन जो मैं सबसे अधिक पसंद करता हूं।

यह न्यूटन अनुमान पर आधारित है, लेकिन कुछ quirks के साथ। इसके आसपास एक great story भी है।