दिलचस्प पोस्ट
जावास्क्रिप्ट में पाठ को द्विआधारी कोड में कैसे रूपांतरित करना है? मोंगोज हमेशा एक खाली सरणी नोडजेएस लौट रहा था क्या जियोलोकेशन जावास्क्रिप्ट के साथ निकाल दिया गया है या नहीं यह जांचने का एक तरीका है? ड्रॉप-डाउन मेनू जो शुद्ध सीएसएस के साथ ऊपर / ऊपर की ओर खुलता है WPF में स्टैटिक रिसोर्स और डायनेमिक रिसोर्स के बीच अंतर क्या है? माता पिता के स्कोप वैरिएबल को अपडेट करें असमर्थित प्रमुख.मोनोर संस्करण 52.0 एंड्रॉइड स्टूडियो में रेंडरिंग करते समय सी # – एक WPF अनुप्रयोग में उपयोगकर्ता सेटिंग्स को बचाने के लिए दृष्टिकोण? एसक्यूएल ROWNUM कैसे एक विशिष्ट श्रेणी के बीच पंक्तियों को वापस करने के लिए SLF4J का उपयोग कर लॉगबैक करने के लिए java.util.logging.Logger (JUL) भेजें / रीडायर / मार्ग भेजें। मैं निर्दिष्ट POST पैरामीटर के साथ एंड्रॉइड ब्राउज़र कैसे खोल सकता / सकती हूं? लम्बाई की सूची में आदिम लम्बे की एक सरणी परिवर्तित करें सी ++ फ़ंक्टर्स – और उनका उपयोग रूबी में प्रारंभिक रूपरेखा को ओवरलोड करने का एक तरीका है? डालें या हटाएं के बाद ओरेकल ट्रिगर

एक यादृच्छिक संख्या जनरेटर का उपयोग करते समय लोग कहते हैं कि मॉड्यूलो पूर्वाग्रह क्यों है?

मैंने इस प्रश्न को बहुत कुछ पूछा है, लेकिन कभी भी इसका सही कंक्रीट जवाब नहीं देखा है। इसलिए मैं यहां पोस्ट करने जा रहा हूं जो उम्मीद है कि लोगों को यह समझने में मदद मिलेगी कि सी ++ में rand() जैसे एक यादृच्छिक संख्या जनरेटर का उपयोग करते समय वास्तव में "मॉड्यूलो पूर्वाग्रह" क्यों है?

Solutions Collecting From Web of "एक यादृच्छिक संख्या जनरेटर का उपयोग करते समय लोग कहते हैं कि मॉड्यूलो पूर्वाग्रह क्यों है?"

तो rand() एक छद्म-यादृच्छिक संख्या जनरेटर है, जो 0 और RAND_MAX बीच एक प्राकृतिक संख्या चुनता है, जो कि cstdlib में निरंतर परिभाषित है ( rand() पर सामान्य अवलोकन के लिए यह लेख देखें)।

अब क्या होता है यदि आप 0 और 2 के बीच एक यादृच्छिक संख्या उत्पन्न करना चाहते हैं? स्पष्टीकरण के लिए, RAND_MAX लें कि RAND_MAX 10 है और मैं rand()%3 कॉल करके 0 और 2 के बीच एक यादृच्छिक संख्या उत्पन्न करने का निर्णय लेता हूं। हालांकि, rand()%3 समानता के साथ 0 और 2 के बीच की संख्या उत्पन्न नहीं करता है!

जब rand() 0, 3, 6 या 9, rand()%3 == 0 इसलिए, पी (0) = 4/11

जब rand() 1, 4, 7 या 10, rand()%3 == 1 इसलिए, पी (1) = 4/11

जब rand() 2, 5 या 8, rand()%3 == 2 इसलिए, पी (2) = 3/11

यह समान संभावना के साथ 0 और 2 के बीच की संख्या उत्पन्न नहीं करता है। बेशक छोटी सी श्रेणियों के लिए यह सबसे बड़ा मुद्दा नहीं हो सकता है, लेकिन एक बड़ी रेंज के लिए यह वितरण को तिरछा कर सकता है, छोटी संख्याओं को द्विगुणित कर सकता है।

तो जब rand()%n बराबर संभावना के साथ संख्याओं की श्रेणी 0 से n-1 तक लौटाता है? जब RAND_MAX%n == n - 1 इस मामले में, हमारे पहले धारणा rand() के साथ, 0 और RAND_MAX के बराबर संभावना के साथ एक नंबर RAND_MAX है, n के मॉड्यूलो वर्गों को समान रूप से वितरित किया जाएगा।

तो हम इस समस्या को कैसे हल करते हैं? एक क्रूड तरीके से यादृच्छिक संख्या उत्पन्न करना है जब तक कि आप अपनी वांछित सीमा में कोई संख्या न प्राप्त करें:

 int x; do { x = rand(); } while (x >= n); 

लेकिन यह n कम मूल्यों के लिए अक्षम है, क्योंकि आपके पास केवल आपकी श्रेणी में एक मान प्राप्त करने का एक n/RAND_MAX मौका है, और आपको rand() पर RAND_MAX/n rand() लिए RAND_MAX/n कॉल करने की आवश्यकता होगी।

एक अधिक कुशल फार्मूला दृष्टिकोण, कुछ बड़ी रेंज को RAND_MAX - RAND_MAX % n द्वारा विभाजित करता है, जैसे कि RAND_MAX - RAND_MAX % n , रैंडम संख्याओं को सृजित करते रहें, जब तक आप सीमा में नहीं आते हैं, और तब मॉड्यूलस लेते हैं:

 int x; do { x = rand(); } while (x >= (RAND_MAX - RAND_MAX % n)); x %= n; 

n के छोटे मूल्यों के लिए, यह शायद ही कभी एक से अधिक कॉल को rand() आवश्यकता होगी।


वर्क्स का उद्धरण और आगे पढ़ना:

  • CPlusPlus संदर्भ

  • अनन्त रूप से विवादित


यादृच्छिक चयन करना पूर्वाग्रह को दूर करने का एक अच्छा तरीका है।

अद्यतन करें

हम कोड को तेज़ बना सकते हैं यदि हम एक्स में विभाजित वर्ग में एक्स के लिए खोज करते हैं।

 // Assumptions // rand() in [0, RAND_MAX] // n in (0, RAND_MAX] int x = rand(); // Keep searching for an x in a range divisible by n while (x >= RAND_MAX - (RAND_MAX % n)) { x = rand(); } x %= n; 

उपर्युक्त लूप बहुत तेजी से होना चाहिए, औसत पर 1 चलना कहना।

@ उपयोगकर्ता 1413793 समस्या के बारे में सही है। मैं एक बात करने के अलावा, उस पर भी चर्चा नहीं कर रहा हूं: हाँ, RAND_MAX छोटे मूल्यों के लिए और RAND_MAX बड़े मूल्यों के लिए, मॉड्यूलो पूर्वाग्रह बहुत छोटा हो सकता है लेकिन पूर्वाग्रह उत्प्रेरण पैटर्न का उपयोग करने का मतलब है कि हर बार जब आप एक यादृच्छिक संख्या की गणना करते हैं और विभिन्न मामलों के लिए अलग-अलग पैटर्न चुनते हैं तो आपको पक्षपात पर विचार करना चाहिए। और अगर आप गलत विकल्प बनाते हैं, तो इसकी शुरुआत की जाने वाली कीड़े सूक्ष्म हैं और इकाई परीक्षण के लिए लगभग असंभव हैं। उचित उपकरण (जैसे कि arc4random_uniform ) का उपयोग करने के मुकाबले, यह अतिरिक्त काम है, कम काम नहीं है अधिक काम करना और बदतर समाधान प्राप्त करना बेहद भयानक इंजीनियरिंग है, खासकर जब ऐसा करते समय हर प्लेटफॉर्म पर हर बार आसान हो जाता है

दुर्भाग्य से, समाधान के कार्यान्वयन सभी गलत या कम कुशल हैं जितने वे होना चाहिए। (प्रत्येक समाधान में समस्याएं समझा जाने वाली विभिन्न टिप्पणियां हैं, लेकिन समाधानों में से कोई भी उनका समाधान करने के लिए तय नहीं किया गया है।) यह आकस्मिक उत्तर-साधक को भ्रमित करने की संभावना है, इसलिए मैं यहां एक ज्ञात-अच्छा कार्यान्वयन प्रदान कर रहा हूं।

दोबारा, सबसे अच्छा समाधान सिर्फ प्लेटफॉर्म पर arc4random_uniform का इस्तेमाल करना है, जो आपके प्लेटफ़ॉर्म (जैसे जावा पर Random.nextInt । यह आपके लिए कोई भी कोड लागत पर सही काम नहीं करेगा। यह लगभग हमेशा सही कॉल करना है।

यदि आपके पास arc4random_uniform नहीं है, तो आप ओपनसोर्स की शक्ति का उपयोग करके देख सकते हैं कि यह कैसे व्यापक श्रेणी के ar4random (इस मामले में ar4random ऊपर लागू किया गया है, लेकिन एक समान दृष्टिकोण अन्य आरएनजी के शीर्ष पर काम कर सकता है) ।

यहां OpenBSD कार्यान्वयन है :

 /* * Calculate a uniformly distributed random number less than upper_bound * avoiding "modulo bias". * * Uniformity is achieved by generating new random numbers until the one * returned is outside the range [0, 2**32 % upper_bound). This * guarantees the selected random number will be inside * [2**32 % upper_bound, 2**32) which maps back to [0, upper_bound) * after reduction modulo upper_bound. */ u_int32_t arc4random_uniform(u_int32_t upper_bound) { u_int32_t r, min; if (upper_bound < 2) return 0; /* 2**32 % x == (2**32 - x) % x */ min = -upper_bound % upper_bound; /* * This could theoretically loop forever but each retry has * p > 0.5 (worst case, usually far better) of selecting a * number inside the range we need, so it should rarely need * to re-roll. */ for (;;) { r = arc4random(); if (r >= min) break; } return r % upper_bound; } 

यह उन लोगों के लिए नवीनतम कोड टिप्पणी पर ध्यान देने योग्य है, जिनके लिए इसी प्रकार की चीजें लागू करने की आवश्यकता है:

2**32 % upper_bound'' as ऊपरी_बाउंड 2**32 % upper_bound'' as -upper_bound% upper_bound 2**32 % upper_bound'' as गणना करने के लिए arc4random_uniform () बदलें कोड को सरल बनाता है और इसे आईएलपी 32 और एलपी 64 आर्किटेक्चर दोनों पर समान बना देता है, और 64-बिट शेष के बजाय 32-बिट शेष का उपयोग करके एलपी 64 आर्किटेक्चर पर थोड़ी तेज़ बनाता है।

जार्डन वर्वर द्वारा टेक @ ओके डेराआड पर नियुक्त किया गया; डीजेएम या ओटो से कोई आपत्ति नहीं है

जावा कार्यान्वयन भी आसानी से खोजा जा सकता है (पिछला लिंक देखें):

 public int nextInt(int n) { if (n <= 0) throw new IllegalArgumentException("n must be positive"); if ((n & -n) == n) // ie, n is a power of 2 return (int)((n * (long)next(31)) >> 31); int bits, val; do { bits = next(31); val = bits % n; } while (bits - val + (n-1) < 0); return val; } 

परिभाषा

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

यह पूर्वाग्रह कंप्यूटिंग से बचने के लिए विशेष रूप से कठिन है, जहां संख्याएं बिट्स के तार के रूप में प्रदर्शित की जाती हैं: 0 एस और 1 एस यादृच्छिकता के सचमुच यादृच्छिक सूत्रों का पता लगाना भी बहुत मुश्किल है, लेकिन इस चर्चा के दायरे से परे है। इस उत्तर के शेष के लिए मान लें कि वास्तव में यादृच्छिक बिट्स का असीमित स्रोत मौजूद है।

समस्या उदाहरण

आइए ये यादृच्छिक बिट्स का उपयोग करके एक डाय रोल (0 से 5) का अनुकरण करने पर विचार करें। 6 संभावनाएं हैं, इसलिए हमें संख्या 6 का प्रतिनिधित्व करने के लिए पर्याप्त बिट की आवश्यकता है, जो 3 बिट्स है। दुर्भाग्यवश, 3 यादृच्छिक बिट्स में 8 संभावित परिणाम उत्पन्न होते हैं:

 000 = 0, 001 = 1, 010 = 2, 011 = 3 100 = 4, 101 = 5, 110 = 6, 111 = 7 

हम मूल्य 6 मॉड्यूल 6 लेते हुए परिणाम के आकार को कम कर सकते हैं, हालांकि यह मॉडुलो बायस समस्या प्रस्तुत करता है: 110 पैदावार एक 0 और 111 पैदावार 1. यह मर जाता है।

संभावित समाधान

दृष्टिकोण 0:

यादृच्छिक बिट पर भरोसा करने के बजाय, सिद्धांत रूप में एक छोटी सी सेना को हर दिन पासा को रोल करने और एक डेटाबेस में परिणाम रिकॉर्ड करने के लिए किराए पर ले सकता है, और फिर प्रत्येक परिणाम का केवल एक बार उपयोग करें ऐसा लगता है कि यह व्यावहारिक रूप से व्यावहारिक है, और संभावना से अधिक होने के बावजूद वास्तव में यादृच्छिक परिणाम नहीं मिलेगा (यमक इरादा)।

दृष्टिकोण 1:

मापांक का उपयोग करने के बजाय, एक सरल लेकिन गणितीय रूप से सही समाधान उन परिणामों को त्यागने के लिए है जो 110 और 111 उत्पन्न करते हैं और बस तीन नए बिट्स के साथ पुनः प्रयास करें। दुर्भाग्य से, इसका मतलब है कि प्रत्येक रोल पर 25% मौका होता है, जिसमें पुन: रोल की आवश्यकता होगी, जिसमें से प्रत्येक को फिर से रोल करना होगा यह सभी के लिए स्पष्ट रूप से अव्यावहारिक है, लेकिन उपयोगों का सबसे तुच्छ है

दृष्टिकोण 2:

अधिक बिट्स का उपयोग करें: 3 बिट्स के बजाय, उपयोग करें 4. यह उपज 16 संभावित परिणाम। बेशक, किसी भी समय फिर से रोलिंग परिणाम 5 से अधिक है जिससे चीजें खराब हो जाती हैं (10/16 = 62.5%) ताकि अकेले मदद नहीं करेगा

ध्यान दें कि 2 * 6 = 12 <16, तो हम सुरक्षित रूप से 12 से भी कम का कोई भी परिणाम निकाल सकते हैं और मॉड्यूल 6 को कम करके परिणामों को समान रूप से वितरित कर सकते हैं। अन्य 4 परिणामों को त्याग दिया जाना चाहिए, और फिर पिछले दृष्टिकोण के रूप में फिर से लुढ़का होना चाहिए

सबसे अच्छा लगता है पहले, लेकिन चलो गणित की जांच करें:

 4 discarded results / 16 possibilities = 25% 

इस मामले में, 1 अतिरिक्त बिट बिल्कुल मदद नहीं किया !

इसका नतीजा दुर्भाग्यपूर्ण है, लेकिन हम 5 बिट के साथ फिर से प्रयास करें:

 32 % 6 = 2 discarded results; and 2 discarded results / 32 possibilities = 6.25% 

कई व्यावहारिक मामलों में एक निश्चित सुधार, लेकिन पर्याप्त नहीं। अच्छी खबर यह है कि, अधिक बिट्स को जोड़ना और त्यागने और पुन: रोल करने की ज़रूरत के अवसरों में वृद्धि नहीं होगी । यह केवल पासा के लिए नहीं है, लेकिन सभी मामलों में।

जैसा कि दिखाया गया है , 1 अतिरिक्त बिट जोड़ने से कुछ भी बदल नहीं सकता है। वास्तव में अगर हम अपने रोल को 6 बिट तक बढ़ा देते हैं, तो संभावना 6.25% रहती है।

यह 2 अतिरिक्त प्रश्न पूछता है:

  1. यदि हम पर्याप्त बिट जोड़ते हैं, तो क्या कोई गारंटी है कि एक त्याग की संभावना कम हो जाएगी?
  2. सामान्य मामले में कितने बिट पर्याप्त हैं ?

सामान्य समाधान

शुक्र है कि पहले प्रश्न का उत्तर हां है। 6 के साथ समस्या यह है कि 2 ^ x mod 6 2 और 4 के बीच फ़्लिप करता है जो संयोग एक दूसरे से 2 के एक गुण होते हैं, ताकि एक एक्स के लिए> 1,

 [2^x mod 6] / 2^x == [2^(x+1) mod 6] / 2^(x+1) 

इस प्रकार 6 नियम के बजाय एक अपवाद है बड़े moduli कि संभवतः 2 की लगातार शक्तियों को एक ही तरह से प्राप्त करने के लिए संभव है, लेकिन अंततः यह चारों ओर लपेटो, और एक त्याग की संभावना कम हो जाएगा

आगे के सबूत की पेशकश के बिना, आम तौर पर आवश्यक बिट्स की संख्या की संख्या का उपयोग करते हुए सामान्य रूप से एक छोटे, आमतौर पर तुच्छ, एक त्यागने का मौका प्रदान करेगा।

अवधारणा के सुबूत

यहां एक उदाहरण कार्यक्रम है जो ओपनएसएसएल के लिब्रेरीपो का इस्तेमाल करता है ताकि यादृच्छिक बाइट्स की आपूर्ति हो सके। संकलन करते समय, लाइब्रेरी से -lcrypto साथ लिंक करना सुनिश्चित करें जो कि सबसे ज्यादा उपलब्ध होना चाहिए।

 #include <iostream> #include <assert.h> #include <limits> #include <openssl/rand.h> volatile uint32_t dummy; uint64_t discardCount; uint32_t uniformRandomUint32(uint32_t upperBound) { assert(RAND_status() == 1); uint64_t discard = (std::numeric_limits<uint64_t>::max() - upperBound) % upperBound; uint64_t randomPool = RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool)); while(randomPool > (std::numeric_limits<uint64_t>::max() - discard)) { RAND_bytes((uint8_t*)(&randomPool), sizeof(randomPool)); ++discardCount; } return randomPool % upperBound; } int main() { discardCount = 0; const uint32_t MODULUS = (1ul << 31)-1; const uint32_t ROLLS = 10000000; for(uint32_t i = 0; i < ROLLS; ++i) { dummy = uniformRandomUint32(MODULUS); } std::cout << "Discard count = " << discardCount << std::endl; } 

मैं MODULUS और ROLLS मूल्यों के साथ खेलने के लिए प्रोत्साहित करता हूं कि यह देखने के लिए कि वास्तव में अधिकांश परिस्थितियों में कितने पुन: रोल होते हैं एक संदिग्ध व्यक्ति, गणना मूल्य को सहेज सकते हैं और यह सत्यापित कर सकते हैं कि वितरण सामान्य दिखाई देता है।

मॉड्यूलो के उपयोग के साथ दो सामान्य शिकायतें हैं

  • एक सभी जनरेटर के लिए वैध है यह एक सीमा के मामले में देखना आसान है। यदि आपके जनरेटर के पास आरएआईटीएएमएक्स है जो 2 है (जो सी मानक के अनुरूप नहीं है) और आप चाहते हैं कि केवल 0 या 1 को वैल्यू के रूप में इस्तेमाल किया जाए, तो मॉड्यूलो का उपयोग करके बार-बार 2 बार जनरेटर उत्पन्न होगा (जब जनरेटर 0 और 2 उत्पन्न करेगा)। उत्पन्न 1 (जब जनरेटर 1 उत्पन्न करता है) ध्यान दें कि जैसे ही आप मूल्यों को नहीं छोड़ते हैं, वहीं जो भी मानचित्रण आप जनरेटर मूल्यों से वांछित एक से उपयोग कर रहे हैं, एक बार दो बार के रूप में अक्सर दूसरे के रूप में होता है।

  • कुछ प्रकार के जनरेटर में उनके कम महत्वपूर्ण बिट्स को कम से कम यादृच्छिक होता है, कम से कम उनके पैरामीटर के लिए, लेकिन दुर्भाग्य से उन पैरामीटर में अन्य रोचक विशेषताएँ होती हैं (जैसे कि 2 की शक्ति से आरएआईटीएमएएक्स एक कम है)। समस्या अच्छी तरह से ज्ञात है और लंबे समय से पुस्तकालय क्रियान्वयन संभवतः समस्या से बचने के लिए (उदाहरण के लिए सी मानक में नमूना रैंड कार्यान्वयन इस तरह के जनरेटर का उपयोग करता है, लेकिन 16 कम महत्वपूर्ण बिट ड्रॉप), लेकिन कुछ लोगों के बारे में शिकायत करना पसंद है कि और तुम बुरी किस्मत हो सकती है

जैसे कुछ का उपयोग करना

 int alea(int n){ assert (0 < n && n <= RAND_MAX); int partSize = n == RAND_MAX ? 1 : 1 + (RAND_MAX-n)/(n+1); int maxUsefull = partSize * n + (partSize-1); int draw; do { draw = rand(); } while (draw > maxUsefull); return draw/partSize; } 

0 और n के बीच एक यादृच्छिक संख्या उत्पन्न करने के लिए दोनों समस्याओं से बचना होगा (और यह RAND_MAX == INT_MAX के साथ अतिप्रवाह से बचा जाता है)

बीटीडब्लू, सी +11 रेड () की तुलना में कमी और अन्य जनरेटर के लिए मानक तरीके पेश करते हैं

जैसा कि स्वीकृत उत्तर इंगित करता है, "मॉड्यूलो पूर्वाग्रह" की जड़ें RAND_MAX के कम मूल्य में हैं। वह RAND_MAX (10) का एक बहुत ही कम मूल्य का उपयोग करता है यह दर्शाता है कि यदि RAND_MAX 10 थे, तो आपने 0 से 2 के बीच संख्या उत्पन्न करने का प्रयास किया, निम्न परिणामों का परिणाम होगा:

 rand() % 3 // if RAND_MAX were only 10, gives output of rand() | rand()%3 0 | 0 1 | 1 2 | 2 3 | 0 4 | 1 5 | 2 6 | 0 7 | 1 8 | 2 9 | 0 

इसलिए 0 के 4 आउटपुट (4/10 मौके) और 1 और 2 के 3 आउटपुट (3/10 संभावनाएं प्रत्येक) हैं

तो यह पक्षपाती है कम संख्या में आने का बेहतर मौका है।

लेकिन यह केवल इतना स्पष्ट RAND_MAX है जब RAND_MAX छोटा होता है या अधिक विशेष रूप से, जब आपके द्वारा RAND_MAX संख्या RAND_MAX की तुलना में बड़ी है।

पाशन की तुलना में एक बहुत अच्छा समाधान (जो अति सूक्ष्म है और इसका सुझाव भी नहीं दिया जाना चाहिए) एक बहुत बड़ी आउटपुट श्रेणी के साथ एक पीआरएनजी का उपयोग करना है मर्सन ट्विस्टर एल्गोरिथम का अधिकतम उत्पादन 4,294,967,295 है। जैसे कि MersenneTwister::genrand_int32() % 10 सभी intents और उद्देश्यों के लिए, समान रूप से वितरित किया जाएगा और मॉड्यूलो पूर्वाग्रह प्रभाव सब गायब हो जाएगा।

एक RAND_MAX 3 मान के साथ (वास्तव में यह उस से बहुत अधिक होना चाहिए, लेकिन पूर्वाग्रह अभी भी मौजूद होगा) यह इन गणनाओं से समझ में आता है कि पूर्वाग्रह है:

1 % 2 = 1 2 % 2 = 0 3 % 2 = 1 random_between(1, 3) % 2 = more likely a 1

इस स्थिति में, % 2 वह है जो आपको 0 और 1 बीच एक यादृच्छिक संख्या चाहते हैं, तब आप क्या नहीं करना चाहिए। आप 0 और 2 बीच यादृच्छिक संख्या प्राप्त कर सकते हैं हालांकि, हालांकि, इस मामले में: RAND_MAX 3 का एक RAND_MAX है

एक अन्य विधि

बहुत आसान है लेकिन अन्य उत्तर जोड़ने के लिए, यहां मेरा समाधान है कि 0 और n - 1 बीच यादृच्छिक संख्या प्राप्त करें, इसलिए n भिन्न संभावनाएं, बिना पूर्वाग्रह के।

  • संभावनाओं की संख्या को सांकेतिक शब्दों में बदलना करने के लिए आवश्यक बिट्स (बाइट्स नहीं) की संख्या आपके लिए यादृच्छिक डेटा की बिट्स की संख्या है
  • यादृच्छिक बिट्स से संख्या को सांकेतिक शब्दों में बदलना
  • अगर यह संख्या >= n , पुनरारंभ करें (कोई मॉड्यूल नहीं है)।

वास्तव में यादृच्छिक डेटा प्राप्त करना आसान नहीं है, इसलिए अधिक बिट्स की आवश्यकता से अधिक उपयोग क्यों करें

नीचे स्मालटाक में एक उदाहरण है, छद्म यादृच्छिक संख्या जनरेटर से बिट्स के कैश का उपयोग करते हुए। मैं कोई सुरक्षा विशेषज्ञ नहीं हूं इसलिए अपने जोखिम पर उपयोग करें I

 next: n | bitSize r from to | n < 0 ifTrue: [^0 - (self next: 0 - n)]. n = 0 ifTrue: [^nil]. n = 1 ifTrue: [^0]. cache isNil ifTrue: [cache := OrderedCollection new]. cache size < (self randmax highBit) ifTrue: [ Security.DSSRandom default next asByteArray do: [ :byte | (1 to: 8) do: [ :i | cache add: (byte bitAt: i)] ] ]. r := 0. bitSize := n highBit. to := cache size. from := to - bitSize + 1. (from to: to) do: [ :i | r := r bitAt: i - from + 1 put: (cache at: i) ]. cache removeFrom: from to: to. r >= n ifTrue: [^self next: n]. ^r 

मार्क का समाधान (स्वीकृत समाधान) लगभग संपूर्ण है

 int x; do { x = rand(); } while (x >= (RAND_MAX - RAND_MAX % n)); x %= n; 

25 मार्च को 23:16 को संपादित किया गया

मार्क अमेरी 39k21170211

हालांकि, इसकी एक चेतावनी है जो सभी परिदृश्यों में 1 वैध सेट को छोड़ देता है जहां RAND_MAX (आरएम) का मान एन के एक से अधिक का 1 कम है।

यानी, जब मूल्यों की संख्या जिसे अमान्य (I) के रूप में खारिज किया जाएगा N के बराबर है, तो वे वास्तव में एक मान्य सेट हैं, अमान्य सेट नहीं हैं

ईजी:

 RM = 255 N = 4 Discard X => RM - RM % N When X => 252, Discarded values = 252, 253, 254, 255 Number of discarded Values (I) = RM % N + 1 

जैसा कि आप उदाहरण में देखे गए मानों की संख्या = 4 देख सकते हैं, जब छोड़े गए मानों की संख्या = N तब सेट उपयोग के लिए मान्य है।

यदि हम डी के रूप में एन और आरएम के बीच अंतर का वर्णन करते हैं, अर्थात्:

 D = (RM - N) 

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

ईजी:

 RM=255 , N=2 Then: D = 253, Lost percentage = 0.78125% RM=255 , N=4 Then: D = 251, Lost percentage = 1.5625% RM=255 , N=8 Then: D = 247, Lost percentage = 3.125% RM=255 , N=16 Then: D = 239, Lost percentage = 6.25% RM=255 , N=32 Then: D = 223, Lost percentage = 12.5% RM=255 , N=64 Then: D = 191, Lost percentage = 25% RM=255 , N= 128 Then D = 127, Lost percentage = 50% 

इसे नकारने के लिए हम एक साधारण संशोधन कर सकते हैं जैसा कि यहां दिखाया गया है:

  int x; do { x = rand(); } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ); x %= n; 

यह सूत्र का अधिक सामान्य संस्करण प्रदान करता है जो आपके अधिकतम मूल्यों को परिभाषित करने के लिए मापांक का उपयोग करने की अतिरिक्त विशेषताओं के लिए खाता है।

RAND_MAX के लिए एक छोटा सा मान का उपयोग करने के उदाहरण जो एन के गुणात्मक है

मार्क का मूल संस्करण:

 RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3. When X >= (RAND_MAX - ( RAND_MAX % n ) ) When X >= 2 the value will be discarded, even though the set is valid. 

संशोधित संस्करण:

 RAND_MAX = 3, n = 2, Values in RAND_MAX = 0,1,2,3, Valid Sets = 0,1 and 2,3. When X > (RAND_MAX - ( ( RAND_MAX % n ) + 1 ) % n ) When X > 3 the value would be discarded, but this is not a vlue in the set RAND_MAX so there will be no discard. 

इसके अतिरिक्त, ऐसे मामले में जहां एन आरए आईडीएएमएक्स में मूल्यों की संख्या होनी चाहिए; इस मामले में, आप N = RAND_MAX +1 सेट कर सकते हैं, जब तक कि RAND_MAX = INT_MAX नहीं।

लूप-वार आप केवल एन = 1 का उपयोग कर सकते हैं, और एक्स के किसी भी मान को स्वीकार किया जाएगा, हालांकि, और अपने अंतिम गुणक के लिए IF स्टेटमेंट डाल दिया जाएगा। लेकिन शायद आपके पास एक ऐसा कोड है जो 1 को वापस करने का वैध कारण हो सकता है जब फ़ंक्शन को n = 1 से कहा जाता है …

तो यह 0 का उपयोग करना बेहतर हो सकता है, जो आम तौर पर एक div 0 त्रुटि प्रदान करेगा, जब आप चाहते हैं कि n = RAND_MAX + 1

अर्थात:

 int x; if n != 0 { do { x = rand(); } while (x > (RAND_MAX - RAND_MAX % n)); x %= n; } else { x = rand(); } 

इन दोनों समाधानों के समाधान के बिना अनिवार्य रूप से छोड़ दिए गए वैध परिणामों के साथ समस्या हल हो जाएगी जो आरएम + 1 n का उत्पाद होगा।

दूसरा संस्करण किनारे की परिदृश्य को भी कवर करता है जब आपको RAND_MAX में निहित मूल्यों के कुल संभव सेट के बराबर n की आवश्यकता होती है।

दोनों में संशोधित दृष्टिकोण समान है और वैध यादृच्छिक संख्या प्रदान करने और त्याग किए गए मानों को कम करने की आवश्यकता के लिए अधिक सामान्य समाधान की अनुमति देता है।

दोहराना:

बुनियादी सामान्य समाधान जो चिह्न का उदाहरण प्रदान करता है:

  int x; do { x = rand(); } while (x > (RAND_MAX - ( ( ( RAND_MAX % n ) + 1 ) % n) ); x %= n; 

विस्तारित सामान्य समाधान जो एक अतिरिक्त परिदृश्य को RAND_MAX + 1 = n की अनुमति देता है:

 int x; if n != 0 { do { x = rand(); } while (x > (RAND_MAX - RAND_MAX % n)); x %= n; } else { x = rand(); } 

मैंने अभी वॉन न्यूमैन के निष्पक्ष सिक्का फ्लिप विधि के लिए एक कोड लिखा है, जिसे सैद्धांतिक रूप से यादृच्छिक संख्या पीढ़ी प्रक्रिया में किसी भी पूर्वाग्रह को समाप्त करना चाहिए। अधिक जानकारी ( http://en.wikipedia.org/wiki/Fair_coin ) पर पाई जा सकती है

 int unbiased_random_bit() { int x1, x2, prev; prev = 2; x1 = rand() % 2; x2 = rand() % 2; for (;; x1 = rand() % 2, x2 = rand() % 2) { if (x1 ^ x2) // 01 -> 1, or 10 -> 0. { return x2; } else if (x1 & x2) { if (!prev) // 0011 return 1; else prev = 1; // 1111 -> continue, bias unresolved } else { if (prev == 1)// 1100 return 0; else // 0000 -> continue, bias unresolved prev = 0; } } }