algorithm - मैं कैसे निर्धारित करूं कि पीआई की मेरी गणना सटीक है या नहीं?




math language-agnostic pi (5)

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

इसलिए, कार्यक्रम लिखते समय मैं एक समस्या पर फंस गया, जैसा कि सभी एल्गोरिदम के साथ: मुझे कैसे पता चलेगा कि मैंने जिन अंकों की गणना की है, वे सटीक हैं?


Answers

पाप और कोस के लिए बिजली श्रृंखला को तेजी से परिवर्तित करने के लिए आप (उचित रूप से) का उपयोग करके sin(pi/2) (या cos(pi/2) की गणना करने की कोशिश कर सकते हैं। (यहां तक ​​कि बेहतर: तेजी से अभिसरण के लिए निकट x=0 गणना करने के लिए विभिन्न दोगुनी सूत्रों का उपयोग करें।)

बीटीडब्ल्यू, tan(x) लिए श्रृंखला का उपयोग करने से बेहतर है, कंप्यूटिंग के साथ एक ब्लैक बॉक्स के रूप में cos(x) कहते हैं (उदाहरण के लिए आप ऊपर के रूप में टेलर श्रृंखला का उपयोग कर सकते हैं) न्यूटन के माध्यम से रूट खोज करना है। वहां निश्चित रूप से बेहतर एल्गोरिदम हैं, लेकिन यदि आप बहुत से अंकों को सत्यापित नहीं करना चाहते हैं तो यह पर्याप्त होना चाहिए (और यह लागू करने में मुश्किल नहीं है, और आपको यह समझने के लिए केवल कुछ कैलकुस चाहिए कि यह क्यों काम करता है।)


टेलर श्रृंखला पीआई अनुमानित करने का एक तरीका है। जैसा कि ध्यान दिया गया है यह धीरे-धीरे अभिसरण करता है।

टेलर श्रृंखला का आंशिक रकम अगली अवधि के कुछ गुणक के भीतर पीआई के वास्तविक मूल्य से दूर दिखाया जा सकता है।

अनुमानित पीआई के अन्य साधनों में अधिकतम त्रुटि की गणना करने के समान तरीके हैं।

हम इसे जानते हैं क्योंकि हम इसे गणितीय साबित कर सकते हैं।


आप कई दृष्टिकोणों का उपयोग कर सकते हैं और देख सकते हैं कि वे एक ही जवाब में अभिसरण करते हैं या नहीं। या कुछ नेट से पकड़ो। Chudnovsky एल्गोरिदम आमतौर पर पीआई की गणना करने की एक बहुत तेज विधि के रूप में प्रयोग किया जाता है। http://www.craig-wood.com/nick/articles/pi-chudnovsky/


चूंकि मैं पीआई के अधिकांश अंकों के लिए वर्तमान विश्व रिकॉर्ड धारक हूं, इसलिए मैं अपने दो सेंट जोड़ दूंगा:

जब तक कि आप वास्तव में एक नया विश्व रिकॉर्ड स्थापित नहीं कर रहे हैं, आम अभ्यास सिर्फ ज्ञात मूल्यों के खिलाफ गणना अंकों को सत्यापित करना है। तो यह काफी आसान है।

असल में, मेरे पास एक वेबपृष्ठ है जो उनके खिलाफ गणनाओं को सत्यापित करने के उद्देश्य से अंकों के स्निपेट सूचीबद्ध करता है: http://www.numberworld.org/digits/Pi/

लेकिन जब आप विश्व रिकॉर्ड क्षेत्र में जाते हैं, तो इसके खिलाफ तुलना करने के लिए कुछ भी नहीं है।

ऐतिहासिक रूप से, गणना किए गए अंकों को सत्यापित करने के लिए मानक दृष्टिकोण सही है, दूसरे एल्गोरिदम का उपयोग करके अंकों को पुन: सम्मिलित करना। तो अगर गणना गणना खराब हो जाती है, तो अंत में अंक मेल नहीं खाते।

यह आम तौर पर आवश्यक समय की दोगुनी से अधिक है (क्योंकि दूसरा एल्गोरिदम आमतौर पर धीमा होता है)। लेकिन जब आप कभी भी पहले से गणना किए गए अंकों और एक नए विश्व रिकॉर्ड के अनचाहे क्षेत्र में घूमते हैं तो गणना किए गए अंकों को सत्यापित करने का यही एकमात्र तरीका है।

उन दिनों में जहां सुपरकंप्यूटर रिकॉर्ड स्थापित कर रहे थे, दो अलग-अलग एजीएम एल्गोरिदम का उपयोग आमतौर पर किया जाता था:

ये दोनों O(N log(N)^2) एल्गोरिदम हैं जो लागू करने के लिए काफी आसान थे।

हालांकि, आजकल, चीजें थोड़ा अलग हैं। पिछले तीन विश्व रिकॉर्ड में, दो गणना करने के बजाय, हमने सबसे तेज़ ज्ञात फॉर्मूला ( चुडनोव्स्की फॉर्मूला ) का उपयोग करके केवल एक गणना की:

यह एल्गोरिदम लागू करने के लिए बहुत कठिन है, लेकिन यह एजीएम एल्गोरिदम से बहुत तेज है।

फिर हम अंक निष्कर्षण के लिए बीबीपी सूत्रों का उपयोग करके बाइनरी अंक सत्यापित करते हैं।

यह सूत्र आपको इससे पहले सभी अंकों की गणना किए बिना मनमाना बाइनरी अंकों की गणना करने की अनुमति देता है। तो यह पिछले कुछ गणना बाइनरी अंकों को सत्यापित करने के लिए प्रयोग किया जाता है। इसलिए यह पूर्ण गणना से बहुत तेज है।

इसका लाभ यह है:

  1. केवल एक महंगी गणना की आवश्यकता है।

नुकसान यह है:

  1. बेली-बोरवेन-प्लौफ ( बीबीपी ) फॉर्मूला के कार्यान्वयन की आवश्यकता है।
  2. बाइनरी से दशमलव तक रेडिक्स रूपांतरण को सत्यापित करने के लिए एक अतिरिक्त चरण की आवश्यकता है।

मैंने पिछले कुछ अंकों को सत्यापित करने के कुछ विवरणों पर गौर किया है कि सभी अंक सही हैं। लेकिन यह देखना आसान है क्योंकि किसी भी गणना त्रुटि अंतिम अंकों के लिए प्रचारित होगी।

अब यह अंतिम चरण (रूपांतरण की पुष्टि) वास्तव में काफी महत्वपूर्ण है। पिछले विश्व रिकॉर्ड धारकों में से एक ने वास्तव में हमें इस पर बुलाया क्योंकि, शुरुआत में, मैंने पर्याप्त काम नहीं किया कि यह कैसे काम करता है।

तो मैंने अपने ब्लॉग से इस स्निपेट को खींच लिया है:

N = # of decimal digits desired
p = 64-bit prime number

बाइनरी अंकगणितीय का उपयोग कर आधार 10 अंकगणितीय और बी का उपयोग कर गणना करें।

यदि A = B , तो "बेहद उच्च संभावना" के साथ, रूपांतरण सही है।

आगे पढ़ने के लिए, मेरे ब्लॉग पोस्ट पीआई - 5 ट्रिलियन अंक देखें


यहां कार्यान्वयन वीबीएनईटी है, यह कार्यान्वयन आपको आपके द्वारा पास किए गए एनम मूल्य के आधार पर केएम या माइल्स में परिणाम देगा।

Public Enum DistanceType
    Miles
    KiloMeters
End Enum

Public Structure Position
    Public Latitude As Double
    Public Longitude As Double
End Structure

Public Class Haversine

    Public Function Distance(Pos1 As Position,
                             Pos2 As Position,
                             DistType As DistanceType) As Double

        Dim R As Double = If((DistType = DistanceType.Miles), 3960, 6371)

        Dim dLat As Double = Me.toRadian(Pos2.Latitude - Pos1.Latitude)

        Dim dLon As Double = Me.toRadian(Pos2.Longitude - Pos1.Longitude)

        Dim a As Double = Math.Sin(dLat / 2) * Math.Sin(dLat / 2) + Math.Cos(Me.toRadian(Pos1.Latitude)) * Math.Cos(Me.toRadian(Pos2.Latitude)) * Math.Sin(dLon / 2) * Math.Sin(dLon / 2)

        Dim c As Double = 2 * Math.Asin(Math.Min(1, Math.Sqrt(a)))

        Dim result As Double = R * c

        Return result

    End Function

    Private Function toRadian(val As Double) As Double

        Return (Math.PI / 180) * val

    End Function

End Class




algorithm math language-agnostic pi