बेज़ियर कर्व्स, अरुडिनो गति और एक दिलचस्प साइट के सवाल पर, या मैंने सप्ताहांत कैसे बिताया

“कोई भी डॉल्फिन के साथ ग्रे विरोधाभास को हल कर सकता है, और आप इसे डॉल्फ़िन के बिना करने की कोशिश करते हैं। "

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

(आवश्यक नोट - पिछले सप्ताहांत का मतलब था, यह हमेशा इस तरह होता है - कार्यक्रम लिखने में कुछ घंटों की आवश्यकता होती है, इसके बारे में रिपोर्ट लिखना और सार्वजनिक परिवहन में पांच दिनों की यात्रा पूरी नहीं होती है।)

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

हम इस समस्या को बताते हैं - हम चरम बिंदु A और B द्वारा परिभाषित बेज़ियर वक्र पर बिंदुओं के निर्देशांक की गणना करना चाहते हैं और काल्पनिक फोकस C. जितनी जल्दी हो सके। वक्र पर बिंदु P की गणना करने का सूत्र दिया गया है।

$$

$$(1) P = T * T * B + 2 * T * (1-T) * C + (1-T) * (1-T) * A$$

जहाँ T 0 से 1 तक भिन्न होता है। (विकी पर वे लिखते हैं कि यह सूत्र एक समय में गुप्त था, यह उस तरह अजीब था, लेकिन सब कुछ संभव है)। यह स्पष्ट है कि हम इसे एक जटिल रूप में नहीं लेंगे, इसके बजाय हम एक्स और वाई निर्देशांक के लिए अलग-अलग खोज करेंगे। हम इस सूत्र का उपयोग करके गणना की जटिलता का अनुमान लगाएंगे, बस इस अभिव्यक्ति में अंकगणितीय संचालन के संकेतों की संख्या की गिनती करके - 7 गुणन और 5 जोड़ (=> 7 * 5 + 5 +। )। यह संभव है कि एक अच्छा संकलक (और अब सभी संकलक अच्छे हैं और पूरी तरह से अनुकूलन करेंगे यदि आप स्पष्ट रूप से उन्हें मना नहीं करते हैं) लागत को 7 * 3 + तक कम कर देगा, हालांकि अग्रिम में गणना करके (1-टी) उसकी मदद करना बेहतर होगा। आमतौर पर, एक अच्छा संकलक आमतौर पर चमत्कार काम कर सकता है यदि सूत्र में सभी मानों को स्थिरांक द्वारा दर्शाया जाता है, लेकिन हम मानते हैं कि सभी मान सांख्यिकीय रूप से अपरिभाषित हैं।

भाग एक, गणित

हम अनुकूलन प्रक्रिया शुरू करते हैं, जिसके लिए हम कोष्ठक का विस्तार करते हैं और T पर शब्दों को समूहित करते हैं (हो सकता है कि किसी दिन कंपाइलर हमारे लिए ऐसा कर सके, लेकिन अभी तक यह कार्य प्राकृतिक बुद्धिमत्ता को सौंपा गया है),

$$

$$(2) P = T * T * (B + A-2 * C) + T * 2 * (C-A) + A$$

=> 5 * 5 +, जो स्पष्ट रूप से 7 * 5 + के प्रारंभिक मूल्य से बेहतर है, लेकिन अपेक्षाकृत बेहतर 7 * 3 + को अभी भी माना जाना चाहिए।

यदि हम अतिरिक्त ऑपरेशन को एक के रूप में पूरा करने के लिए समय लेते हैं, तो गुणा को पूरा करने का समय एक नियम के रूप में, एक से कम नहीं होगा, लेकिन अब यह एमके के कार्यान्वयन पर निर्भर करता है (पहले लिखा - वास्तुकला पर, लेकिन यह पूरी तरह सच नहीं है)। जब क्रिस्टल पर कोई हार्डवेयर गुणक नहीं होता है, तो गुणा निष्पादन का समय एक से अधिक दसियों (30+) गुना होगा, और जब यह मौजूद होता है, तो यह कई गुना (1-6) होगा। इसलिए, हम आत्मविश्वास से विश्वास कर सकते हैं कि इसके अलावा गुणा को प्रतिस्थापित करने से लगभग हमेशा निष्पादन समय में लाभ (और अक्सर महत्वपूर्ण) मिलता है। ठीक है, हम तुरंत ध्यान देंगे कि फिक्स्ड-पॉइंट नंबरों से एक फ़्लोटिंग पॉइंट (हम इस तथ्य के प्रमाण को छोड़ दें) से संक्रमण निष्पादन समय में वृद्धि के लिए 20+ गुना तक बढ़ जाता है (संरेखण यहाँ बहुत प्रभावशाली है), लेकिन केवल गुणन के लिए मामूली वृद्धि के लिए । इसलिए, फ्लोटिंग-पॉइंट नंबरों के लिए, जोड़ और गुणा का समय अलग-अलग होता है, विशेष रूप से सापेक्ष शब्दों में (हम अधिकतम 2 बार उम्मीद कर सकते हैं), लेकिन वे अभी भी अलग-अलग हैं और गुणा के पक्ष में नहीं हैं, इसलिए यहां एक लाभ है।

पिछले पैराग्राफ पर लौटते हुए, हम पाते हैं कि पीटी के लिए 5 * 5 + रेटिंग में 7 * 3 + से अधिक महत्वपूर्ण लाभ नहीं होना चाहिए, लेकिन हमारे पास अभी भी भंडार है। इस तथ्य पर ध्यान दें कि हमें बेज़ियर वक्र पर बिंदुओं के मूल्यों की गणना करनी चाहिए जब पैरामीटर टी बदलता है, और वक्र के अन्य सभी पैरामीटर तय किए जाते हैं (लेकिन स्थिर नहीं, लेकिन अफ़सोस की बात है), तो शेष सूत्र की गणना अग्रिम में की जा सकती है और प्राप्त कर सकते हैं

$$

$$(3) पी = टी * टी * ए 1 + टी * बी 1 + ए$$

=> 3 * 2 +, कहां $$$A1 = A + B-2 * C$और $$$B1 = 2 * (C-A)$पहले से ही अच्छा है, लेकिन यदि आप हॉर्नर की योजना को याद करते हैं और लिखते हैं

$$

$$(4) पी = टी * (टी * ए 1 + बी 1) + ए$$

=> 2 * 2 +, फिर "माथे पर" निर्णय की तुलना में हमें 2 से अधिक बार जीतना होगा, लगभग 3, और ये अनुकूलन पूरी तरह से स्पष्ट हैं।

आइए अभ्यास के साथ सिद्धांत की जांच करें (हालांकि यह पूरी तरह से बेमानी है, हम अपने अनुमानों में आश्वस्त हैं, लेकिन अचानक मैंने संकलक को कम करके आंका), जिसके लिए हमें वास्तविक हार्डवेयर पर विभिन्न विकल्पों के निष्पादन के वास्तविक समय को मापने की आवश्यकता है। ठीक है, यह सिर्फ इतना हुआ है कि घर पर मेरे पास विभिन्न कंपनियों के एमके के लिए सभी प्रकार के डिबग बोर्ड हैं (जिनमें ल्यूमिनरी माइक्रो या इंटेल एडिसन से डिबग जैसी रारियां शामिल हैं, अब एक खरीदने की कोशिश करें), लेकिन एक भी Arduino बोर्ड नहीं है ("ठीक है) हमारे पास अनानास नहीं हैं ”)। यह एक मृत अंत की तरह प्रतीत होगा, लेकिन विकल्प हैं - एक बहुत ही दिलचस्प साइट tinkercad.com हमारी सहायता के लिए आती है, जिस पर आप Arduino मॉड्यूल का उपयोग करके ब्रेडबोर्ड पर अपना सर्किट बना सकते हैं, एक स्केच लिख सकते हैं और तुरंत इसे निष्पादित कर सकते हैं। उसी समय, आप ब्रेकपॉइंट्स सेट कर सकते हैं, प्रोग्राम स्टेप बाय स्टेप निष्पादित कर सकते हैं और यहां तक ​​कि (एक असली Arduino के लिए एक अभूतपूर्व चीज) ब्रेकडाउन के समय चर के मूल्यों को देख सकते हैं।

हम इस साइट की ओर मुड़ते हैं और मापना शुरू करते हैं। शुरू करने के लिए, हम संचालन के निष्पादन समय के बारे में हमारी धारणाओं की जांच करते हैं और आसपास की परिस्थितियों से मुक्त होने के बाद, हम पूर्णांक के बाद निम्नलिखित डेटा प्राप्त करते हैं:

8 + 8 => 8 - 1 हरा, 16 + 16 => 16 - 2,
8 * 8 => 16 - 2, 16 * 16 => 16 - 14 (केवल एक चीज जो अप्रत्याशित रूप से बदल गई, मैंने सोचा कि 4 * 2 + 4 * 2 = 16 प्राप्त करना है, दिलचस्प अनुकूलन हैं)
8/8 => 8 - 230, 16/16 => 16 - 230।

अंतिम दो अंकों पर ध्यान दें, यह उनसे स्पष्ट है कि यदि हम वास्तव में जल्दी से गिनती करना चाहते हैं तो विभाजन ऑपरेशन निषिद्ध है। अब (अंत में) हम पीटीएस की संख्या पर 24-बिट मंटिसा के साथ संचालन करने के लिए लगने वाले समय को मापते हैं
a + b - 126 (और ऑपरेंड पर बहुत अधिक निर्भर करता है), एक * b - 140, a / b - 482।
डेटा हमारी सैद्धांतिक मान्यताओं के साथ अच्छी तरह से जुड़ा हुआ है, यह स्पष्ट है कि इस एमके पर बोर्ड पर एक हार्डवेयर कार्यान्वयन है: गुणा के लिए, विभाजन के लिए, संचालन के लिए नहीं, पीटी।

अब हम पूर्ण गणना के समय को मापना शुरू करते हैं। हम डिजाइन ब्यूरो पर ए = 140, बी = 120, सी = 70 और 170 समान रूप से वितरित बिंदुओं का निर्माण करते हैं। इन मूल्यों का ठीक-ठीक मूल्यांकन क्यों किया जाता है - प्रदर्शन का मूल्यांकन करते समय उन्हें निर्दिष्ट पोस्ट में दिया गया था। नीचे एल्गोरिदम और इसी परीक्षण के निष्पादन का समय है।

फॉर्मूला (1) => 20ms या 1,900 घड़ी चक्र प्रति नमूना
फॉर्मूला (1) => 18ms या 1660 घड़ी चक्र प्रति नमूना (अलग से 1-T पर विचार करें)
फॉर्मूला (2) => 16ms या 1540 प्रति चक्र घड़ी चक्र
फॉर्मूला (3) => प्रति नमूना 10ms या 923 घड़ी चक्र
सूत्र (4) => 8ms या 762 उपाय प्रति गणना

यह देखा जा सकता है कि निष्पादन समय (20ms से 8ms तक) में परिणामी कमी अपेक्षित रूप से अच्छी तरह से संबंधित है और हम गणना को 2 गुना से अधिक गति देने में सक्षम थे। ध्यान दें कि पूरी तरह से स्पष्ट विचारों और गणित के अलावा, हाई स्कूल के पाठ्यक्रम से परे नहीं, हमें ज़रूरत नहीं थी।

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

भाग दो, कम्प्यूटिंग

एक बार एल्गोरिथ्म में संशोधन समाप्त हो जाने के बाद, केवल डेटा संरचनाएं बनी रहती हैं और हम निश्चित-बिंदु संख्याओं की मिट्टी में प्रवेश करते हैं। यहां हम कई नुकसान पाएंगे जो हमने पीटी के लिए नहीं सोचा था - रेंज और सटीकता (सामान्य तौर पर, पीटी के लिए इन मुद्दों के बारे में सोचना चाहिए, लेकिन यहां सब कुछ सरल है, हमारे लिए बहुत कुछ किया गया है)। एफटी के आवश्यक प्रतिनिधित्व को निर्धारित करने के लिए समस्या का एक छोटा अध्ययन करना आवश्यक है (उपरोक्त पोस्ट 9.7 में चयनित, परिणामों से देखते हुए, यह स्पष्ट रूप से अपर्याप्त है), लेकिन मैं थोड़ा अलग रास्ता लेने का प्रस्ताव करता हूं। वैसे, अगर हम अंतराल पर 170 कदम नहीं उठाते हैं, लेकिन 128 (मुझे इस कदम से हमें कोई कारण नहीं दिखता है), तो यह विचार हमारे लिए पूरी तरह से उपयुक्त होगा। यदि हम इस तथ्य को ध्यान में रखते हैं कि KB को परिभाषित करने वाले स्थिरांक पूर्णांक द्वारा दिए गए हैं, और केवल पैरामीटर T को फॉर्म के एक अंश द्वारा दर्शाया जा सकता है और / और हम स्क्रीन पर रेंडर करने के लिए परिणाम का उपयोग करेंगे, अर्थात, पूर्णांक निर्देशांक में अनुवाद कर सकते हैं, तब हम कर सकते हैं पूर्णांक में सब कुछ करें, जो बहुत तेजी से प्रक्रिया करता है।

हम केवल अंतिम सूत्र का उपयोग करते हैं और इसे नए अंकन में फिर से लिखते हैं

$$

$$(5) पी = यू / यू * (यू / यू * ए 1 + बी 1) + ए$$

(=> 2 * 2 + 2 /), जहां A1 और B1 की गणना पीटी के लिए उसी तरह की जाती है। जाहिर है, सभी संख्या पूर्णांक हैं और संबंधित कार्यों को बहुत तेजी से निष्पादित किया जाना चाहिए। पूर्णांक विभाजन (2/3 = 1! = 1.5) के संचालन के दौरान सटीकता न खोने और बहुत ही अंतिम समय में विभाजन करने के लिए, हम सूत्र को सूत्र में थोड़ा बदल देते हैं

$$

$$(6) पी = ((और * ए 1 + बी 1 * और) / और * और + ए * और) / और$$

(=> 4 * 2 + 2 /)। सभी एफटी नंबर, इसलिए हम इस एल्गोरिथ्म को लागू करते हैं और प्राप्त करते हैं ... यहां आप हैं, दादी, और युरेव के दिन ... 1869 चक्र, लेकिन यह एफटी के लिए बहुत खराब है, हमने इस से शुरू किया, किसी प्रकार का कचरा, क्योंकि पूर्णांक बहुत तेज है।

हम डिब्रीफिंग शुरू करते हैं और यह पता चला है कि केवल चर के प्रकार को बदलना पर्याप्त नहीं है। सबसे पहले, हमें 8 या 16 नहीं, बल्कि 32 बिट्स का उपयोग करना होगा, अन्यथा अतिप्रवाह होगा, और लंबी संख्या, हालांकि पीटी की तुलना में तेज़ है, लेकिन इतना नहीं जितना कि एल्गोरिथ्म में खामियों की भरपाई करने के लिए है। दूसरा, ये दोष हैं। हमारे पास फिर से प्रत्येक उपाय पर गणना की गई थी - हम उन्हें प्रारंभिक गणना B2 = B1 * I, A2 = A * I I I से हटाते हैं। तब हमें मिलता है

$$

$$(7) पी = ((और * ए 1 + बी 2) * और + ए 2) / और / और$$

(=> 2 * 2 + 2 /) 1684 के परिणाम के साथ पिछले एक से बेहतर है, लेकिन फिर भी हम इससे दूर नहीं हुए।

हम एक और स्थिर और 2 की गणना को बाहर करते हैं = और * और हम प्राप्त करते हैं

$$

$$(8) पी = ((और * ए 1 + बी 2) * और + ए 2) / II$$

(=> 2 * 2 + 1 /), 956 चक्रों के निष्पादन समय के साथ - लेकिन यह दिलचस्प है, एक ऑपरेशन के बहिष्कार से उत्पादकता में उल्लेखनीय वृद्धि हुई।

यही हमें धीमा कर देता है - विभाजन, क्योंकि यह बहुत समय लेने वाला ऑपरेशन है, लेकिन इससे निपटने के लिए हमारे पास एक दिलचस्प चाल है। अभिव्यक्ति की गणना करने के लिए 1 / और हम प्राथमिक परिवर्तनों 1 / = 1 / * ( / ) = 1 * ( / ) / . यदि हम एच के रूप में दो की डिग्री चुनते हैं, तो एच द्वारा विभाजन को पाली द्वारा प्रतिस्थापित किया जा सकता है, और यदि घातांक 8 से अधिक है, तो भी पाली की आवश्यकता नहीं होगी। और एन / ए के मूल्य को ईमानदारी से गणना करना होगा, लेकिन केवल एक बार, जिसके बाद गणना चक्र में केवल गुणा रहता है।

इस तथ्य पर ध्यान दें कि हमने काफी सही रूपांतरण नहीं किया है और एन / ए को इसके गोल मूल्य के साथ बदल दिया है, जो पूर्णांक के साथ विशेष रूप से संचालन के लिए जाने के लिए है। हमारे मामले में इस दृष्टिकोण की प्रयोज्यता को साबित करने के लिए सटीकता की हानि में सटीकता शामिल है और अतिरिक्त शोध किया जाना चाहिए। हम H / I को फ़ॉर्म में लिखते हैं (K * I + d) / I = K + (d / I), जहाँ q I से कम है। तब H / I से K में जाने में पूर्ण त्रुटि d / I होगी, और सापेक्ष त्रुटि d / I होगी। I / (K + d / I)> = d / I / (K + 1) ~ d / I / K, बशर्ते कि K >> 1 (यह एक बदलाव नहीं है)। यह निम्नानुसार है कि एच के मूल्य को यथासंभव बड़ा चुना जाना चाहिए, क्योंकि पूर्ण गणना त्रुटि ए * डी / आई / के> = ए * 1 / एन / आई के बराबर है। यदि हम चाहते हैं कि त्रुटि एकता से अधिक न हो, तो हमें A / K <= 1 की स्थिति का सामना करना होगा, फिर K> = A, हम K * I> = A * I, जिसका अर्थ H> = A * I है, को बदल देते हैं, तब हम नहीं करते सटीकता में हार। हमारे मामले में, A <= 256 और I <= 256, हमें H> = 2 ** 16 मिलता है, जो काफी स्वीकार्य है। जाहिर है, उपरोक्त सूत्रों में, मूल संख्याओं के मॉड्यूल का उपयोग किया जाना चाहिए।

हम भविष्य के लिए ध्यान देते हैं कि यदि हम नीचे नहीं, बल्कि निकटतम पूर्णांक की ओर बढ़ते हैं, तो आवश्यकताएं कुछ हद तक कम हो जाती हैं और एच को पर्याप्त आधा होना चाहिए, हालांकि बारीकियां हैं।

किसी भी मामले में, हम आवश्यक सटीकता प्रदान कर सकते हैं और निम्नलिखित एल्गोरिथ्म प्राप्त कर सकते हैं: एच = 2 ** 16; के = [एन / ए] (आई <256); 0 <= और <= AND;

$$

$$(9) P = (((((और * A1 + B2) * और + A2) * K) >> 16) * K> >>$$

(=> 4 * 2 + 2 >> 16) जहां सभी ऑपरेशन लंबे पूर्णांक पर किए जाते हैं। हम इस एल्गोरिथ्म को लागू करते हैं और 583 घड़ी चक्र प्राप्त करते हैं ... लेकिन यह पहले से ही आदर्श के करीब है, लेकिन अभी तक आदर्श नहीं है।

आगे एक विशिष्ट एमके के लिए छोटी सेटिंग्स आती हैं - वैश्विक चर के साथ काम करना तेज है। स्थानीय लोगों की तुलना में, लेकिन रजिस्टर स्थानीय लोगों के साथ तेजी से, जो समय के साथ 506 घड़ी चक्रों में कमी की ओर जाता है।

इसके अलावा, हम ध्यान दें कि शिफ्ट से पहले अंतिम गुणा 16 बिट संख्या के साथ किया जा सकता है, जो 504 देगा - एक ट्रिफ़ल, लेकिन अच्छा।

कुल मिलाकर, हमने 1900/504 में "माथे" कार्यान्वयन की तुलना में गणनाओं को तेज किया - 3 बार से अधिक, और हमने बिल्कुल शब्द नहीं खोए। यह वह परिणाम है जिसे मैं समय अनुकूलन कहता हूं, और मूल पोस्ट में प्राप्त 20% नहीं।

क्या बेहतर संकेतक प्राप्त करना संभव है - यह संभव है, लेकिन यह अगले पोस्ट का विषय है।