बेज़ियर कर्व्स और Arduino स्पीड पर, भाग दो

हम - और आगे से गुजरेंगे

अपनी पिछली पोस्ट में, मैंने दिखाया कि आप बेजियर कर्व (KB) पर अंकों की गणना की गति में कैसे सुधार कर सकते हैं:

1. गणना सूत्रों के रूपांतरण - त्वरण ~ 3 बार।
2. पीटी से एफटी तक लगभग कोई त्वरण नहीं है - लेकिन यह 3 की अनुमति देता है।
3. गुणा और शिफ्ट द्वारा विभाजन का प्रतिस्थापन ऑपरेशन एक और 40% का त्वरण है।

उल्लिखित पोस्ट के अंत में, मैंने कहा कि गणना और भी तेजी से की जा सकती है, लेकिन "लड़के ने क्या कहा - लड़के ने किया।"

मुझे KB पर बिंदु की गणना करने के लिए प्राप्त सूत्र का एक बार फिर से स्मरण दिलाएं

$$

$$P = (A1 * और + B1) * और + C (=> 2 * 2 +)$$

। गति में अगली वृद्धि समस्या की ख़ासियत से संबंधित है - हमें पैरामीटर "और" के विभिन्न मूल्यों पर KB के मान की गणना करने की आवश्यकता नहीं है, लेकिन एक ज्ञात, अतिरिक्त, निश्चित मान (हमारे मान में) को बदलते हुए (इस मामले में) बढ़ते हुए मानों की एक श्रृंखला खोजने के लिए। मामला इकाई), जो आपको नीचे वर्णित तकनीक का उपयोग करने की अनुमति देता है। मेरे समय में, इसे गणना की अंतर विधि कहा जाता था (यदि स्मृति मुझे सही काम करती है, तो कम से कम यह वही था जिसे व्याख्यान में बुलाया गया था), पूरा इंटरनेट आपके निपटान में है, शायद (यहां तक ​​कि निश्चित रूप से), एक और नाम है।

हम मामले को P = A * और (=> 1 *) मानते हैं, और मान लें कि हम P0 का मान कुछ तर्क u0 के साथ जानते हैं। फिर अगले तर्क u0 + 1 के साथ मूल्य की गणना P = A * (u0 + 1) = A * u0 + A = P0 + A (=> 1+) के रूप में की जा सकती है। किसी भी सटीकता को खोने के बिना, हम गुणा ऑपरेशन को जोड़ने के लिए सक्षम थे, इसके अलावा ऑपरेशन, जो बहुत तेज है।

अब एक और अधिक जटिल उदाहरण पी = ए * और * (=> 2 *), हम सादृश्य पी = ए * (और + 1) * (और + 1) = ए * (और * और + 2 * और + 1) पर विचार करते हैं। = A * और * और + 2 * A * और + A = P0 + 2 * A * और + A (=> 2 * 2))। पहली नज़र में, हम कुछ भी नहीं जीते थे, लेकिन अगर हम पहले से ए '= 2 * ए की गणना करते हैं, तो हमें (=> 1 * 2 +) मिलता है, एक जीत काफी संभव है। लेकिन हम प्राप्त की गई अभिव्यक्ति और 'ए * पर प्राप्त की गई चीज़ों पर रोक नहीं लगाएंगे और पहले से ज्ञात तकनीक को लागू करेंगे, तो हमें दो चर पर दो ऑपरेशन मिलेंगे: पी = पी + ए' + ए; A '= A' + A (=> 3+)। अगर हम इस बात को ध्यान में रखते हैं कि A का प्रारंभिक मान A से अधिक हो सकता है, तो सामान्य तौर पर दो गुणा के बजाय केवल दो जोड़ होते हैं। हां, हमें दो अतिरिक्त चर प्राप्त करने थे, लेकिन यह एक क्लासिक एक्सचेंज है - हम समय के लिए स्मृति के साथ भुगतान करते हैं।

यह केवल सही प्रारंभिक मानों की गणना करने के लिए ही रहता है, लेकिन यह केवल पुनरावृत्तियों की शुरुआत में किया जाता है, और यदि पैरामीटर का प्रारंभिक मान u = 0 है, तो यह आम तौर पर तुच्छ P = 0, A '= A है। हम कई पुनरावृत्तियों पर अपनी पद्धति का परीक्षण करेंगे (यह पूरी तरह अनावश्यक है, सही ढंग से लागू गणित गलत उत्तर नहीं दे सकता है), लेकिन यह हमें बेहतर समझने की अनुमति देगा कि क्या हो रहा है। इतना
पुनरावृति 0: और = 0; पी = 0 (सच); ए '= ए; ए '' = 2 * ए;
पुनरावृति 1: और = 1; पी = 0 + ए '= 0 + ए = ए (सच); ए '= ए' + ए '' = ए + 2 * ए = 3 * ए;
पुनरावृति 2: और = 2; पी = ए + 3 * ए = 4 * ए (सच); ए '= 3 * ए + 2 * ए = 5 * ए;
पुनरावृति 3: और = 3; पी = 9 * ए (सच); ए '= 7 * ए और इतने पर।

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

विस्तारित रूप में KB के लिए हमारी मूल अभिव्यक्ति को फिर से लिखें

$$

$$P = A1 * और * और + B1 * और + C$$

फिर इस विधि का उपयोग करके गणना के लिए हमें पहले शब्द (और दो चर) के लिए 2+, दूसरे शब्द के लिए 1+ (और एक चर) और सब कुछ एक साथ जोड़ने के लिए 2+ (=> 5+) चाहिए। यह उम्मीद की जा सकती है कि इस तरह के (गलत) दृष्टिकोण 2 * 2 + की तुलना में लाभ प्राप्त करेंगे, लेकिन सब कुछ बहुत बेहतर है। जाहिर है, अतिरिक्त ऑपरेशन एडिटिव (धन्यवाद, कप्तान) है, इसलिए आप शब्दों को समूह बना सकते हैं और नए शब्दों के साथ निरंतर शब्दों को बदल सकते हैं, जो निम्नलिखित एल्गोरिदम देता है:

1. पी = सी के प्रारंभिक मूल्य; ए '= ए 1 + बी 1; ए '' = 2 * ए 1;
2. अगले चरण पर P = P + A '; ए '= ए' + ए '' (=> 2+), जो निस्संदेह हॉर्नर की योजना से तेज है।

हम अपने एल्गोरिथ्म को एक कार्यक्रम के रूप में कार्यान्वित करते हैं (यह उतना तुच्छ नहीं है जितना यह प्रतीत हो सकता है, क्योंकि सादगी के लिए मैं पाली की आवश्यकता के बारे में भूल गया था, लेकिन यह बहुत मुश्किल नहीं है ... 20 मिनट के लिए), हम कम्प्यूटेशनल जटिलता प्राप्त करते हैं (=> 2 + 1 >>) और माप गति - यह प्रति चक्र 140 (एक और 3 गुना गति से वृद्धि) चक्र प्रति निकला, लेकिन यह लगभग एक आदर्श परिणाम है। आदर्श (एक अर्थ में) विकल्प प्राप्त करने के लिए हमें क्या करना है, सूत्र में परिचालनों के आयाम पर ध्यान देना है। अब हम लंबे (32-बिट) पूर्णांक पर सभी ऑपरेशन करते हैं, और यह कुछ स्थानों पर अनावश्यक हो सकता है। यदि हम ऑपरेंड की क्षमता को न्यूनतम आवश्यक तक कम कर देते हैं, तो हम 20-25 प्रतिशत लाभ प्राप्त कर सकते हैं, लेकिन इसके लिए हमें कोडांतरक पर स्विच करना होगा (सी के पास ऐसे कार्यों के लिए उपयुक्त साधन नहीं हैं) और मूल समस्या के डेटा का सावधानीपूर्वक विश्लेषण करें। यह तय करना पाठक के लिए है या नहीं, यह करने के लिए, हमने पहले से ही "भोले" दृष्टिकोण की तुलना में 1900/140 = 13 से अधिक बार गणनाओं में तेजी लाई है।

एल्गोरिथ्म के कार्यान्वयन पर अंतिम नोट यह है कि हम अभी भी डिवीजन ऑपरेशन को लगातार गुणा से बदलकर बाहर करते हैं, जिसे हम प्रारंभिक डेटा उत्पन्न करते समय और 8 के निरंतर मल्टीपल द्वारा शिफ्ट करते समय ध्यान में रखते हैं। यह थोड़ा अलग-अलग समय के साथ विभिन्न तरीकों से किया जा सकता है, इस तरह के प्रयोगों को एक जिज्ञासु पाठक के ध्यान में रखते हुए। ।

हालांकि, एक समस्या पूरी तरह से अप्रत्याशित रूप से उत्पन्न हुई - हम स्पष्ट रूप से 32 बिट नंबरों पर दो अतिरिक्त संचालन देखते हैं, जो 4 + 4 = 8 घड़ी चक्र लेना चाहिए, ऑपरेंड भेजने के लिए एक और 8 * 3 * 2 = 48 घड़ी चक्र डालें, शिफ्ट परिणाम प्राप्त करने के लिए 4 घड़ी चक्र, 4 गणना प्रक्रिया को कॉल करने के लिए एक घड़ी चक्र और वापसी, और चक्र के आयोजन के लिए 4 घड़ी चक्र - जहां से एक और 60 घड़ी चक्र स्पष्ट नहीं हैं। पहले, हमने केवल सैकड़ों घड़ी चक्रों की पृष्ठभूमि के खिलाफ इसे नोटिस नहीं किया था, लेकिन अब आप ध्यान दे सकते हैं। अत्यधिक उपाय आसानी से मिल गए थे - चक्र में अनावश्यक डिबगिंग ऑपरेशन थे, यदि आप सावधानीपूर्वक सब कुछ साफ करते हैं, तो केवल 120 उपाय शेष रहते हैं और प्रत्येक का उद्देश्य काफी समझ में आता है (ठीक है, इतना पूरी तरह से स्पष्ट नहीं है, लेकिन अभी भी)। अगला, हम खाली चक्र के निष्पादन समय का पता लगाते हैं - 22 उपाय, मुझे आश्चर्य है कि वे इस समय वहां क्या कर रहे हैं, लेकिन ओह अच्छी तरह से, और वास्तविक गणना समय को साफ करें, जो कि 98 चक्र होगा। ध्यान दें कि प्राप्त कार्य त्वरण का अनुमान बदल जाता है: 1900/140 = 13 के बजाय हम प्राप्त करते हैं (1900-50) / (140-40) = 19 बार, जो कोई व्यावहारिक अर्थ नहीं देता है, क्योंकि चक्र अभी भी आवश्यक है, लेकिन यह आपको इसे और अधिक बढ़ाने की अनुमति देता है आत्म सम्मान।

और आखिरी टिप्पणी - जैसा कि यह देखना आसान है, हमने केवल fleas को ढूंढना और खत्म करना शुरू कर दिया जब हम बड़े हिरण बीटल और उनके (fleas) अस्तित्व के साथ निपटा और स्पष्ट रूप से, महत्वपूर्ण। मैं प्रदर्शन के संदर्भ में कार्यक्रमों का अनुकूलन करते समय वास्तव में इस दृष्टिकोण (और मैं इस सिफारिश में अकेला नहीं हूं) की दृढ़ता से अनुशंसा करता हूं।

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