तालिकाओं का उपयोग करके तेजी से पूर्णांक गुणन

मैं पाठकों को एक प्रोग्रामिंग ट्रिक के बारे में बताना चाहता हूं जो मुझे किसी प्रकार की अनुवाद पुस्तक में मिली थी जिसमें उन दूरियों में ऐसे ट्रिक्स का चयन किया गया था जब इसे अभी तक न केवल बाइट का आविष्कार किया गया था, लेकिन इसे स्टैक कहने के लिए डरावना है, और महान दिक्जस्त्र ने अभी तक ऑपरेटर को शाप नहीं दिया है GOTO (sic, अपरकेस में)।

मुझे इसकी सरलता और कृपा से यह ट्रिक इतनी पसंद आई कि पहले से ही इस सहस्राब्दी में मैं छात्रों को निम्नलिखित कार्य के रूप में इसके बारे में बताने में प्रसन्न था।

कल्पना कीजिए कि 2030 में चंद्रमा से लौटने की प्रक्रिया में, आपको अचानक पता चला कि आपका ऑन-बोर्ड कंप्यूटर सही ढंग से पूर्णांक गुणन क्रिया नहीं कर रहा है, और यह निश्चित रूप से लैंडिंग के दौरान एक दुर्घटना का कारण होगा।

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

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

अंकगणित के स्कूल पाठ्यक्रम से, हम याद करते हैं कि बहुस्तरीय संख्याओं को एक कॉलम से गुणा किया जा सकता है, और व्यक्तिगत संख्याओं के गुणन का परिणाम गुणन तालिका से लिया जा सकता है।

लेकिन केवल अगर संख्याओं को कम चुना जाता है (उदाहरण के लिए, 0 और 1), गुणन तालिका कम और कॉलम लंबा होगा, और उनकी गणना में बहुत समय लगेगा।

यदि, इसके विपरीत, हम लंबी संख्या लेते हैं (उदाहरण के लिए, 0 से 65535 तक), तो 16-बिट अंकगणितीय के लिए
परिणाम सीधे तालिका से लिया गया है, और कॉलम गायब हैं। हालांकि, शास्त्रीय पाइथागोरस तालिका का आकार लगभग 17GB (4 * 65536 * 65536) है, अगर हम विकर्ण के संबंध में समरूपता को ध्यान में रखते हैं, तो आधा लगभग 8.5GB है।

यह बहुत अधिक हो सकता है।

बीजगणित को याद रखें।

$$$(a + b) ^ 2 = a ^ 2 + b ^ 2 + 2ab$(1)

$$$(a - b) ^ 2 = a ^ 2 + b ^ 2 - 2ab$(2)

(1) से घटाएँ ( 1)

$$$(a + b) ^ 2 - (a - b) ^ 2 = 4ab$

और आगे

$$$a b = ((a + b) ^ 2 - (a - b) ^ 2) / 4$

इस प्रकार, वर्ग सरणी में वर्गों की एक तालिका होने, हम प्राप्त करते हैं

a * b = (sqr [a + b] - sqr [a - b]) / 4 (*)

8 * टेबल (65535 + 65535) का आकार लगभग 8.4MB है, जो पहले से ही स्वीकार्य हो सकता है।

8 बाइट्स की तालिका तत्व का आकार इस तथ्य के कारण है कि अधिकतम ए और बी में, उनके 4 बाइट्स के योग का वर्ग फिट नहीं होता है - 2 बिट पर्याप्त नहीं हैं।

आगे, मैं कुछ सुधार का वर्णन करूँगा, जो पुस्तक में नहीं था। मैं खुद इसके साथ आया था जब मैं पहले से ही यह नोट लिख रहा था।

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

अंत में हमारे पास है

a * b = sqr4 [a + b] - sqr4 [a - b] (**)

जहां sqr4 वर्गों की संशोधित तालिका है।

हमारे उदाहरण में, इसका आकार लगभग 4.2 एमबी है।

इस दृष्टिकोण को समझने के लिए, लुआ कार्यक्रम का पाठ शामिल है।

function create_multiplier(N) -- N     local sqr4 = {} --   for i = 1, 2 * N - 1 do local temp = 0 for j = 1, i - 1 do --    temp = temp + i - 1 --    end -- ..  "" sqr4[i] = math.floor(temp / 4) --  2  end return --   () function (i, j) if i < j then i, j = j, i end return sqr4[1 + i + j] - sqr4[1 + i - j] end end N = 256 mpy = create_multiplier(N) for i = 0, N - 1 do for j = 0, N - 1 do if i * j ~= mpy(i,j) then print("", i, j, i * j, mpy(i,j)) end end end print(" .") 

आधुनिक प्रोसेसरों के लिए, एक डिजिट आकार होना उचित है, जो कि उन तक आसानी से पहुंचने के लिए कई बाइट आकार का है। 1-बाइट अंकों के साथ, तालिका का आकार केवल 1022 बाइट्स है, जो इस चाल को 8-बिट प्रोसेसर में उपयोग करने की अनुमति दे सकता है जिसमें हार्डवेयर गुणन नहीं है।

मैं इस नोट के सभी पाठकों के लिए सुधारों और टिप्पणियों के लिए आभारी रहूंगा।