کاذبی تصادفی عدد مولّد

آزاد دائرۃ المعارف، ویکیپیڈیا سے
:چھلانگ بطرف رہنمائی، تلاش
اصطلاح term

کاذبی
مولّد
تولید

pseudo
generator
generate

شمارندہ پر تصادفی عدد تولید کرنے کے لیے ایسے طریقے استعمال ہوتے ہیں، جو تصادفی نہیں ہوتے، مگر اعداد کا ایسا متوالیہ تولید کرتے ہیں، جس پر تصادفی ہونے کا گمان ہوتا ہے، اور دراصل یہ تصادف پن کے تمام "اختبار" پر پورا اترتے ہیں۔ ایسے مولد کو فرضی تصادفی عدد مولّد کہا جاتا ہے۔

تعریف: ریاضی میں تصادفی عدد مولّد ایسے طریقہ کو کہا جاتا ہے جو صفر اور ایک کے درمیانی وقفہ (0،1) میں عدد x تولید کرے، اس خوبی کے ساتھ کہ عدد x کا کسی ذیلی وقفہ (a,b) میں واقع ہونے کا احتمال اس ذیلی وقفہ کی لمبائی b-a کے برابر ہو، یعنی

 \Pr\left(x\in (a,b)\right) = b-a  \,,\,\,\,\,\,\,\, (a,b) \subseteq (0,1)

غور کرو کہ اس طریقہ سے جنم پانے والا تصادفی متغیر یکساں توزیع احتمال رکھے گا۔

فرضی تصادفی عدد مولد، عام طور پر ایک (بمعامل) رَجعت نسبت ہوتا ہے۔ مثال کے طور پر اس کے لیے ایک مشہور رَجعت نسبت یہ ہے:

 x_{n+1} = a x_n + c \mod m

جہاں دائم a ،c، اور m، کو نہایت احتیاط سے چنا جاتا ہے، اور \mod m سے مراد بمعامل ہے۔ کسی بھی مثبت صحیح عدد x_0 سے شروع کر کے ہمیں فرضیتصادفی اعداد کا متوالیہ

 x_0, x_1, x_2, \cdots

تولید ہوتا ہے۔ غور کرو کہ یہ متوالیہ معیادی ہے، اور اس کی معیاد زیادہ سے زیادہ m ہے، یعنی اتنے قدموں کے بعد یہ دہرائے گا۔ اس متوالیہ کے کسی بھی صحیح عدد x_n سے (0,1) وقفہ کے درمیان تصادفی عدد

r_n=\frac{x_n}{m}

بنتا ہے۔ رجعت نسبت کے دائم اعداد کا ایک اچھا انتخاب یہ ہے،

a=630360016,\, m=2^{31}-1,\, c=0

اکثر برمجہ ماحول (مثلاً سائیلیب) میں پائے جانے والے مولّد اسی اصول (بمعامل رَجعت نسبت) پر بنائے جاتے ہیں۔ واضح رہے کہ یہ مولّد کرپٹوگرافی اطلاقیہ کے لیے موزوں نہیں ہوتے۔ حالیہ برسوں میں ایک نئے مولّد کا چرچا ہؤا ہے جو مرسین (مفرد عدد) twister کے نام سے مشہور ہے، اور جسے جاپانی محققین نے بنایا ہے۔[1]


کسی وقفہ میں تصادفی عدد کی تولید[ترمیم]

اگر 10 اور 15 کے درمیان تصادفی عدد تولید کرنا ہو (یکساں توزیع احتمال کے ساتھ)، تو ہم اپنے فرضی تصادفی عدد مولد سے معیاری وقفہ (0,1) میں عدد r حاصل کرنے کے بعد، مطلوبہ وقفہ میں تصادفی عدد یوں حاصل کریں گے: \ 10 + (15-10) \times r

تصادفی صحیح عدد کی تولید[ترمیم]

اگر 1 اور N کے درمیان تصادفی صحیح عدد تولید کرنا ہو (یکساں توزیع احتمال کے ساتھ)، تو ہم اپنے فرضی تصادفی عدد مولد سے معیاری وقفہ (0,1) میں عدد r حاصل کرنے کے بعد، مطلوبہ صحیح تصادفی عدد یوں حاصل کریں گے:

\ 1+ \lfloor N \times r \rfloor

جہاں علامت \lfloor x\rfloor سے مراد ہے x سے کم سب سے بڑا صحیح عدد۔ مثلاً \lfloor 3.2\rfloor=3

تصادفی تَبَدُّلِ کامل[ترمیم]

اگر صحیح اعداد کے مجموعہ 1,2,3, \cdots, N کا تصادفی تَبَدُّلِ کامل تولید کرنا ہو تو یہ طریقہ ہے:

  1. رکھو \ v \leftarrow N، اور D(i)=i,\,\,\,\, i=1,2,\cdots,N
  2. اپنے فرضی تصادفی عدد مولد سے معیاری وقفہ (0,1) میں عدد r حاصل کرنے کے بعد صحیح تصادفی عدد \ n= 1+ \lfloor v \times r \rfloor حاصل کرو۔
  3. \ D(n) اور \ D(v) کی اقدار کا باہمی تبادلہ کر دو۔
  4. اب \ v  \leftarrow v-1 رکھو۔ اگر \ v>1 تو واپس قدم 2 پر چلو، ورنہ رُک جاؤ، اور تصادفی تبدل کامل \left(D(1), D(2), \cdots, D(N)\right) ہے۔


تصادفی عدد بمطابق متفرد توزیع احتمال[ترمیم]

اگر تصادفی متغیر X ہو جو دو اقدار x_0 اور x_1 لیتا ہو۔ یعنی دو نکاتی توزیعِ احتمال ہو، قدر x_0 احتمال p_0 کے ساتھ، اور دوسری قدر x_1 احتمال \ 1-p_0 کے ساتھ۔ تو ہم اپنے فرضی تصادفی عدد مولد سے معیاری وقفہ (0,1) میں عدد r حاصل کرنے کے بعد، قدر x_0 چنیں گے اگر \ r < p_0، ورنہ قدر x_1۔ اس طریقہ کو عام کیا جا سکتا ہے کسی بھی متفرد توزیع احتمال کے لیے۔

تصادفی عدد بمطابق متواصل توزیع احتمال[ترمیم]

Cdf pseudo rng.png

اگر تصادفی متغیر Y بمطابق متواصل توزیعِ احتمال \ F_Y(y) ، تولید کرنا ہو تو یہ طریقہ ہے: اپنے فرضی تصادفی عدد مولد سے معیاری وقفہ (0,1) میں عدد x حاصل کرو، اور

y = F_Y^{-1}(x)

مطلوبہ عدد ہے، جس کی توزیع احتمال \ F_Y(y) ہو گی (یہاں \ F_Y(.) دالہ کا مقلوب دالہ F_Y^{-1}(.) ہے۔)[2] [3]

اور دیکھو[ترمیم]

حوالہ جات[ترمیم]

  1. ^ ACM Transactions on Modeling and Computer Simulations, 1998 "Mersenne Twister: A 623 dimensionally equidistributed uniform pseudorandom number generator"
  2. ^ Numerical Recipes دیکھو تفصیل
  3. ^ روئے خط کتاب, "Luc Devroye: Non-Uniform Random Variate Generation"

بیرونی روابط[ترمیم]

E=mc2     اردو ویکیپیڈیا پر ریاضی مساوات کو بائیں سے دائیں LTR پڑھیٔے     ریاضی علامات

Pseudorandom number generator