मनोरंजक जावास्क्रिप्ट: लगभग एक रेखीय समीकरण

क्या होगा अगर हम अद्भुत गणित (अर्थात् रेखीय समीकरण) और हमारे समान रूप से अद्भुत जावास्क्रिप्ट लेते हैं, और फिर एक दूसरे पर सुपरइम्पोज करते हैं? Js- पर्यावरण की सीमाओं और बारीकियों की स्थितियों में, एक साधारण गणितीय समस्या बहुत ही जिज्ञासु और js- पत्थरों के नुकसान से भरी हो सकती है। मॉस्को में आखिरी होलीजस 19 सम्मेलन में, इस तरह के एक रैखिक समीकरण ( SEMrush से अन्य कार्यों के बीच) ने काफी हलचल मचाई ।



और हाँ, यह फिर से मनोरंजक जावास्क्रिप्ट का शीर्षक है: मैं आपको उन सभी लोगों को काटने के लिए कहता हूं जो परवाह करते हैं।


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

सूत्रीकरण

1. समीकरण के सभी पूर्णांक समाधान खोजें:

9 +~ x >> 6 / 3 = -x / 3 

2. समीकरण के सभी पूर्णांक समाधान खोजें:

 9 +~ x >> 6 / 3 = -x / 3 | 0 

दूसरा समीकरण दाईं ओर एक अतिरिक्त ऑपरेशन में केवल पहले से अलग है।

गणितीय सन्निकटन

हम पहले समीकरण की ओर मुड़ते हैं। और शुरू करने के लिए, हम तालिका के अनुसार उपयोग किए गए कार्यों की प्राथमिकताओं को समझेंगे:

 (9 +(~ x)) >> (6 / 3) = -x / 3 

हम x से बिट वाइज निगेटिव लेते हैं, फिर इसे 9 में जोड़ते हैं। जोड़ का परिणाम बिटवाइज को दाईं ओर स्थानांतरित किया जाता है, बिट्स की संख्या 6 से 3 से विभाजित करने के परिणाम के बराबर होती है।

जाहिर है, समस्या वांछित एक्स पर बिटवाइज संचालन के उपयोग में है। लेकिन आगे तर्क के लिए कुछ सशर्त जड़ खोजने के लिए, समीकरण को अनुमानित गणितीय एनालॉग लाने की कोशिश करना लायक है।

बिटवाइज ऑपरेशंस 32-बिट पूर्णांक के रूप में ऑपरेंड के साथ काम करते हैं। बिटवाइज़ को इंक्रीमेंट से पूर्णांक नकार के साथ नहीं बदला जा सकता है:

 (9 -(x + 1)) >> (6 / 3) = -x / 3 (8 - x) >> 2 = -x / 3 

दाईं ओर स्थित बिटवाइज़ शिफ्ट (संकेत को संरक्षित करते समय) पूर्णांक डिवीजन द्वारा दाईं ओर स्थित ऑपरेंड के बराबर दो डिग्री से बदला जा सकता है:

 (8 - x) / 2^2 = -x / 3 (8 - x) / 4 = -x / 3 

बेशक, ये प्रतिस्थापन बहुत मनमानी हैं, और हम इस बारे में बाद में बात करेंगे। और अब हमारे पास सामान्य रैखिक समीकरण है, जिसकी एकमात्र जड़ -24 है। मूल समीकरण के बाएँ और दाएँ पक्ष में मान को प्रतिस्थापित करें:

 9 +~ (-24) >> 6 / 3; // = 8 -(-24) / 3; // = 8 

दोनों भाग समान हैं, जिसका अर्थ है कि सब कुछ इतना निराशाजनक नहीं है और -24 वास्तव में एक समाधान है।

आलसी को खोजो

यदि हम f1 (x) = (8 -x) / 4 और f2 (x) = -x / 3 के फ़ंक्शंस के ग्राफ़ खींचते हैं, तो निश्चित रूप से हमें x = -24 पर दो लाइनों का एकमात्र चौराहा बिंदु मिल जाता है।



लेकिन हमने बाएं अभिव्यक्ति में बिटवाइज़ ऑपरेशंस के साथ कुछ असमान प्रतिस्थापन किए, इसलिए वास्तव में फ़ंक्शन एफ 1 का ग्राफ थोड़ा अलग होगा। किसी भी x के लिए, फ़ंक्शन का मान -1 से 1. रेंज में संभावित बदलाव के साथ निरंतर लाइन f1 पर मूल्य से अलग एक पूर्णांक होगा। इसका मतलब है कि हम समाधान खोज क्षेत्र को बाएं और दाएं -24 तक सीमित कर सकते हैं, जहां फ़ंक्शन एफ 1 और एफ 2 के मान हैं एक से अधिक के द्वारा अंतर करना शुरू करें।

खोज क्षेत्र की सीमाओं को खोजने के लिए, आप 1) मॉड्यूल के साथ असमानता को हल कर सकते हैं, या 2) कार्यों के ग्राफ़ पर करीब से नज़र डाल सकते हैं। हम पाएंगे कि x खंड [-36, -12] को देखने लायक है:

 | (8 - x) / 4 + x / 3 | <= 1 

कुछ बंद रेंज में संपूर्ण समाधानों पर पुनरावृत्ति करने के लिए [भीख मांगें ], हम खोज कार्य लिखते हैं:

 const findx = (f, beg, end) => [...Array(end - beg + 1)].map((_, i) => i + beg).filter(f); 

फ़ंक्शन पूर्णांक का एक सरणी देता है जिसके लिए पारित फ़ंक्शन f का मान कम हो जाता है । समाधान खोजने के लिए, हम समीकरण ऑपरेटर का उपयोग करके एक जेएस-फ़ंक्शन के रूप में समीकरण का प्रतिनिधित्व करते हैं:

 let eq1 = x => 9 +~ x >> 6 / 3 == -x / 3; findx(eq1, -36, -12); // [-24, -21, -18, -15] 

इस प्रकार, x = [-24, -21, -18, -15] पहले समीकरण के वांछित समाधान हैं।

चित्रमय समाधान

गणना एक सफलता है, लेकिन चलो अभी भी फ़ंक्शन f1 के ग्राफ को अंत तक समझें और समीकरण को रेखांकन से हल करें। इसके अलावा, समाधान ब्राउज़र कंसोल के अनिवार्य स्वामित्व का मतलब नहीं है।

बिटवाइज़ NOT ऑपरेटर केवल भिन्नात्मक भाग को हटाता है, जिससे परिणाम - (x + 1) गोल हो जाएगा। बिट शिफ्ट ऑपरेटर थोड़ा अधिक जटिल है। हमने इसे पूर्णांक विभाजन के साथ बदल दिया, लेकिन लाभांश संख्या के संकेत के आधार पर, यह ऑपरेशन परिणाम को नीचे या ऊपर करता है:

 10 >> 2; // = 2 -10 >> 2; // = -3 

हालाँकि, हम जानते हैं कि वांछित x [-36, -12] श्रेणी में है। तदनुसार, बिटवाइड शिफ्ट ( 8 -x ) के बाएं ऑपरेंड की सीमा [20, 44] में है, अर्थात यह हमेशा सकारात्मक है। जिसका अर्थ है पूर्णांक विभाजन का अर्थ है नीचे की ओर गोल होना।

परिचालन की प्रकृति का पता लगाने के बाद, हम f1 के सही ग्राफ को खींच सकते हैं:



हम समान निर्देशांक x = [-24, -21, -18, -15] में कार्यों के चार चौराहे बिंदु पाएंगे।

दूसरा समीकरण

तो, हम दूसरे समीकरण के लिए मिला:

 9 +~ x >> 6 / 3 = -x / 3 | 0 

यह पहले से एक बिटवाइज़ या इसके अलावा से भिन्न होता है। यदि इस तरह के ऑपरेशन का सही संचालन शून्य है, तो परिणाम केवल आंशिक रूप से छोड़े गए भाग के साथ बाएं ऑपरेंड का मूल्य है।

आरंभ करने के लिए, उसी खोज से गुज़रें, बस खोज क्षेत्र पर निर्णय लें। चूंकि अब फ़ंक्शन f2 में एफ 1 के साथ एक समान चरित्र है, विश्वसनीयता के लिए, संभव पारी को संक्षेप में प्रस्तुत किया जाना चाहिए और खोज को सीमित किया जाना चाहिए जहां फ़ंक्शन दो से अधिक इकाइयों द्वारा निरपेक्ष मूल्य में भिन्न होते हैं - यह [-48, 0] है।

 let eq2 = x => 9 +~ x >> 6 / 3 == -x / 3 | 0; findx(eq2, -48, 0); // [-24, -21, -18, -15] 

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

 x => (9 +~ x >> 6 / 3 == -x / 3) | 0; 

इस मामले में, बिटवाइस या का कोई प्रभाव नहीं है, क्योंकि यह सच है | 0 = 1 । इससे बचने के लिए, फ़ंक्शन बॉडी में स्पष्ट रूप से इंगित करना आवश्यक है कि हम दो सबएक्सप्रेस के परिणामों की तुलना कर रहे हैं:

 let eq2 = x => (9 +~ x >> 6 / 3) == (-x / 3 | 0); findx(eq2, -48, 0); // [-32, -29, -28, -26, -25, -24, -23, -22, -21, -19, -18, -15] 

समाधानों की संख्या में वृद्धि हुई है। अब आइए फ़ंक्शन ग्राफ़ पर ध्यान दें। F1 के साथ सादृश्य द्वारा, एक "स्टेप लैडर" एक संशोधित फ़ंक्शन f2 का निर्माण करता है:



फ़ंक्शन ग्राफ़ के स्थान एक-दूसरे को ओवरलैप करते हैं, लेकिन हम केवल x समन्वय के पूर्णांक मान के साथ अंकों में रुचि रखते हैं: [-32, -29, -28, -26, -25, -24, -23, -22, -21 और -19 में -18, -15], केवल 12 समाधान। यदि आप चाहें तो चरण 3 और 4 के साथ दो "सीढ़ी" के चौराहे को एल्गोरिथम पाया जा सकता है।

अतिरिक्त प्रश्न

सम्मेलन में प्रस्तावित समस्या में एक अतिरिक्त सवाल था: समीकरण के लिए न्यूनतम समाधान खोजना आवश्यक था 2. यह नहीं कहा गया था कि यह जरूरी एक पूर्णांक था, इसलिए उत्तर x = -32 - गलत निकला।

जानवर बल द्वारा एक समाधान खोजने से यहां काम नहीं होगा, लेकिन इसे ग्राफिक रूप से हल करना बहुत सरल है। यह दाईं ओर निकटतम x- -33 मान है:



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

बिटवाइज़ ऑपरेशन्स का डार्क साइड

जैसा कि ऊपर उल्लेख किया गया है, बिटवाइज़ ऑपरेशंस ऑपरेशंस को 0 और 1 के प्रतिनिधित्व वाले 32-बिट संख्याओं में परिवर्तित करते हैं - यह रेंज है [-2147483648, 2147483647]। यदि संख्या इसमें फिट नहीं होती है, तो सबसे महत्वपूर्ण बिट्स को छोड़ दिया जाएगा।

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

उदाहरण के लिए, संख्या -24 को इस प्रकार दर्शाया जाएगा:

 11111111111111111111111111101000 

संख्या का एक नकारात्मक मान एक के जोड़ के साथ एक सकारात्मक संख्या के रिकॉर्ड में इनवर्टिंग (बिटवाइज़ नहीं) बिट्स द्वारा प्राप्त किया जाता है।

इस 32-बिट अनुक्रम में रूपांतरण समाप्त होने के बाद सीमा के बाहर की कोई भी संख्या, बाइनरी संचालन में संख्या -24 के समान होगी। उदाहरण के लिए, ये संख्याएँ हैं:

 4294967272 | 0; // -24 8589934568 | 0; // -24, prepend '1' 12884901864 | 0; // -24, prepend '10' 17179869160 | 0; // -24, prepend '11' 21474836456 | 0; // -24, prepend '100' // ... 

समीकरण के दाईं ओर, बिटवाइज़ ऑपरेशन से पहले, हम x को 3 से विभाजित करते हैं। हम x को "समतुल्य" -24 के बीच में खोजते हैं, जो 3. से विभाज्य है। निकटतम संख्या 12884901864 है। इसे समीकरण में प्रतिस्थापित करें:

 9 +~ 12884901864 >> 6 / 3 = -12884901864 / 3 | 0 9 +~ 12884901864 >> 2 = -4294967288 | 0 9 + 23 >> 2 = 8 8 = 8 

3 (-4294967288) द्वारा विभाजित होने का परिणाम आवंटित 32 अंकों में फिट नहीं होता है; बिट्स inverting के दौरान, साइन अंत में खो जाता है और केवल 8 रहता है:

 00000000000000000000000000001000 

इसके अतिरिक्त, आप eq2 फ़ंक्शन को कॉल करके परिणाम की शुद्धता को सत्यापित कर सकते हैं:

 eq2(12884901864); // true 

यदि आप इसके बारे में सोचते हैं, तो इस रूट के बगल में आप शेष 11 पूर्णांक समाधानों के अनुमानों को पा सकते हैं।

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

और आप नहीं बना सकते हैं! फिर, सबसे छोटी जड़ को खोजने के लिए, आपको एक नकारात्मक चिन्ह के साथ Number.MAX_SAFE_INTEGER के पड़ोस पर ध्यान देना चाहिए, क्योंकि यह संख्या पूर्णांक है और अत्यधिक सटीक फ्लोट64 के साथ है। खैर, फिर अपने दम पर।

निष्कर्ष

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

मुझे वास्तव में आशा है कि आपको सम्मेलन प्रारूप के लिए मनोरंजन के रूप में इस तरह के एक असामान्य कार्य का विचार पसंद आया। पिछले एक साल में, मैंने कई ऐसे "मनोरंजक" जावास्क्रिप्ट कार्यों को संचित किया है। मैंने उन सभी को एक जगह इकट्ठा करने का फैसला किया। यदि आपको डर नहीं है, तो लिंक का अनुसरण करें: अप्रत्याशित चुनौती देने वाला जावास्क्रिप्ट । लुक कॉम्प्लेक्स और टूटे पाइप के कार्य , जो सम्मेलन में प्रस्तावित किए गए थे, पहले ही निर्धारित किए जा चुके हैं। हां, ऐसे कई संग्रह हैं, लेकिन यह एक मेरा है! सभी को फिर से धन्यवाद।