View source for मर्सेन ट्विस्टर

{{Short description|Pseudorandom number generator}}
'''मर्सेन ट्विस्टर''' एक साधारण-उद्देश्य [[छद्म यादृच्छिक संख्या जनरेटर|प्रतीतिसंद्ध संख्या उत्पन्नक]] (पीआरएनजी) है जिसे 1997 में मकोतो {{nihongo|{{Interlanguage link multi|मकोतो मत्सुमोटो (mathematician)|lt=मकोतो मत्सुमोटो|ja|3=松本眞 (数学者)}}|松本 眞}} और {{nihongo|[[ताकुजी निशिमुरा]]|西村 拓士}} द्वारा विकसित किया गया था।<ref>{{Cite journal|last1=Matsumoto|first1=M.|last2=Nishimura|first2=T.|year=1998|title=Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator|url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/mt.pdf|journal=ACM Transactions on Modeling and Computer Simulation|volume=8|issue=1|pages=3–30|citeseerx=10.1.1.215.1141|doi=10.1145/272991.272995|s2cid=3332028}}</ref><ref>E.g. Marsland S. (2011) ''Machine Learning'' ([[CRC Press]]), §4.1.1. Also see the section "Adoption in software systems".</ref> इसका नाम इस तथ्य से प्राप्त होता है कि इसकी अवधि की लंबाई को [[मेर्सन प्रीमियम|मर्सेन प्रधान संख्या]] के रूप में चुना जाता है।

मेर्सन ट्विस्टर को विशेष रूप से पुराने पीआरएनजी में पाई गई अधिकांश त्रुटियों को दूर करने के लिए प्ररूपित किया गया था।

मेर्सन ट्विस्टर विधिकलन का सबसे अधिक उपयोग किया जाने वाला संस्करण मेर्सन प्राइम <math>2^{19937}-1</math> पर आधारित है। इसका मानक कार्यान्वयन, MT19937, [[32-बिट]] शब्द लंबाई का उपयोग करता है। इसके अतिरिक्त एक और कार्यान्वयन MT19937-64 है<ref>{{cite web|author=John Savard|title=मेर्सन ट्विस्टर|url=http://www.quadibloc.com/crypto/co4814.htm|quote=A subsequent paper, published in the year 2000, gave five additional forms of the Mersenne Twister with period 2^19937-1. All five were designed to be implemented with 64-bit arithmetic instead of 32-bit arithmetic.}}</ref> जो 64-बिट शब्द लंबाई, का उपयोग करता है। यह एक भिन्न अनुक्रम उत्पन्न करता है।

== अनुप्रयोग ==
{{Main article|प्रतीतिसंद्ध संख्या उत्पन्नक}}

=== सॉफ्टवेयर ===
निम्नलिखित सॉफ्टवेयर द्वारा मेर्सन ट्विस्टर का उपयोग डिफ़ॉल्ट पीआरएनजी के रूप में किया जाता है:

* प्रोग्रामिंग भाषाएँ: डायलोग [[एपीएल (प्रोग्रामिंग भाषा)|एपीएल]],<ref>{{cite web|title=यादृच्छिक लिंक|url=http://help.dyalog.com/latest/#Language/System%20Functions/rl.htm|access-date=2020-06-04|work=Dyalog Language Reference Guide}}</ref> [[आईडीएल (प्रोग्रामिंग भाषा)|आईडीएल]],<ref>{{cite web|title=रैंडोमू (आईडीएल संदर्भ)|url=http://www.exelisvis.com/docs/RANDOMU.html|access-date=2013-08-23|work=Exelis VIS Docs Center}}</ref> [[आर (प्रोग्रामिंग भाषा)|आर]],<ref>{{cite web|title=यादृच्छिक संख्या जेनरेटर|url=https://cran.r-project.org/web/views/Distributions.html|access-date=2012-05-29|work=CRAN Task View: Probability Distributions}}</ref> [[रूबी (प्रोग्रामिंग भाषा)|रूबी]],<ref>{{cite web|title="यादृच्छिक" वर्ग दस्तावेज़ीकरण|url=http://www.ruby-doc.org/core-1.9.3/Random.html|access-date=2012-05-29|work=Ruby 1.9.3 documentation}}</ref> [[फ़्री पास्कल]],<ref>{{cite web|title=रैंडम|url=http://www.freepascal.org/docs-html/rtl/system/रैंडम.html|access-date=2013-11-28|work=free pascal documentation}}</ref> [[PHP (प्रोग्रामिंग भाषा)|पीएचपी]],<ref>{{cite web|title=mt_rand — Generate a better random value|url=http://php.net/manual/en/function.mt-rand.php|access-date=2016-03-02|work=PHP Manual}}</ref> [[पायथन (प्रोग्रामिंग भाषा)|पायथन]]  ([[NumPy|नमपाइ]] भी मर्सेन ट्विस्टर का उपयोग करता है, परंतु संस्करण 1.17 से पूर्व इसको डिफ़ॉल्ट यादृच्छिक संख्या उत्पन्नक के रूप में परिवर्तित कर दिया गया था।<ref>{{Cite web|title=NumPy 1.17.0 Release Notes — NumPy v1.21 Manual|url=https://numpy.org/doc/stable/release/1.17.0-notes.html?highlight=random|access-date=2021-06-29|website=numpy.org}}</ref>),<ref>{{cite web|title=9.6 random — Generate pseudo-random numbers|url=https://docs.python.org/release/2.6.8/library/random.html|access-date=2012-05-29|work=Python v2.6.8 documentation}}</ref><ref>{{cite web|title=8.6 random — Generate pseudo-random numbers|url=https://docs.python.org/release/3.2/library/random.html|access-date=2012-05-29|work=Python v3.2 documentation}}</ref><ref>{{cite web|title=random — Generate pseudo-random numbers — Python 3.8.3 documentation|url=https://docs.python.org/3/library/random.html|access-date=2020-06-23|work=Python 3.8.3 documentation}}</ref> [[सीएमयू कॉमन लिस्प]],<ref>{{cite web|title=डिज़ाइन विकल्प और एक्सटेंशन|url=http://common-lisp.net/project/cmucl/doc/cmu-user/extensions.html|access-date=2014-02-03|work=CMUCL User's Manual}}</ref> [[एंबेडेबल कॉमन लिस्प]],<ref>{{cite web|title=यादृच्छिक अवस्थाएँ|url=https://common-lisp.net/project/ecl/manual/ch12s02.html|access-date=2015-09-20|work=The ECL manual}}</ref> [[स्टील बैंक कॉमन लिस्प]],<ref>{{cite web|title=यादृच्छिक संख्या सृजन|url=http://www.sbcl.org/manual/#Random-Number-Generation|work=SBCL User's Manual}}</ref> [[जूलिया (प्रोग्रामिंग भाषा)|जूलिया]]  (जूलिया 1.6 एलटीएस तक, यह मर्सेन ट्विस्टर उपलब्ध था, परंतु 1.7 के उपरांत डिफ़ॉल्ट यादृच्छिक संख्या उत्पन्नक के रूप में एक बेहतर/तेज़ आरएनजी का उपयोग किया जाता है।<ref>{{Cite web |title=Random Numbers · The Julia Language |url=https://docs.julialang.org/en/v1/stdlib/Random/ |access-date=2022-06-21 |website=docs.julialang.org}}</ref>
* [[लिनक्स]] लाइब्रेरी और सॉफ्टवेयर: जीएलआईबी,<ref>{{cite web|title=Random Numbers: GLib Reference Manual|url=https://developer.gnome.org/glib/stable/glib-Random-Numbers.html}}</ref> जीएनयू एकाधिक परिशुद्धता अंकगणित लाइब्रेरी,<ref>{{cite web|title=यादृच्छिक संख्या एल्गोरिदम|url=http://gmplib.org/manual/Random-Number-Algorithms.html|access-date=2013-11-21|work=GNU MP}}</ref> [[जीएनयू ऑक्टेव]],<ref>{{cite web|title=16.3 Special Utility Matrices|url=https://www.gnu.org/software/octave/doc/interpreter/Special-Utility-Matrices.html|work=GNU Octave|quote=Built-in Function: rand}}</ref> [[जीएनयू वैज्ञानिक पुस्तकालय|जीएनयू साइंटिफिक लाइब्रेरी]]<ref>{{cite web|title=यादृच्छिक संख्या पर्यावरण चर|url=https://www.gnu.org/software/gsl/manual/html_node/Random-number-environment-variables.html|access-date=2013-11-24|work=GNU Scientific Library}}</ref>
* अन्य: [[ Microsoft Excel | माइक्रोसॉफ्ट एक्सेल]] ,<ref>{{citation|last=Mélard|first=G.|title=On the accuracy of statistical procedures in Microsoft Excel 2010|journal=[[Computational Statistics (journal)|Computational Statistics]]|volume=29|issue=5|pages=1095–1128|year=2014|citeseerx=10.1.1.455.5508|doi=10.1007/s00180-014-0482-5|s2cid=54032450}}.</ref> [[गॉस (सॉफ्टवेयर)|गॉस]],<ref>{{cite web|title=GAUSS 14 Language Reference|url=http://www.aptech.com/wp-content/uploads/2014/01/GAUSS14_LR.pdf}}</ref> [[ग्रेटल]]<ref>"[http://gretl.sourceforge.net/gretl-help/funcref.html#uniform uniform]". ''Gretl Function Reference''.</ref> [[था|स्टेटा]],<ref>{{cite web|title=New random-number generator—64-bit Mersenne Twister|url=https://www.stata.com/new-in-stata/random-number-generators/}}</ref> [[सेजमैथ]],<ref>{{cite web|title=Probability Distributions — Sage Reference Manual v7.2: Probablity|url=http://doc.sagemath.org/html/en/reference/probability/sage/gsl/probability_distribution.html}}</ref> [[साइलैब]],<ref>{{cite web|title=भव्य - यादृच्छिक संख्याएँ|url=https://help.scilab.org/docs/5.5.2/en_US/grand.html|work=Scilab Help}}</ref> [[मेपल (सॉफ्टवेयर)|मेपल]],<ref>{{cite web|title=रैंडम संख्या जनरेटर|url=http://www.maplesoft.com/support/help/Maple/view.aspx?path=rand|access-date=2013-11-21|work=Maple Online Help}}</ref> [[मतलब|मैटलैब]]<ref>{{cite web|title=यादृच्छिक संख्या जनरेटर एल्गोरिदम|url=http://www.mathworks.co.uk/help/matlab/ref/randstream.list.html|work=Documentation Center, [[MathWorks]]}}</ref>
यह [[अपाचे कॉमन्स]] में,<ref>{{cite web|title=डेटा जनरेशन|url=http://commons.apache.org/proper/commons-math/userguide/random.html|work=Apache Commons Math User Guide}}</ref> मानक [[C++]] लाइब्रेरी में ([[C++11]] के उपरांत),<ref>{{cite web|title=C++11 में यादृच्छिक संख्या सृजन|url=https://isocpp.org/files/papers/n3551.pdf|work=Standard C++ Foundation}}</ref><ref>{{cite web|title=std::mersenne_twister_engine|url=http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine|access-date=2012-09-25|work=Pseudo Random Number Generation}}</ref> और मैथेमैटिका में<ref>[http://reference.wolfram.com/language/tutorial/RandomNumberGeneration.html#569959585] Mathematica Documentation</ref> भी उपलब्ध है। बूस्ट सी++ लाइब्रेरी सहित कई प्रोग्राम लाइब्रेरी जैसे सीयूडीए,<ref>{{cite web|title=होस्ट एपीआई अवलोकन|url=http://docs.nvidia.com/cuda/curand/host-api-overview.html#generator-types|access-date=2016-08-02|work=CUDA Toolkit Documentation}}</ref> और [[एनएजी न्यूमेरिकल लाइब्रेरी]]<ref>{{cite web|title=G05 – Random Number Generators|url=http://www.nag.co.uk/numeric/fl/nagdoc_fl23/xhtml/G05/g05intro.xml|access-date=2012-05-29|work=NAG Library Chapter Introduction}}</ref>में इसके युग्मित कार्यान्वयन प्रदान किए जाते हैं।<ref>{{cite web|title=boost/random/mersenne_twister.hpp|url=http://www.boost.org/doc/libs/1_49_0/boost/random/mersenne_twister.hpp|access-date=2012-05-29|work=Boost C++ Libraries}}</ref> 

[[एसपीएसएस]] में मेर्सन ट्विस्टर, दो पीआरएनजी में से एक है: अन्य उत्पन्नक केवल पुराने प्रोग्रामों के साथ संगतता हेतु रखा गया है, और मर्सेन ट्विस्टर को "अधिक विश्वसनीय" घोषित किया जाता है।<ref>{{cite web|title=यादृच्छिक संख्या जेनरेटर|url=http://pic.dhe.ibm.com/infocenter/spssstat/v20r0m0/index.jsp?topic=%2Fcom.ibm.spss.statistics.help%2Fidh_seed.htm|access-date=2013-11-21|work=IBM SPSS Statistics}}</ref> मेर्सन ट्विस्टर इसी तरह [[एसएएस (सॉफ्टवेयर)|एसएएस]] में विभिन्न पीआरएनजी में से एक है: अन्य उत्पन्नक पुराने और अप्रचलित हैं।<ref>{{cite web|title=यादृच्छिक-संख्या फ़ंक्शंस का उपयोग करना|url=http://support.sas.com/documentation/cdl/en/lrdict/64316/HTML/default/viewer.htm#a001281561.htm|access-date=2013-11-21|work=SAS Language Reference}}</ref> मेर्सन ट्विस्टर स्टाटा में डिफ़ॉल्ट पीआरएनजी है, दूसरा स्टाटा के पुराने संस्करणों के साथ संगतता के लिए [[KISS (एल्गोरिदम)|केआइएसएस]] विधिकलन का उपयोग किया जाता है।<ref>Stata help: [https://www.stata.com/help.cgi?set%20rng set rng -- Set which random-number generator (RNG) to use]</ref>



== लाभ ==
* [[अनुमेय सॉफ़्टवेयर लाइसेंस|क्रिप्टएमटी]] के अतिरिक्त मेर्सन ट्विस्टर, सभी संस्करणों के लिए अनुमेय-लाइसेंसीकृत और पेटेंट-मुक्त है।
* मर्सेन ट्विस्टर सांख्यिकीय यादृच्छिकता के लिए कई परीक्षणों, जैसे डाइहार्ड परीक्षण और अधिकांश [[TestU01]] परीक्षणों, को पार करता है। यद्यपि, यह सभी [[TestU01]] परीक्षणों को पूरा नहीं करता है।।<ref name="TestU01">P. L'Ecuyer and R. Simard, "[http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf TestU01: "A C library for empirical testing of random number generators]", ''[[ACM Transactions on Mathematical Software]]'', 33, 4, Article 22 (August 2007).</ref>
* बहुत लम्बी अवधि <math>2^{19937}-1</math>. ध्यान दें कि यद्यपि लंबी अवधि यादृच्छिक संख्या उत्पन्नक में गुणवत्ता की गारंटी नहीं है, छोटी अवधि, जैसे कि <math>2^{32}</math> कई पुराने सॉफ़्टवेयर पैकेजों में सामान्य, समस्याग्रस्त हो सकता है।<ref>Note: 2<sup>19937</sup> is approximately 4.3&nbsp;×&nbsp;10<sup>6001</sup>; this is many orders of magnitude larger than the estimated number of particles in the [[Observable universe#Matter content|observable universe]], which is 10<sup>87</sup>.</ref>
* प्रत्येक <math>1 \le k \le 623</math> के लिए k-वितरण 32-बिट सटीकता को समर्थित करता है।
* कार्यान्वयन सामान्यतः हार्डवेयर-कार्यान्वित विधियों की तुलना में तेजी से यादृच्छिक संख्याएं निर्मित करता है। एक अध्ययन में पाया गया कि मेर्सन ट्विस्टर हार्डवेयर-कार्यान्वित, प्रोसेसर-आधारित [[RDRAND|आरडीरैंड]] निर्देश समुच्चय की तुलना में लगभग बीस गुना तेजी से 64-बिट फ़्लोटिंग पॉइंट यादृच्छिक संख्याएँ निर्मित करता है।<ref>{{cite journal|last1=Route|first1=Matthew|date=August 10, 2017|title=रेडियो-फ्लेयरिंग अल्ट्राकूल बौना जनसंख्या संश्लेषण|journal=The Astrophysical Journal|volume=845|issue=1|page=66|arxiv=1707.02212|bibcode=2017ApJ...845...66R|doi=10.3847/1538-4357/aa7ede|s2cid=118895524}}</ref>


== हानि ==
* 2.5 [[KiB]] का अपेक्षाकृत बड़ा स्टेट बफर, जब तक कि टाइनीएमटी संस्करण का उपयोग नहीं किया जाता है।
* आधुनिक मानकों के अनुसार औसत श्रेणी का थ्रूपुट, जब तक कि एसएफएमटी संस्करण का उपयोग नहीं किया जाता है।<ref>{{cite web|title=SIMD-oriented Fast Mersenne Twister (SFMT): twice faster than Mersenne Twister|url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/|access-date=27 March 2017|website=Japan Society for the Promotion of Science}}</ref>
* TestU01 सुइट में क्रश और बिगक्रश दोनों में दो स्पष्ट विफलताएं प्रदर्शित होती हैं। मेर्सन ट्विस्टर की तरह परीक्षण, एक <math>\textbf{F}_2</math>-बीजगणित पर आधारित है।<ref name="TestU01" />* कई उदाहरण जो केवल बीजगणितीय मानों में भिन्न होते हैं, सामान्यतः [[ मोंटे कार्लो सिमुलेशन ]]के लिए उपयुक्त नहीं होते हैं। मोंटे-कार्लो सिमुलेशन के लिए स्वतंत्र यादृच्छिक संख्या उत्पन्नक की आवश्यकता होती है, यद्यपि पैरामीटर मानों के कई समुच्चयों को चुनने के लिए एक विधि उपलब्ध है।<ref>{{cite web|author1=Makoto Matsumoto|author2=Takuji Nishimura|title=छद्म यादृच्छिक संख्या जेनरेटर का गतिशील निर्माण|url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dgene.pdf|access-date=19 July 2015}}</ref><ref>{{cite web|author1=Hiroshi Haramoto|author2=Makoto Matsumoto|author3=Takuji Nishimura|author4=François Panneton|author5=Pierre L'Ecuyer|title=Efficient Jump Ahead for F2-Linear Random Number Generators|url=http://www.iro.umontreal.ca/~lecuyer/myftp/papers/jumpf2.pdf|access-date=12 Nov 2015}}</ref>
* खराब प्रसार: यदि प्रारंभिक स्थिति अत्यधिक गैर-यादृच्छिक है - विशेषकर यदि प्रारंभिक स्थिति में कई शून्य हैं तो [[ यादृच्छिकता परीक्षण |यादृच्छिकता परीक्षण]] उत्तीर्ण करने वाले आउटपुट को उत्पन्न करने में लंबा समय लग सकता है। इसका एक परिणाम यह है कि उत्पन्नक के दो उदाहरण, प्रारंभिक अवस्थाओं के साथ प्रारंभ हुए जो लगभग समान हैं, सामान्यतः अंततः अलग होने से पहले, कई पुनरावृत्तियों के लिए लगभग समान अनुक्रम का उत्पादन करते हैं। एमटी विधिकलन के लिए 2002 के अपडेट ने आरंभीकरण में सुधार किया है, इसलिए ऐसी स्थिति के साथ प्रारंभ करना असंभव है।<ref>{{cite web|title=mt19937ar: Mersenne Twister with improved initialization|url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html|access-date=4 October 2015|work=hiroshima-u.ac.jp}}</ref> जीपीयू संस्करण एमटीजीपी को और भी बेहतर बताया गया है।<ref name="fog">{{cite journal|last1=Fog|first1=Agner|date=1 May 2015|title=वेक्टर प्रोसेसर और मल्टीकोर प्रोसेसर के लिए छद्म-यादृच्छिक संख्या जेनरेटर|journal=Journal of Modern Applied Statistical Methods|volume=14|issue=1|pages=308–334|doi=10.22237/jmasm/1430454120|doi-access=free}}</ref>
* इसमें 1 से अधिक 0 वाले अनुवर्ती सम्मिलित हैं। इससे कई-शून्य स्टेट से पुनर्प्राप्ति को कठिन बनाने के लिए खराब प्रसार गुण युग्मित हो जाता है।
* यदि क्रिप्टएमटी संस्करण का उपयोग नहीं किया जाता है तो मर्सेन ट्विस्टर कैरिप्टोग्राफिकली सुरक्षित नहीं होता है। कारण यह है कि पर्याप्त संख्या के आवर्तनों की पर्यवेक्षण (MT19937 के परिप्रेक्ष्य में 624, क्योंकि इससे भविष्य के आवर्तन उत्पन्न होते हैं) से भविष्य के सभी आवर्तनों की पूर्वानुमान करने में सक्षम हो जाता है।

== विकल्प ==
एक वैकल्पिक उत्पन्नक, वेल  त्वरित पुनर्प्राप्ति, समान यादृच्छिकता और लगभग समान गति प्रदान करता है।<ref>P. L'Ecuyer, "Uniform Random Number Generators", ''[[International Encyclopedia of Statistical Science]]'', Lovric, Miodrag (Ed.), Springer-Verlag, 2010.</ref>

मार्साग्लिया के[[ xorshift | एक्सओआर शिफ्ट]] उत्पन्नक और उनके संस्करण, एलएफएसआर की श्रेणी में सबसे तेज़ हैं।<ref>{{cite web|title=xorshift*/xorshift+ generators and the PRNG shootout|url=http://prng.di.unimi.it}}</ref>

64-बिट एमईएलजी, के-वितरण गुणों के संदर्भ में पूरी तरह से अनुकूलित हैं।<ref>{{Cite journal|last1=Harase|first1=S.|last2=Kimoto|first2=T.|date=2018|title=Implementing 64-bit Maximally Equidistributed F<sub>2</sub>-Linear Generators with Mersenne Prime Period|url=https://github.com/sharase/melg-64|journal=ACM Transactions on Mathematical Software|volume=44|issue=3|pages=30:1–30:11|arxiv=1505.06582|doi=10.1145/3159444|s2cid=14923086}}</ref>

[[ACORN (PRNG)|ऐकॉर्न,]] जिसका प्रकाशन 1989 मे हुआ था एक और के-वितरित पीआरएनजी है, जो एमटी के समान संगणन गति और बेहतर सांख्यिकीय गुण प्रदर्शित करता है क्योंकि यह सभी उपलब्ध (2019) TestU01 मानदंडों को पूरा करता है; जब मापदंडों के उचित विकल्पों के साथ उपयोग किया जाता है, तो ऐकॉर्न में लंबी अवधि और सटीकता हो सकती है।

पीसीजी परिवार उत्पन्नक, अधिक आधुनिक लंबी अवधि वाला उत्पन्नक है, जिसमें बेहतर कैश स्थानीयता और आधुनिक विश्लेषण विधियों का उपयोग करने वाले पूर्वाग्रह प्रत्यक्ष नहीं है।<ref>{{cite web|date=27 July 2017|title=पीसीजी पेपर|url=https://www.pcg-random.org/paper.html}}</ref>



== के-वितरण ==
एक w-बिट पूर्वनिर्धारित अनुक्रम <math>x_i</math> जिसकी अवधि P है, को v-बिट की सटीकता तक k-वितरित माना जाता है यदि निम्नलिखित समीकरण सत्य होता है।

: प्राथमिक v बिटों द्वारा गठित संख्या x को truncv(x) से चिह्नित किया जाता है, और k v-बिट सदिशों को P द्वारा चिन्हित किया जाता है तोː
:: <math> (\operatorname{trunc}_v(x_i), \operatorname{trunc}_v(x_{i+1}), \, \ldots, \operatorname{trunc}_v(x_{i+k-1})) \quad (0\leq i< P) </math>.
: तो पूर्ण-शून्य संयोजन को छोड़कर प्रत्येक <math>2^{kv}</math> बिट्स का संभावित संयोजन एक अवधि में समान संख्या में होता है, जो एक बार न्यूनतम होता है।

== विधिकलन विवरण ==
[[File:Mersenne_Twister_visualisation.svg|thumb|288x288px|मेर्सन ट्विस्टर का उपयोग करके छद्म-यादृच्छिक 32-बिट पूर्णांकों की पीढ़ी का प्रदर्शन। 'नंबर निकालें' अनुभाग एक उदाहरण दिखाता है जहां पूर्णांक 0 पहले ही आउटपुट हो चुका है और सूचकांक पूर्णांक 1 पर है। 'जनरेट नंबर' तब चलाया जाता है जब सभी पूर्णांक आउटपुट हो चुके होते हैं।]]डब्ल्यू-बिट शब्द लंबाई के लिए, मेर्सन ट्विस्टर श्रेणी <math>[0, 2^w-1]</math> में पूर्णांक उत्पन्न करता है .

मेर्सन ट्विस्टर विधिकलन एक परिमित [[बाइनरी अंक प्रणाली|द्विआधारी अंक प्रणाली]] क्षेत्र पर [[पुनरावृत्ति संबंध]] <math>\textbf{F}_2</math> पर आधारित है। विधिकलन एक व्यावर्तित [[सामान्यीकृत फीडबैक शिफ्ट रजिस्टर]] है<ref>{{Cite journal|last1=Matsumoto|first1=M.|last2=Kurita|first2=Y.|year=1992|title=मुड़े हुए जीएफएसआर जनरेटर|url=http://ir.lib.hiroshima-u.ac.jp/00015037|journal=ACM Transactions on Modeling and Computer Simulation|volume=2|issue=3|pages=179–194|doi=10.1145/146382.146383|s2cid=15246234}}</ref> मूल विचार है की किसी श्रृंखला <math>x_i</math> को एक सरल पुनरावृत्ति संबंध के माध्यम से परिभाषित करना है, और फिर फॉर्म की आउटपुट संख्याएँ <math>x_i^T</math>, जहां T एक व्युत्क्रमणीय <math>\textbf{F}_2</math>-आव्यूह है जिसे विवर्तित प्रतिनिधित्व कहा जाता है।

सामान्य विधिकलन को निम्नलिखित मात्राओं द्वारा दर्शाया जाता है (इनमें से कुछ स्पष्टीकरण शेष विधिकलन को पढ़ने के बाद ही समझ में आते हैं):

* w: शब्द का आकार (बिट्स की संख्या में)
* एन: पुनरावृत्ति की श्रेणी
* एम: मध्य शब्द, <math>1 \le m < n</math> श्रृंखला को परिभाषित करने वाले पुनरावृत्ति संबंध में प्रयुक्त एक ऑफसेट <math>x</math>, 
* आर: एक शब्द <math>0 \le r \le w - 1</math> का पृथक्करण बिंदु, या निचले बिटमास्क के बिट्स की संख्या, 
* ए: तर्कसंगत सामान्य रूप ट्विस्ट आव्यूह के गुणांक
* बी, सी: टीजीएफएसआर (आर) विवर्तन बिटमास्क
* एस, टी: टीजीएफएसआर (आर) विवर्तन बिट शिफ्ट
* यू, डी, एल: अतिरिक्त मेर्सन ट्विस्टर विवर्तन बिट शिफ्ट/मास्क

उस प्रतिबंध के साथ <math>2^{nw-r}-1</math> एक मेरसेन प्राइम है। यह विकल्प आदिमता परीक्षण और k-वितरण परीक्षण को सरल निर्मित बनाता है जो पैरामीटर खोज में आवश्यक हैं।

श्रृंखला <math>x</math> पुनरावृत्ति संबंध के साथ डब्ल्यू-बिट मात्राओं की एक श्रृंखला के रूप में परिभाषित किया गया है:

: <math>x_{k+n} := x_{k+m} \oplus \left( ({x_k}^u \mid {x_{k+1}}^l) A \right)\qquad
k=0,1,\ldots</math>
जहाँ <math>\mid</math> बिट सदिशों के संयोजन को दर्शाता है (बाईं ओर ऊपरी बिट्स के साथ), <math>
\oplus

</math> बिटवाइज़ [[एकमात्र]] (XOR), <math>
x_{k}^{u}

</math> अर्थात ऊपरी {{nowrap|''w'' − ''r''}} का <math>
x_k

</math>, और <math>
x_{k+1}^{l}

</math> का अर्थ निम्न आर बिट्स है <math>
x_{k+1}

</math>. विवर्त परिवर्तन ए को तर्कसंगत सामान्य रूप में परिभाषित किया गया है:<math display="block">
A = \begin{pmatrix} 0 & I_{w - 1} \\ a_{w-1} & (a_{w - 2}, \ldots , a_0) \end{pmatrix}
</math><math>
I_{w-1}

</math> के रूप में <math>
(w-1)(w-1)
</math> शिनाख्त सांचा है। तर्कसंगत सामान्य रूप का लाभ यह है कि ए द्वारा गुणा को कुशलतापूर्वक इस प्रकार व्यक्त किया जा सकता है: (याद रखें कि यहां आव्यूह गुणा किया जा रहा है <math>
\textbf{F}_{2}

</math>, और इसलिए बिटवाइज़ XOR जोड़ का स्थान लेता है)<math display="block">
\boldsymbol{x}A = \begin{cases}\boldsymbol{x} \gg 1 & x_0 = 0\\(\boldsymbol{x} \gg 1) \oplus \boldsymbol{a} & x_0 = 1\end{cases}
</math>जहाँ <math>
x_0

</math> का निम्नतम ऑर्डर बिट <math>
x

</math> है .

टीजीएफएसआर (आर) के समान, मेर्सन ट्विस्टर को समान वितरण की कम आयामीता की भरपाई के लिए एक टेम्पर्ड प्रतिनिधित्व के साथ कैस्केड किया गया है। ध्यान दें कि यह आव्यूह ए का उपयोग करने के समान है <math>
A = T^{-1}*AT

</math> टी के लिए एक व्युत्क्रम आव्यूह, और इसलिए नीचे उल्लिखित विशेषता बहुपद का विश्लेषण अभी भी मान्य है।

ए के साथ, हम सरलता से गणना करने योग्य होने के लिए एक विवर्तन परिवर्तन चुनते हैं, और इसलिए वास्तव में टी का निर्माण नहीं करते हैं। मेर्सन ट्विस्टर के परिप्रेक्ष्य में आव्यूह को इस प्रकार परिभाषित किया गया है

: <math>
\begin{aligned}
y &\equiv x \oplus ((x\gg u)~\And~d)\\
y &\equiv y \oplus ((y\ll s)~\And~b)\\
y &\equiv y \oplus ((y\ll t)~\And~c)\\
z &\equiv y \oplus (y\gg l)
\end{aligned}
</math>
जहाँ <math>x</math> श्रृंखला से अगला मान है, <math>y</math> एक अस्थायी मध्यवर्ती मान है, और <math>z</math> विधिकलन से <math>\ll</math>और <math>\gg</math> [[बिट-शिफ्ट]] के रूप में, और <math>\&</math> बिटवाइज [[तार्किक संयोजन]] के रूप में लौटाया गया मान है । निचले-बिट समवितरण को बेहतर बनाने के लिए पहला और आखिरी परिवर्तन जोड़ा जाता है। टीजीएफएसआर के गुण से, <math>s + t \ge \lfloor{\frac{w}{2}}\rfloor - 1</math> ऊपरी बिट्स के लिए समवितरण की ऊपरी सीमा तक पहुंचना आवश्यक है।

MT19937 के लिए गुणांक हैं:

<math>
\begin{aligned}
(w, n, m, r) &= (32, 624, 397, 31)\\
a &= \textrm{9908B0DF}_{16}\\
(u, d) &= (11, \textrm{FFFFFFFF}_{16})\\
(s, b) &= (7, \textrm{9D2C5680}_{16})\\
(t, c) &= (15, \textrm{EFC60000}_{16})\\
l &= 18\\
\end{aligned}
</math>

ध्यान दें कि मेर्सन ट्विस्टर के 32-बिट कार्यान्वयन में सामान्यतः d = FFFFFFFF<sub>16</sub> होता है. परिणामस्वरूप, कभी-कभी डी को विधिकलन विवरण से हटा दिया जाता है, क्योंकि उस स्थिति में डी के साथ बिटवाइज़ तार्किक संयोजन का कोई प्रभाव नहीं पड़ता है।

MT19937-64 के लिए गुणांक हैं:<ref name="std::mersenne_twister_engine">{{cite web|title=std::mersenne_twister_engine|url=http://en.cppreference.com/w/cpp/numeric/random/mersenne_twister_engine|access-date=2015-07-20|work=Pseudo Random Number Generation}}</ref>

<math>
\begin{aligned}
(w, n, m, r) = (64, 312, 156, 31)\\
a = \textrm{B5026F5AA96619E9}_{16}\\
(u, d) = (29, \textrm{5555555555555555}_{16})\\
(s, b) = (17, \textrm{71D67FFFEDA60000}_{16})\\
(t, c) = (37, \textrm{FFF7EEE000000000}_{16})\\
l = 43\\
\end{aligned}

</math>


=== आरंभीकरण ===
मेर्सन ट्विस्टर कार्यान्वयन के लिए आवश्यक स्थिति प्रत्येक डब्ल्यू बिट्स के एन मानों की एक सरणी है। सरणी को प्रारंभ करने के लिए,  एक w-बिट बीज मान का उपयोग किया जाता है तथा  <math>x_0</math> द्वारा <math>x_{n-1}</math> व्यवस्थित करके <math>x_0</math> बीज मान और उसके बाद निम्नलिखित को

: <math>
x_i = f \times (x_{i-1} \oplus (x_{i-1} \gg (w-2))) + i
</math>
के लिए <math>i</math> से <math>1</math> को <math>n-1</math> के रूप में संयोजित किया जाता है।

* विधिकलन द्वारा उत्पन्न पहला मान <math>x_n</math> उस पर आधारित होता है न की <math>x_0</math> पर। 
* स्थिरांक f उत्पन्नक के लिए एक और मापदंड निर्मित करता है, यद्यपि यह विधिकलन का उचित भाग नहीं है।
* MT19937 के लिए f का मान 1812433253 है।
* MT19937-64 के लिए f का मान 6364136223846793005 है।<ref name="std::mersenne_twister_engine" />


=== पारंपरिक जीएफएसआर के साथ तुलना ===
<math>2^{nw-r}-1</math> प्राप्त करने के लिए टी[[जीएफएसआर]] में अवधि की सैद्धांतिक ऊपरी सीमा, <math>\phi_{B}(t)</math> एक [[आदिम बहुपद (क्षेत्र सिद्धांत)|प्राथमिक बहुपद]] होता है <math>\phi_{B}(t)</math> का अभिलक्षणिक बहुपदː

: <math>
B = \begin{pmatrix}
0 & I_w & \cdots & 0 & 0 \\
\vdots & & & & \\
I_w & \vdots & \ddots & \vdots & \vdots \\
\vdots & & & & \\
0 & 0 & \cdots & I_w & 0 \\
0 & 0 & \cdots & 0 & I_{w - r} \\
S & 0 & \cdots & 0 & 0
\end{pmatrix}
\begin{matrix}
\\ \\ \leftarrow m\text{-th row} \\ \\ \\ \\
\end{matrix}
</math> है। 
: <math>
S = \begin{pmatrix} 0 & I_r \\ I_{w - r} & 0 \end{pmatrix} A
</math>
ट्विस्ट परिवर्तन निम्नलिखित प्रमुख गुणों के साथ पारंपरिक जीएफएसआर में सुधार करता है:

* अवधि सैद्धांतिक ऊपरी सीमा <math>2^{nw-r}-1</math> तक प्रसारित होती है  (सिवाय यदि 0 से प्रारंभ किया गया हो)
* एन आयामों में समान वितरण (उदाहरण के लिए [[रैखिक सर्वांगसम जनरेटर|रैखिक सर्वांगसम उत्पन्नक]] पांच आयामों में उचित वितरण का सर्वोत्तम प्रबंधन कर सकता है)

=== स्यूडोकोड ===
निम्नलिखित स्यूडोकोड सामान्य मेर्सन ट्विस्टर विधिकलन को लागू करता है। स्थिरांक w, n, m, r, a, u, d, s, b, t, c, l, और f उपरोक्त विधिकलन विवरण के अनुसार हैं। यह माना जाता है कि int w बिट्स के साथ मान रखने के लिए पर्याप्त टाइप का प्रतिनिधित्व करता है:
  ''// Create a length '''n''' array to store the state of the generator''

  '''int'''[0..'''n'''-1] MT
  '''int''' index := '''n'''+1
  '''const int''' lower_mask = (1 << '''r''') - 1 ''// That is, the binary number of '''r''' 1's''
  '''const int''' upper_mask = lowest '''w''' bits of ('''not''' lower_mask)
  
  ''// Initialize the generator from a seed''
  '''function''' seed_mt('''int''' seed) {
      index := '''n'''
      MT[0] := seed
      '''for''' i '''from''' 1 '''to''' ('''n''' - 1) { ''// loop over each element''
          MT[i] := lowest '''w''' bits of ('''f''' * (MT[i-1] '''xor''' (MT[i-1] >> ('''w'''-2))) + i)
      }
  }
  
  ''// Extract a tempered value based on MT[index]''
  ''// calling twist() every '''n''' numbers''
  '''function''' extract_number() {
      '''if''' index >= '''n''' {
          '''if''' index > '''n''' {
            '''error''' "Generator was never seeded"
            ''// Alternatively, seed with constant value; 5489 is used in reference C code''
          }
          twist()
      }
  
      '''int''' y := MT[index]
      y := y '''xor''' ((y >> '''u''') '''and''' '''d''')
      y := y '''xor''' ((y << '''s''') '''and''' '''b''')
      y := y '''xor''' ((y << '''t''') '''and''' '''c''')
      y := y '''xor''' (y >> '''l''')
  
      index := index + 1
      '''return''' lowest '''w''' bits of (y)
  }
  
  ''// Generate the next'' n ''values from the series x_i'' 
  '''function''' twist() {
      '''for''' i '''from''' 0 '''to''' ('''n'''-1) {
          '''int''' x := (MT[i] '''and''' upper_mask)
                    | (MT[(i+1) '''mod''' '''n'''<nowiki>] </nowiki>'''and''' lower_mask)
          '''int''' xA := x >> 1
          '''if''' (x '''mod''' 2) != 0 { ''// lowest bit of x is 1''
              xA := xA '''xor''' '''a'''
          }
          MT[i] := MT[(i + '''m''') '''mod''' '''n'''] '''xor''' xA
      }
      index := 0
  }

== संस्करण ==

=== क्रिप्टएमटी ===
{{Main article|क्रिप्टएमटी}}
[[CryptMT|क्रिप्टएमटी]] एक [[ धारा सिफर |स्ट्रीम साइफर]] तथा [[क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म यादृच्छिक संख्या जनरेटर|क्रिप्टोग्राफ़िक रूप से सुरक्षित छद्म यादृच्छिक संख्या उत्पन्नक]] है जो आंतरिक रूप से मेर्सन ट्विस्टर का उपयोग करता है।<ref name="eSTREAM">{{cite web|title=क्रिप्टएमटी और फ़ुबुकी|url=http://www.ecrypt.eu.org/stream/cryptmtfubuki.html|access-date=2017-11-12|publisher=[[eCRYPT]]}}</ref><ref>{{Cite web|last1=Matsumoto|first1=Makoto|last2=Nishimura|first2=Takuji|last3=Hagita|first3=Mariko|last4=Saito|first4=Mutsuo|year=2005|title=Cryptographic Mersenne Twister and Fubuki Stream/Block Cipher|url=http://eprint.iacr.org/2005/165.pdf}}</ref> इसे मात्सुमोतो और निशिमुरा ने मारिको हागिटा और मुत्सुओ सैतो के साथ मिलकर विकसित किया था। इसे [[eCRYPT|ई]][[CryptMT|क्रिप्ट]] नेटवर्क के [[eSTREAM|ई]][[ धारा सिफर |स्ट्रीम]] परियोजना में प्रस्तुत किया गया था।<ref name="eSTREAM" />मेर्सन ट्विस्टर या इसके अन्य संस्करणों के विपरीत, क्रिप्टएमटी [[सॉफ्टवेयर पेटेंट|सॉफ्टवेयर एकस्व]] है।

=== एमटीजीपी ===
एमटीजीपी मुत्सुओ सैटो और माकोतो मात्सुमोतो द्वारा प्रकाशित [[ ग्राफ़िक्स प्रोसेसिंग युनिट | ग्राफ़िक्स प्रोसेसिंग इकाई]] के लिए अनुकूलित मेर्सन ट्विस्टर का एक प्रकार है।<ref>{{cite arXiv|eprint=1005.4973v3|class=cs.MS|author1=Mutsuo Saito|author2=Makoto Matsumoto|title=मेरसेन ट्विस्टर के वेरिएंट ग्राफिक प्रोसेसर के लिए उपयुक्त हैं|year=2010}}</ref> मूल रैखिक पुनरावृत्ति संचालन एमटी से विस्तृत होते हैं और पैरामीटर्स चुने जाते हैं ताकि कई थ्रेड समानांतर में पुनरावृत्ति की गणना कर सकें, साथ ही अपने स्थिति स्थान को साझा करके मेमोरी लोड को कम कर सकें। लेख में एमटी पर [[समान वितरण]] में सुधार और 5×10 के लिए 4.7 एमएस के अत्यधिक पुराने जीपीयू (192 कोर के साथ [[ NVIDIA | एनविडिया]] जीटीएक्स 260) पर प्रदर्शन का दावा किया गया है।

=== एसएफएमटी ===
एसएफएमटी (एकल निर्देश, एकाधिक डेटा-उन्मुख फास्ट मेर्सन ट्विस्टर) मेर्सन ट्विस्टर का एक प्रकार है, जिसे 2006 में प्रस्तुत किया गया था।<ref>{{cite web|title=SIMD-उन्मुख फास्ट मेरसेन ट्विस्टर (SFMT)|url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/index.html|access-date=4 October 2015|work=hiroshima-u.ac.jp}}</ref> इसे 128-बिट एसआइएमडी पर चलते समय तेज़ बनाने के लिए प्रारूपित किया गया है।

* यह मेरसेन ट्विस्टर से लगभग दोगुना तेज़ है।<ref>{{cite web|title=SFMT:Comparison of speed|url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/SFMT/speed.html|access-date=4 October 2015|work=hiroshima-u.ac.jp}}</ref>
* एसएफएमटी, एमटी की तुलना में वी-बिट सटीकता के साथ बेहतर इक्विडिस्ट्रीब्यूशन गुणधर्म रखता है, परंतु यह वेल की तुलना में बेहतर नहीं है।
* इसमें एमटी की तुलना में शून्य-अतिरिक्त प्रारंभिक अवस्था से त्वरित पुनर्प्राप्ति होती है, लेकिन वेल की तुलना में धीमी होती है।
* यह 2<sup>607</sup> − 1 से 2<sup>216091</sup> − 1 तक विभिन्न अवधियों का समर्थन करता है।

इंटेल [[SSE2|एसएसई2]] और [[PowerPC|पावरपीसी]] अल्टीवेक एसएफएमटी द्वारा समर्थित हैं। इसका उपयोग [[PlayStation 3|प्लेस्टेशन 3]] में [[सेल (माइक्रोप्रोसेसर)|सेल]] वाले खेल के लिए भी किया जाता है।<ref>{{cite web|title=PlayStation3 License|url=http://www.scei.co.jp/ps3-license/index.html|access-date=4 October 2015|work=scei.co.jp}}</ref>


=== टाइनीएमटी ===
टाइनीएमटी मेरसेन ट्विस्टर का एक प्रकार है, जिसे 2011 में सैटो और मात्सुमोतो द्वारा प्रस्तावित किया गया था।<ref>{{cite web|title=टिनी मेरसेन ट्विस्टर (टिनीएमटी)|url=http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/TINYMT/index.html|access-date=4 October 2015|work=hiroshima-u.ac.jp}}</ref> टाइनीएमटी केवल 127 बिट्स स्टेट स्पेस का उपयोग करता है, जो मूल स्टेट के 2.5 KiB की तुलना में एक महत्वपूर्ण कमी है। यद्यपि, इसकी एक अवधि <math>
2^{127}-1

</math> होती है जो मूल एमटी से अत्यधिक छोटी है, इसलिए लेखकों द्वारा इसकी अनुशंसा केवल उन स्थितियों में की जाती है जहां मेमोरी प्रमुख है।

== संदर्भ ==
{{Reflist|30em}}


== अग्रिम पठन ==
* {{citation|last=Harase|first=S.|title=On the <math>\mathbb{F}_2</math>-linear relations of Mersenne Twister pseudorandom number generators|journal=Mathematics and Computers in Simulation|volume=100|pages=103–113|year=2014|arxiv=1301.5435|doi=10.1016/j.matcom.2014.02.002|s2cid=6984431}}.
* {{citation|last=Harase|first=S.|title=Conversion of Mersenne Twister to double-precision floating-point numbers|journal=Mathematics and Computers in Simulation|volume=161|pages=76–83|year=2019|arxiv=1708.06018|doi=10.1016/j.matcom.2018.08.006|s2cid=19777310}}.


== बाहरी संबंध ==
* [http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/ARTICLES/earticles.html The academic paper for MT, and related articles by Makoto Matsumoto]
* [http://www.math.sci.hiroshima-u.ac.jp/m-mat/MT/emt.html Mersenne Twister home page, with codes in C, Fortran, Java, Lisp and some other languages]
* [https://github.com/bmurray7/mersenne-twister-examples Mersenne Twister examples] — a collection of Mersenne Twister implementations, in several programming languages - at [[GitHub]]
* [http://www.codeproject.com/KB/DLL/SFMT_dll.aspx?msg=3130186 SFMT in Action: Part I – Generating a DLL Including SSE2 Support] – at [[Code Project]]
{{Mersenne}}
[[Category: छद्म यादृच्छिक संख्या जनरेटर]] [[Category: स्यूडोकोड उदाहरण सहित लेख]] [[Category: जापानी आविष्कार]] 



[[Category: Machine Translated Page]]
[[Category:Created On 22/06/2023]]
[[Category:Vigyan Ready]]