बिगइन्टर (System.Numerics.BigInteger) के वर्ग रूट की गणना करें

Question

.NET 4.0 System.Numerics.BigInteger मनमाने ढंग से बड़े पूर्णांक के लिए प्रकार प्रदान करता है। मुझे BigInteger के वर्ग रूट (या एक उचित अनुमान - उदाहरण के लिए, पूर्णांक वर्ग रूट) की गणना करने की आवश्यकता है। इसलिए मुझे पहिया को फिर से लागू करने की ज़रूरत नहीं है, क्या किसी के पास इसके लिए एक अच्छी विस्तार विधि है?

Answer 1

एक मनमाना परिशुद्धता के लिए एक वर्गमूल गणना करने के लिए सबसे सरल संभव तरह से शायद Newton's method.

Answer 2

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

static uint isqrt(uint x) 
{ 
    int b=15; // this is the next bit we try 
    uint r=0; // r will contain the result 
    uint r2=0; // here we maintain r squared 
    while(b>=0) 
    { 
     uint sr2=r2; 
     uint sr=r; 
        // compute (r+(1<<b))**2, we have r**2 already. 
     r2+=(uint)((r<<(1+b))+(1<<(b+b)));  
     r+=(uint)(1<<b); 
     if (r2>x) 
     { 
      r=sr; 
      r2=sr2; 
     } 
     b--; 
    } 
    return r; 
} 

, एक ऐसी ही विधि है जो केवल इसके अलावा और पाली, 'Dijkstras स्क्वायर रूट' कहा जाता है का उपयोग करता है उदाहरण के लिए यहाँ के लिए समझाया उपयोग कर सकते हैं:

• http://lib.tkk.fi/Diss/2005/isbn9512275279/article3.pdf

Answer 3

Check if BigInteger is not a perfect square एक जावा BigInteger के पूर्णांक वर्गमूल गणना करने के लिए कोड है। यहां इसे एक विस्तार विधि के रूप में सी # में अनुवादित किया गया है।

public static BigInteger Sqrt(this BigInteger n) 
    { 
     if (n == 0) return 0; 
     if (n > 0) 
     { 
      int bitLength = Convert.ToInt32(Math.Ceiling(BigInteger.Log(n, 2))); 
      BigInteger root = BigInteger.One << (bitLength/2); 

      while (!isSqrt(n, root)) 
      { 
       root += n/root; 
       root /= 2; 
      } 

      return root; 
     } 

     throw new ArithmeticException("NaN"); 
    } 

    private static Boolean isSqrt(BigInteger n, BigInteger root) 
    { 
     BigInteger lowerBound = root*root; 
     BigInteger upperBound = (root + 1)*(root + 1); 

     return (n >= lowerBound && n < upperBound); 
    } 

अनौपचारिक परीक्षण इंगित करता है कि यह छोटे पूर्णांक के लिए Math.Sqrt से लगभग 75X धीमी है। वीएस प्रोफाइलर हॉटस्कॉट्स के रूप में isSqrt में गुणाओं को इंगित करता है।

Answer 4

लघु जवाब: (लेकिन सावधान रहना, अधिक जानकारी के लिए नीचे देखें)

Math.Pow(Math.E, BigInteger.Log(pd)/2) 

कहाँ pdBigInteger जिस पर आप वर्गमूल कार्रवाई करने के लिए चाहते हैं प्रतिनिधित्व करता है।

लांग जवाब और स्पष्टीकरण:

इस समस्या को समझने के लिए एक और तरीका है कैसे वर्ग जड़ों और लॉग काम को समझने है।

यदि आपके पास के लिए हल करने के लिए समीकरण 5^x = 25 है, तो हमें लॉग का उपयोग करना होगा। इस उदाहरण में, मैं प्राकृतिक लॉग का उपयोग करूंगा (अन्य अड्डों में लॉग भी संभव है, लेकिन प्राकृतिक लॉग आसान तरीका है)।

5^x = 25 

नए सिरे से लिखना, हमने:

x(ln 5) = ln 25 

एक्स अलग करने के लिए, हम

x = ln 25/ln 5 

हम देखते हैं इस x = 2 में परिणाम होती हैं। लेकिन चूंकि हम पहले से ही एक्स (x = 2, 5^2 में) जानते हैं, चलिए बदलते हैं जो हम नहीं जानते हैं और एक नया समीकरण लिखते हैं और नए अज्ञात के लिए हल करते हैं। एक्स को वर्ग रूट ऑपरेशन का परिणाम बनने दें।यह हमें

2 = ln 25/ln x 

देता एक्स अलग करने के लिए नए सिरे से लिखना, हम

ln x = (ln 25)/2 

है लॉग निकालने के लिए, अब हम प्राकृतिक लॉग की एक विशेष पहचान और विशेष संख्या ई का उपयोग करें। विशेष रूप से, e^ln x = x। समीकरण को फिर से लिखने अब हमें

e^ln x = e^((ln 25)/2) 

देता बाएं हाथ की ओर सरल बनाना, हमारे पास

x = e^((ln 25)/2) 

जहां x 25 का वर्गमूल आप किसी भी जड़ या संख्या के लिए इस विचार का विस्तार कर सकता है हो जाएगा, और एक्स की yth रूट के लिए सामान्य सूत्र e^((ln x)/y) बन जाता है।

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

// A sample generated public key modulus 
var pd = BigInteger.Parse("101017638707436133903821306341466727228541580658758890103412581005475252078199915929932968020619524277851873319243238741901729414629681623307196829081607677830881341203504364437688722228526603134919021724454060938836833023076773093013126674662502999661052433082827512395099052335602854935571690613335742455727"); 
var sqrt = Math.Pow(Math.E, BigInteger.Log(pd)/2); 

Console.WriteLine(sqrt); 

नोट:BigInteger.Log() विधि एक डबल देता है, तो दो चिंताओं उत्पन्न होती हैं। 1) संख्या कमजोर है, और 2) Log() पर ऊपरी सीमा है BigInteger इनपुट के लिए संभाल सकता है। ऊपरी सीमा की जांच करने के लिए, हम प्राकृतिक लॉग के लिए सामान्य रूप देख सकते हैं, जो ln x = y है। दूसरे शब्दों में, e^y = x। चूंकि doubleBigInteger.Log() का रिटर्न प्रकार है, तो यह सबसे बड़ा BigInteger होगा क्योंकि ईdouble.MaxValue तक बढ़ाया जाएगा। मेरे कंप्यूटर पर, यह e^1.79769313486232E+308 होगा। अपर्याप्तता अनचाहे है। कोई भी BigDecimal लागू करना चाहते हैं और BigInteger.Log() अद्यतन करें?

उपभोक्ता सावधान रहें, लेकिन यह आपको पड़ोस में लाएगा, और परिणाम को स्क्वायर करने से मूल इनपुट के समान संख्या उत्पन्न होती है, इतने सारे अंकों तक और रेडग्रीनकोड के उत्तर के रूप में सटीक नहीं। हैप्पी (वर्ग) rooting! ;)

Answer 5

आप इसे अपनी पसंद के भाषा और परिवर्तनीय प्रकार में परिवर्तित कर सकते हैं। जावास्क्रिप्ट में एक छोटा सा स्क्वायर्रूट है (मेरे लिए सबसे ताजा) जो 1 + 3 + 5 का लाभ उठाता है ... + nth odd number = n^2। सभी चर पूर्णांक हैं, और यह केवल जोड़ता है और घटाता है।

var truncSqrt=function(n){ 
var oddNumber=1; 
var result=0; 
while (n>=oddNumber) { 
    n-=oddNumber; 
    oddNumber+=2; 
    result++; } 
return result; }`