मैं इस वर्ग रूट विधि को कैसे सुधार सकता हूं?

Question

मुझे पता है कि यह होमवर्क असाइनमेंट की तरह लगता है, लेकिन ऐसा नहीं है। हाल ही में मुझे कुछ गणितीय परिचालनों जैसे कि साइन, स्क्वायर रूट इत्यादि करने के लिए इस्तेमाल किए गए एल्गोरिदम में दिलचस्पी है। फिलहाल, मैं सी # में कंप्यूटिंग स्क्वायर जड़ों की Babylonian method लिखने की कोशिश कर रहा हूं।

public static double SquareRoot(double x) { 
    if (x == 0) return 0; 

    double r = x/2; // this is inefficient, but I can't find a better way 
         // to get a close estimate for the starting value of r 
    double last = 0; 
    int maxIters = 100; 

    for (int i = 0; i < maxIters; i++) { 
     r = (r + x/r)/2; 
     if (r == last) 
      break; 
     last = r; 
    } 

    return r; 
} 

यह सिर्फ ठीक काम करता है और .नेट फ्रेमवर्क के Math.Sqrt के रूप में ठीक उसी जवाब का उत्पादन() विधि हर बार:

अब तक, मैं इस किया है। जैसा कि आप शायद अनुमान लगा सकते हैं, हालांकि, यह मूल विधि (लगभग 800 टिकों से) धीमा है। मुझे पता है कि यह विशेष विधि देशी विधि से कभी तेज नहीं होगी, लेकिन मैं सोच रहा हूं कि क्या कोई अनुकूलन है जो मैं कर सकता हूं।

एकमात्र ऑप्टिमाइज़ेशन मैंने तुरंत देखा था कि गणना 100 गुना चल जाएगी, जवाब देने के बाद भी (जिस बिंदु पर, आर हमेशा एक ही मूल्य होगा)। इसलिए, मैंने यह देखने के लिए एक त्वरित जांच जोड़ा कि क्या नया गणना मूल्य पहले गणना मूल्य के समान है और लूप से बाहर निकलता है। दुर्भाग्यवश, इसने गति में बहुत अंतर नहीं बनाया, लेकिन ऐसा करने के लिए सही काम की तरह लग रहा था।

और इससे पहले कि आप कहें "क्यों न केवल Math.Sqrt() का उपयोग करें?" ... मैं इसे सीखने के अभ्यास के रूप में कर रहा हूं और वास्तव में किसी भी उत्पादन कोड में इस विधि का उपयोग करने का इरादा नहीं रखता हूं।

Answer 1

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

Answer 2

लूप तोड़ने और फिर वापस लौटने के बजाय, आप बस आर वापस कर सकते हैं। प्रदर्शन में कोई उल्लेखनीय वृद्धि प्रदान नहीं कर सकता है।

Answer 3

आप r = x >> 1;

/2 (भी अन्य जगह में आप 2 से डिवाइस) के बजाय

कोशिश कर सकते हैं। यह आपको थोड़ी सी बढ़त दे सकता है। मैं 100 को लूप में भी ले जाऊंगा। शायद कुछ भी नहीं, लेकिन हम यहां टिकों के बारे में बात कर रहे हैं।

बस इसे अभी जांच रहा है।

संपादित करें: >> में फिक्स्ड, लेकिन यह युगल के लिए काम नहीं करता है, इसलिए कभी नहीं। 100 की इनलाइनिंग ने मुझे कोई गति वृद्धि नहीं दी।

Answer 4

आप यहां क्या कर रहे हैं यह है कि आप Newton's method of finding a root निष्पादित करते हैं। तो आप बस कुछ और अधिक कुशल रूट-खोज एल्गोरिदम का उपयोग कर सकते हैं। आप इसे here खोजना शुरू कर सकते हैं।

Answer 5

थोड़ा बदलाव के साथ विभाजन को 2 से बदलना उस बड़े अंतर को बनाने की संभावना नहीं है; यह देखते हुए कि विभाजन निरंतर है, मुझे आशा है कि संकलक आपके लिए ऐसा करने के लिए पर्याप्त स्मार्ट होगा, लेकिन आप इसे देखने की कोशिश भी कर सकते हैं।

आपको लूप से बाहर निकलने में सुधार होने की अधिक संभावना है, इसलिए या तो एक चर में नई आर स्टोर करें और पुराने आर के साथ तुलना करें, या एक चर में x/r स्टोर करें और तुलना करने से पहले आर के विरुद्ध तुलना करें जोड़ और विभाजन।

Answer 6

सहिष्णुता को परिभाषित करें और बाद में पुनरावृत्ति उस सहिष्णुता के भीतर आने पर वापस आएं।

eps = 1e-10 // pick any small number 
if (Math.Abs(r-last) < eps) break; 

के रूप में:

Answer 7

ठीक है, मूल Sqrt() फ़ंक्शन शायद सी # में लागू नहीं किया गया है, यह संभवतः निम्न-स्तर की भाषा में किया जाएगा, और यह निश्चित रूप से एक अधिक कुशल एल्गोरिदम का उपयोग करेगा। तो इसकी गति से मिलान करने की कोशिश करना शायद व्यर्थ है।

हालांकि, हेक्विविट के लिए अपने फ़ंक्शन को अनुकूलित करने की कोशिश करने के संबंध में, आपके द्वारा लिंक किया गया विकिपीडिया पृष्ठ "प्रारंभिक अनुमान" को 2^मंजिल (डी/2) होने की अनुशंसा करता है, जहां डी बाइनरी अंकों की संख्या का प्रतिनिधित्व करता है रेखावृत्त। आप इसे एक प्रयास दे सकते हैं, मुझे और कुछ नहीं दिख रहा है जिसे आपके कोड में महत्वपूर्ण रूप से अनुकूलित किया जा सकता है।

Answer 8

जब से तुम ने कहा कि नीचे कोड काफी तेजी से नहीं था, इस प्रयास करें:

static double guess(double n) 
    { 
     return Math.Pow(10, Math.Log10(n)/2); 
    } 

यह बहुत ही सटीक हो सकता है और उम्मीद है कि तेजी से करना चाहिए।

यहां प्रारंभिक अनुमान के लिए कोड है here। यह बहुत अच्छा प्रतीत होता है। इस कोड का प्रयोग करें, और तब आपको तब भी पुनरावृत्त करना चाहिए जब तक कि मूल्य अंतर के एक ईपीएसलॉन में परिवर्तित न हो जाएं।

public static double digits(double x) 
    { 
     double n = Math.Floor(x); 
     double d; 

     if (d >= 1.0) 
     { 
      for (d = 1; n >= 1.0; ++d) 
      { 
       n = n/10; 
      } 
     } 
     else 
     { 
      for (d = 1; n < 1.0; ++d) 
      { 
       n = n * 10; 
      } 
     } 


     return d; 
    } 

    public static double guess(double x) 
    { 
     double output; 
     double d = Program.digits(x); 

     if (d % 2 == 0) 
     { 
      output = 6*Math.Pow(10, (d - 2)/2); 
     } 
     else 
     { 
      output = 2*Math.Pow(10, (d - 1)/2); 
     } 

     return output; 
    } 

Answer 9

आपकी विधि के साथ, प्रत्येक पुनरावृत्ति सही बिट्स की संख्या को दोगुना करता है।

शुरुआती 4 बिट्स (उदाहरण के लिए) प्राप्त करने के लिए तालिका का उपयोग करके, आपके पास पहले पुनरावृत्ति के बाद 8 बिट्स होंगे, फिर दूसरे के बाद 16 बिट होंगे, और चौथे पुनरावृत्ति के बाद आपको आवश्यक सभी बिट्स (double स्टोर के बाद से मंथिसा के 52 + 1 बिट्स)।

टेबल लुकअप के लिए, आप [0.5,1 [और इनपुट से एक्सपोनेंट (फ्रीएक्स जैसे फ़ंक्शन का उपयोग करके) में मंटिसा निकालें, फिर [64,256 [मल्टीसा को 2 की उपयुक्त शक्ति द्वारा गुणा करके उपयोग करें।

mantissa *= 2^K 
exponent -= K 

इसके बाद, आपका इनपुट नंबर अभी भी mantissa*2^exponent है। एक एक्सपोनेंट प्राप्त करने के लिए के 7 या 8 होना चाहिए। आप मंथिसा के अभिन्न अंग की सभी वर्ग जड़ों वाली तालिका से पुनरावृत्तियों के लिए प्रारंभिक मान प्राप्त कर सकते हैं। मंथिसा के वर्ग रूट आर प्राप्त करने के लिए 4 पुनरावृत्तियों का पालन करें। परिणाम r*2^(exponent/2) है, जो ldexp जैसे फ़ंक्शन का उपयोग करके बनाया गया है।

संपादित करें। मैंने इसे चित्रित करने के लिए नीचे कुछ सी ++ कोड डाला। बेहतर परीक्षण के साथ ओपी का फ़ंक्शन sr1 2^24 वर्ग जड़ों की गणना करने के लिए 2.78s लेता है; मेरा फ़ंक्शन sr2 1.42 लेता है, और हार्डवेयर sqrt 0.12s लेता है।

#include <math.h> 
#include <stdio.h> 

double sr1(double x) 
{ 
    double last = 0; 
    double r = x * 0.5; 
    int maxIters = 100; 
    for (int i = 0; i < maxIters; i++) { 
    r = (r + x/r)/2; 
    if (fabs(r - last) < 1.0e-10) 
     break; 
    last = r; 
    } 
    return r; 
} 

double sr2(double x) 
{ 
    // Square roots of values in 0..256 (rounded to nearest integer) 
    static const int ROOTS256[] = { 
    0,1,1,2,2,2,2,3,3,3,3,3,3,4,4,4,4,4,4,4,4,5,5,5,5,5,5,5,5,5,5,6,6,6,6,6,6,6,6,6,6,6,6, 
    7,7,7,7,7,7,7,7,7,7,7,7,7,7,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,8,9,9,9,9,9,9,9,9,9,9,9,9,9, 
    9,9,9,9,9,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,11,11,11,11,11, 
    11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,12,12,12, 
    12,12,12,12,12,12,12,12,12,12,12,12,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13,13, 
    13,13,13,13,13,13,13,13,13,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14,14, 
    14,14,14,14,14,14,14,14,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15,15, 
    15,15,15,15,15,15,15,15,15,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16,16 }; 

    // Normalize input 
    int exponent; 
    double mantissa = frexp(x,&exponent); // MANTISSA in [0.5,1[ unless X is 0 
    if (mantissa == 0) return 0; // X is 0 
    if (exponent & 1) { mantissa *= 128; exponent -= 7; } // odd exponent 
    else { mantissa *= 256; exponent -= 8; } // even exponent 
    // Here MANTISSA is in [64,256[ 

    // Initial value on 4 bits 
    double root = ROOTS256[(int)floor(mantissa)]; 

    // Iterate 
    for (int it=0;it<4;it++) 
    { 
     root = 0.5 * (root + mantissa/root); 
    } 

    // Restore exponent in result 
    return ldexp(root,exponent>>1); 
} 

int main() 
{ 
    // Used to generate the table 
    // for (int i=0;i<=256;i++) printf(",%.0f",sqrt(i)); 

    double s = 0; 
    int mx = 1<<24; 
    // for (int i=0;i<mx;i++) s += sqrt(i); // 0.120s 
    // for (int i=0;i<mx;i++) s += sr1(i); // 2.780s 
    for (int i=0;i<mx;i++) s += sr2(i); // 1.420s 
} 

Answer 10

मैं इसे सीखने के उद्देश्यों के लिए भी देख रहा हूं। मैंने कोशिश की दो संशोधनों में रुचि हो सकती है।

पहले x0 में एक पहले के आदेश टेलर श्रृंखला सन्निकटन उपयोग करने के लिए किया गया था:

Func<double, double> fNewton = (b) => 
    { 
     // Use first order taylor expansion for initial guess 
     // http://www27.wolframalpha.com/input/?i=series+expansion+x^.5 
     double x0 = 1 + (b - 1)/2; 
     double xn = x0; 
     do 
     { 
      x0 = xn; 
      xn = (x0 + b/x0)/2; 
     } while (Math.Abs(xn - x0) > Double.Epsilon); 
     return xn; 
    }; 

दूसरा एक तिहाई आदेश (और अधिक महंगी) की कोशिश करना, पुनरावृति

Func<double, double> fNewtonThird = (b) => 
    { 
     double x0 = b/2; 
     double xn = x0; 
     do 
     { 
      x0 = xn; 
      xn = (x0*(x0*x0+3*b))/(3*x0*x0+b); 
     } while (Math.Abs(xn - x0) > Double.Epsilon); 
     return xn; 
    }; 

मैं एक सहायक बनाया गया था कार्य करने के लिए विधि

public static class Helper 
{ 
    public static long Time(
     this Func<double, double> f, 
     double testValue) 
    { 
     int imax = 120000; 
     double avg = 0.0; 
     Stopwatch st = new Stopwatch(); 
     for (int i = 0; i < imax; i++) 
     { 
      // note the timing is strictly on the function 
      st.Start(); 
      var t = f(testValue); 
      st.Stop(); 
      avg = (avg * i + t)/(i + 1); 
     } 
     Console.WriteLine("Average Val: {0}",avg); 
     return st.ElapsedTicks/imax; 
    } 
} 

मूल विधि तेज थी, लेकिन फिर, बी ई दिलचस्प :)

Answer 11

float InvSqrt (float x){ 
    float xhalf = 0.5f*x; 
    int i = *(int*)&x; 
    i = 0x5f3759df - (i>>1); 
    x = *(float*)&i; 
    x = x*(1.5f - xhalf*x*x); 
    return x;} 

यह मेरा पसंदीदा तेज़ वर्ग रूट है। असल में यह वर्ग रूट के विपरीत है, लेकिन अगर आप चाहें तो इसे उलटा कर सकते हैं .... मैं यह नहीं कह सकता कि अगर आप स्क्वायर रूट चाहते हैं और विपरीत वर्ग रूट नहीं चाहते हैं, तो यह ठीक है, लेकिन यह ठीक है ।
http://www.beyond3d.com/content/articles/8/

Answer 12

की जगह "/ 2" से "* 0.5" इस ~ 1.5 गुना मेरी मशीन पर तेजी से बनाता है, लेकिन निश्चित रूप से लगभग रूप में तेजी से नहीं देशी कार्यान्वयन के रूप में।