वृत्ताकार परिवर्तन: Difference between revisions
No edit summary |
No edit summary |
||
| Line 32: | Line 32: | ||
</ref> | </ref> | ||
<syntaxhighlight lang=" | <syntaxhighlight lang="c"> | ||
/* | /* | ||
* Shift operations in C are only defined for shift values which are | * Shift operations in C are only defined for shift values which are | ||
| Line 47: | Line 47: | ||
count &= mask; | count &= mask; | ||
return (value << count) | (value >> (-count & mask)); | return (value << count) | (value >> (-count & mask)); | ||
} | } | ||
uint32_t rotr32 (uint32_t value, unsigned int count) { | uint32_t rotr32 (uint32_t value, unsigned int count) { | ||
| Line 145: | Line 145: | ||
*[[परिसंचारी|परिचालित]] | *[[परिसंचारी|परिचालित]] | ||
*[[लिंडन शब्द]] | *[[लिंडन शब्द]] | ||
*नेकलेस (कॉम्बिनेटरिक्स) - टपल जैसी वस्तु | *नेकलेस (कॉम्बिनेटरिक्स) - टपल जैसी वस्तु किन्तु जिसके लिए गोलाकार परिवर्तन को समकक्ष माना जाता है। | ||
==संदर्भ == | ==संदर्भ == | ||
Revision as of 13:55, 19 July 2023
साहचर्य गणित में, वृत्ताकार परिवर्तन टुपल में प्रविष्टियों को पुनर्व्यवस्थित करने का ऑपरेशन है, या तो अंतिम प्रविष्टि को पहले समिष्ट पर ले जाकर, जबकि अन्य सभी प्रविष्टियों को अगले समिष्ट पर स्थानांतरित करके, या प्रतिलोम ऑपरेशन करके प्राप्त करते है। वृत्ताकार परिवर्तन विशेष प्रकार का चक्रीय क्रमपरिवर्तन है, जो बदले में विशेष प्रकार का क्रमपरिवर्तन है। औपचारिक रूप से, गोलाकार परिवर्तन टुपल में n प्रविष्टियों का क्रमपरिवर्तन है जैसे कि या तो
- मॉड्यूलर अंकगणित n, सभी प्रविष्टियों के लिए i = 1, ..., n
या
- मॉड्यूलर अंकगणित n, सभी प्रविष्टियों के लिए i = 1, ..., n।
किसी दिए गए टुपल में बार-बार वृत्ताकार परिवर्तन प्रयुक्त करने के परिणाम को ट्यूपल का 'वृत्ताकार परिवर्तन' भी कहा जाता है।
उदाहरण के लिए, चार-टुपल (a, b, c, d) में बार-बार गोलाकार परिवर्तन लगाने से क्रमिक रूप से लाभ मिलता है
- (d, a, b, c),
- (c, d, a, b),
- (b, c, d, a),
- (a, b, c, d) (मूल चार-ट्यूपल),
और फिर क्रम दोहराता है; इसलिए इस चार-टुपल में चार अलग-अलग गोलाकार परिवर्तन हैं। चूँकि, सभी n-टुपल्स में n विशिष्ट वृत्ताकार परिवर्तन नहीं होते हैं। उदाहरण के लिए, 4-ट्यूपल (a, b, a, b) में केवल 2 अलग-अलग गोलाकार परिवर्तन हैं। n-ट्यूपल की अलग-अलग गोलाकार परिवर्तन की संख्या है , जहां k का भाजक है n, सभी उप-पैटर्न पर दोहराव की अधिकतम संख्या को दर्शाता है।
कंप्यूटर प्रोग्रामिंग में, बिटवाइज़ रोटेशन, जिसे वृत्ताकार परिवर्तन के रूप में भी जाना जाता है, बिटवाइज़ ऑपरेशन है जो इसके ऑपरेंड के सभी बिट्स को परिवर्तन करता है। इस प्रकार अंकगणितीय परिवर्तन के विपरीत, गोलाकार परिवर्तन किसी संख्या के साइन बिट को संरक्षित नहीं करता है या फ़्लोटिंग-पॉइंट नंबर के घातांक को उसके महत्व से अलग नहीं करता है। तार्किक परिवर्तन के विपरीत, रिक्त बिट स्थिति शून्य से नहीं भरी जाती है, किन्तु अनुक्रम से बाहर स्थानांतरित बिट्स से भरी जाती है।
वृत्ताकार परिवर्तन प्रयुक्त करना
बिट अनुक्रमों को व्यवस्थित करने के लिए क्रिप्टोग्राफी में अधिकांशतः वृत्ताकार परिवर्तन का उपयोग किया जाता है। सामान्यतः, सी (प्रोग्रामिंग भाषा) सहित कई प्रोग्रामिंग भाषाओं में वृत्ताकार शिफ्टिंग के लिए ऑपरेटर या मानक फ़ंक्शन नहीं हैं, तथापि लगभग सभी प्रोसेसर के पास इसके लिए बिटवाइज़ ऑपरेशन निर्देश हैं (उदाहरण के लिए इंटेल x86 में आरओएल और आरओआर हैं)। चूँकि, कुछ कंपाइलर आंतरिक कार्य के माध्यम से प्रोसेसर निर्देशों तक पहुंच प्रदान कर सकते हैं। इसके अतिरिक्त, मानक एएनएसआई सी कोड में कुछ निर्माणों को कंपाइलर द्वारा सीपीयू पर रोटेट असेंबली भाषा निर्देश के लिए अनुकूलित किया जा सकता है जिसमें ऐसा निर्देश होता है। अधिकांश सी कंपाइलर निम्नलिखित मुहावरे को पहचानते हैं, और इसे एकल 32-बिट रोटेट निर्देश में संकलित करते हैं।[1][2]
/*
* Shift operations in C are only defined for shift values which are
* not negative and smaller than sizeof(value) * CHAR_BIT.
* The mask, used with bitwise-and (&), prevents undefined behaviour
* when the shift count is 0 or >= the width of unsigned int.
*/
#include <stdint.h> // for uint32_t, to get 32-bit-wide rotates, regardless of the size of int.
#include <limits.h> // for CHAR_BIT
uint32_t rotl32 (uint32_t value, unsigned int count) {
const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
count &= mask;
return (value << count) | (value >> (-count & mask));
}
uint32_t rotr32 (uint32_t value, unsigned int count) {
const unsigned int mask = CHAR_BIT * sizeof(value) - 1;
count &= mask;
return (value >> count) | (value << (-count & mask));
}
यह सुरक्षित और संकलक-अनुकूल कार्यान्वयन जॉन रेगेहर द्वारा विकसित किया गया था,[3] और इसे पीटर कॉर्डेस द्वारा और अधिक परिष्कृत किया गया था।[4][5] एक सरल संस्करण अधिकांशतः देखा जाता है जब count 1 से 31 बिट्स की सीमा तक सीमित है:
uint32_t rotl32 (uint32_t value, unsigned int count) {
return value << count | value >> (32 - count);
}
यह संस्करण खतरनाक है क्योंकि यदि count 0 या 32 है, तो यह 32-बिट परिवर्तन के लिए पूछता है, जो सी भाषा मानक में अपरिभाषित व्यवहार है। चूँकि, यह वैसे भी कार्य करता है, क्योंकि अधिकांश माइक्रोप्रोसेसर इसे प्रयुक्त करते हैं value >> 32 या तो 32-बिट परिवर्तन (0 का उत्पादन) या 0-बिट परिवर्तन (मूल का उत्पादन) के रूप में value), और इनमें से कोई भी इस एप्लिकेशन में सही परिणाम देता है।
उदाहरण
यदि बिट अनुक्रम 0001 0111 को बिट स्थिति के गोलाकार परिवर्तन के अधीन किया गया था... (नीचे चित्र देखें)
|
|
यदि बिट अनुक्रम 1001 0110 को निम्नलिखित परिचालनों के अधीन किया गया था:
| बायीं ओर वृत्ताकार 1 स्थिति से परिवर्तन: | 0010 1101 |
| बाएं वृत्ताकार में 2 समिष्ट का परिवर्तन: | 0101 1010 |
| बाएं वृत्ताकार में 3 समिष्ट का परिवर्तन: | 1011 0100 |
| बाएं वृत्ताकार में 4 समिष्ट का परिवर्तन: | 0110 1001 |
| बाएं वृत्ताकार में 5 समिष्ट का परिवर्तन: | 1101 0010 |
| बाएं वृत्ताकार में 6 समिष्ट का परिवर्तन: | 1010 0101 |
| बाएं वृत्ताकार में 7 समिष्ट का परिवर्तन: | 0100 1011 |
| बाएं वृत्ताकार में 8 समिष्ट का परिवर्तन: | 1001 0110 |
| दांयी ओर वृत्ताकार 1 स्थिति से परिवर्तन: | 0100 1011 |
| दांयी वृत्ताकार में 2 समिष्ट का परिवर्तन: | 1010 0101 |
| दांयी वृत्ताकार में 3 समिष्ट का परिवर्तन: | 1101 0010 |
| दांयी वृत्ताकार में 4 समिष्ट का परिवर्तन: | 0110 1001 |
| दांयी वृत्ताकार में 5 समिष्ट का परिवर्तन: | 1011 0100 |
| दांयी वृत्ताकार में 6 समिष्ट का परिवर्तन: | 0101 1010 |
| दांयी वृत्ताकार में 7 समिष्ट का परिवर्तन: | 0010 1101 |
| दांयी वृत्ताकार में 8 समिष्ट का परिवर्तन: | 1001 0110 |
अनुप्रयोग
चक्रीय कोड प्रकार का ब्लॉक कोड होता है, जिसमें यह गुण होता है कि कोडवर्ड का गोलाकार परिवर्तन सदैव और कोडवर्ड उत्पन्न करता है। यह निम्नलिखित सामान्य परिभाषा को प्रेरित करता है: इस प्रकार वर्णमाला Σ पर स्ट्रिंग (कंप्यूटर विज्ञान) के लिए, परिवर्तन (o) को एस के परिपत्र परिवर्तन के फलन (गणित) को निरूपित करें, और स्ट्रिंग्स के फलन L के लिए, परिवर्तन (L) को L में स्ट्रिंग्स के सभी गोलाकार शिफ्टों के फलन को निरूपित करें। यदि L चक्रीय कोड है, तो परिवर्तन (L) ⊆ L; L के चक्रीय भाषा होने के लिए यह आवश्यक नियम है। इस प्रकार औपचारिक भाषा सिद्धांत में ऑपरेशन परिवर्तन (L) का अध्ययन किया गया है। उदाहरण के लिए, यदि L संदर्भ-फ्री भाषा है, तो परिवर्तन(L) फिर से संदर्भ-फ्री है।[6][7] इसके अलावा, यदि L को लंबाई n की नियमित अभिव्यक्ति द्वारा वर्णित किया गया है, तो शिफ्ट (L) का वर्णन करने वाली लंबाई O(n3) की एक नियमित अभिव्यक्ति है।[8]
यह भी देखें
- बैरल शिफ्टर
- परिचालित
- लिंडन शब्द
- नेकलेस (कॉम्बिनेटरिक्स) - टपल जैसी वस्तु किन्तु जिसके लिए गोलाकार परिवर्तन को समकक्ष माना जाता है।
संदर्भ
- ↑ GCC: "Optimize common rotate constructs"
- ↑ "Cleanups in ROTL/ROTR DAG combiner code" mentions that this code supports the "rotate" instruction in the CellSPU
- ↑ Safe, Efficient, and Portable Rotate in C/C++
- ↑ Stackoverflow: Best practices for rotates in C/C++
- ↑ Near constant time rotate that does not violate the standards
- ↑ T. Oshiba, "Closure property of the family of context-free languages under the cyclic shift operation", Transactions of IECE, 55D:119–122, 1972.
- ↑ A. N. Maslov, "Cyclic shift operation for languages", Problems of Information Transmission 9:333–338, 1973.
- ↑ Gruber, Hermann; Holzer, Markus (2009). "बहुपद आकार की नियमित अभिव्यक्तियों के साथ भाषा संचालन" (PDF). Theoretical Computer Science. 410 (35): 3281–3289. doi:10.1016/j.tcs.2009.04.009. Zbl 1176.68105. Archived from the original (PDF) on 2017-08-29. Retrieved 2012-09-06..
