त्रुटि और अतिप्रवाह के मार्जिन के साथ समस्या

मैं आपके साथ एक छोटे से एल्गोरिथम कार्य को साझा करना चाहता हूं जो मेरे सहयोगियों ने हाल ही में मुझे लगाया था। यह मुझे लगता है कि समाधान काफी सुरुचिपूर्ण निकला।

समस्या का सार इस प्रकार था। एक निश्चित उपकरण (माइक्रोकंट्रोलर) है जो केवल 32-बिट पूर्णांक मान को संभाल सकता है और यह नहीं जानता कि फ्लोटिंग पॉइंट के साथ कैसे काम किया जाए।
ऐसे उपकरण पर एक टाइमर होता है जो प्रति सेकंड 32768 टिक उत्पन्न करता है। यह एक फ़ंक्शन लिखना आवश्यक है जो टिक्सेस को सटीकता के नुकसान के बिना मिलीसेकंड में परिवर्तित करता है (अधिमानतः गोलाई के साथ)।

नोट: लेख के सभी उदाहरण जावा में बने हैं, लेकिन यह एल्गोरिदम की समझ में हस्तक्षेप नहीं करना चाहिए।

जाहिर है, "हेड-ऑन" समाधान - m = (ticks * 1000) / (2^15) उपयुक्त नहीं है, क्योंकि यह आसानी से अतिप्रवाह कर सकता है।

यूरेका?

कर्मचारियों ने जिस पहले विकल्प के बारे में बात की थी वह मूर्खतापूर्ण रूप से 32 से विभाजित है, लेकिन यहां हमें एक बड़ी त्रुटि मिलती है।
एक अन्य समाधान को गुणा के साथ "स्मार्ट" विभाजन माना जाता था, कई चरणों में चेक की एक श्रृंखला के साथ, प्रत्येक चरण पर 32 बिट्स को ओवरफ्लो नहीं करने की कोशिश की जाती है।

त्वरित रूप से पर्याप्त, परिवर्तनों की निम्नलिखित श्रृंखला मेरे दिमाग में आई (उस 1000 = 1024 - 24 याद करते हुए):
ticks * 1000 * 2^(-15) =
ticks * 2^(-5) - ticks * 24 * 2^(-15) = ticks * 2^(-5) - 3 * ticks * 2^(-12)

हमारे पास कुल:

  private int getMillis(int ticks) { return (ticks >> 5) - 3*(ticks >> 12); } 

सुपर! बहुत बुरा यह काम नहीं करता है।

पहला दृष्टिकोण

मैंने सोचा, एक बार फिर से जाँच की गई - तर्क में कोई स्पष्ट त्रुटियाँ नहीं हैं। मैंने कई परीक्षण उदाहरणों पर जाँच की - ऐसा एल्गोरिथ्म मानता है, लेकिन हमेशा सही ढंग से नहीं। कुछ मामलों में, + -3 द्वारा सही परिणाम से विचलन होते हैं। जाहिर है, गणित में कोई समस्या नहीं है (अन्यथा उत्तर सत्य के समान नहीं होते), लेकिन एक त्रुटि है।

यह समझने के लिए कि समस्या क्या है, यह याद रखने योग्य है कि बिट शिफ्ट कैसे काम करता है। N से दाईं ओर एक बिट शिफ्ट का संचालन n की शक्ति से 2 से विभाजित करने के लिए मेल खाता है। यह एक पूर्णांक ऑपरेशन है, इसलिए बिट्स जो कि शून्य बिट के "दाईं ओर" हैं, को बस छोड़ दिया जाता है।

यदि आप प्रस्तावित एल्गोरिदम को करीब से देखते हैं, तो हमारे पास 2 शिफ्ट ऑपरेशन हैं, परिणामों में से एक का गुणन और अंतर। योजनाबद्ध रूप से, यह ऑपरेशन नीचे दिखाया गया है।

जाहिर है, त्रुटि उन बिट्स में ठीक से जमा हो सकती है जो शून्य बिट के दाईं ओर हैं।

प्रारंभ में, मुझे पिछले खारिज (माइनस-फर्स्ट) बिट का संदेह था, शायद यह वह था जो गुणा और अंतर के संचालन में गायब था। परिणामस्वरूप, फ़ंक्शन कोड कुछ अधिक जटिल हो गया है:

  private int getMillis(int ticks) { int err = ((ticks & 16) >> 4) - 3 * ((ticks & 2048) >> 11); if (err < 0) { return (ticks >> 5) - 3 * (ticks >> 12) - (Math.abs(err) >> 1); } else { return (ticks >> 5) - 3 * (ticks >> 12) + (err >> 1); } } 

गलत चर में हमने उस बिट को डाल दिया है जिसे शिफ्ट ऑपरेशन के दौरान छोड़ दिया गया था, और फॉर्म x - 3 * y एक ही ऑपरेशन उस पर अलग x - 3 * y किया जाता है। ऐसा करने के लिए, 4 वें और 11 वें बिट्स आवंटित किए जाते हैं, शून्य स्थिति में स्थानांतरित कर दिया जाता है, ऑपरेशन की गणना की जाती है, और परिणाम फिर से 1 बिट द्वारा दाईं ओर स्थानांतरित कर दिया जाता है।
नतीजतन, पारी के बाद जो कुछ भी रहता है वह खोए हुए बिट्स होते हैं, जिसका उपयोग हम परिणाम को समायोजित करने के लिए करते हैं।
परिणाम में सुधार हुआ है: अब पूर्ण त्रुटि 2 से अधिक नहीं थी।

निर्णय

अब यह स्पष्ट हो गया कि विचार की दिशा सही थी, लेकिन दशमलव बिंदु के दाईं ओर न केवल एक बिट को भाग लेना चाहिए, बल्कि सभी 5 इंटरसेक्टिंग वाले (जो कि उपरोक्त आरेख में -1 से -5 तक के पदों में दिखाई देते हैं)।

नतीजतन, मुझे फ़ंक्शन का अंतिम संस्करण मिला, जिसकी त्रुटि 0.5 से कम थी।
सामान्य विचार पिछले उदाहरण के समान था, लेकिन प्रत्येक ऑपरेंड से 1 बिट नहीं, लेकिन 5 प्रत्येक को त्रुटि स्रोत के रूप में आवंटित किया गया था।

इसके अलावा, गोलाई को लागू किया जाता है, जो इस विचार पर आधारित है कि i- th बिट i + 1- वें बिट के आधे के बराबर है।

बाकी सब कुछ कोड से स्पष्ट होना चाहिए :)

  private int getMillis(int ticks) { int l = (ticks & 0x1F) << 7; int r = ticks & 0xFFF; // 2^12 - 1 int err = l - 3 * r; int fraction = (Math.abs(err) & 0xFFF); int fractionRound = fraction >> 11; //== 1 <=> there is 0.5xxx fraction = fraction & 0x7FF; // 0.5xxx => 0.0xxx if (err < 0) { fraction = fraction > 0 ? 1 : 0; return (ticks >> 5) - 3 * (ticks >> 12) - (Math.abs(err) >> 12) - (fractionRound & fraction); } else { return (ticks >> 5) - 3 * (ticks >> 12) + (err >> 12) + fractionRound; } } 

अच्छे प्रोग्रामर बनें और एक अच्छा सप्ताहांत रखें!