Неліктен C ++ rand () дәл осындай тәртіптегі сандар сандарын шығарады?

C/C ++-те жазылған кішігірім бағдарламада мен rand функциясымен проблемаға кезігемін және мүмкін тұқым:

Мен түрлі тапсырыстарды, яғни әр түрлі логарифмдік мәндермен (2-база) кездейсоқ сандар тізбегін шығарғым келеді. Дегенмен, барлық сандар бірдей тәртіпті құрайды, яғни 2 ^ 25 және 2 ^ 30 арасында ауытқып тұрады.

rand() Unix уақытымен себілген болса, ол қазір салыстырмалы үлкен сан болып табылады? Мен не ұмытып жатырмын? Мен rand() main() басында тек бір рет егемін.

146
rand-тің іске асуы анықталған, сол себепті әлдеқайда жоғары сапалы және анықталған алгоритмдері бар күшейтуді қолданыңыз.
қосылды автор Dov, көзі
FWIW осылайша, C немесе C ++? Егер C/C ++ арқылы сіз C ++-ды қолдансаңыз және C-ны еске түсіру жай ғана кездейсоқ болса, мүмкін, бұл en.cppreference.com/w/cpp/numeric/random/binomial_distributi‌ on көмектесе алады.
қосылды автор R. Martinho Fernandes, көзі
Сіз srand (уақыт (NULL)) қолдандыңыз ба; кездейсоқ тұқымдарды инициализациялау
қосылды автор One Man Crew, көзі
«Кездейсоқ» дегеніміз әрбір элементтің таңдалу ықтималдығы бар екенін білдіреді (немесе әрбір элементтің бір рет пайда болғанда сол нәрсе болып табылатын халықтағы элементтердің үлесіне тең ықтималдығы бар). Егер дәйектегі ешбір сан қайталанбайтын болса, онда ол кездейсоқ толығымен керісінше, себебі сіз нөмірдің пайда болған сәттен бастап, жоқ болады цикл аяқталды. Әрине, кез-келген PRNG тұқымды таңдағаннан кейін детерминирлік болады, бірақ бұл сіз -нен нәтиже туралы бірдеңе болжай алатын өте өзгеше нәрсе.
қосылды автор Paul Griffiths, көзі
Көптеген қарапайым кездейсоқ санды іске асыруда, сан қайталанған кезде, келесі дәйектілік қайталанады, себебі формула тек ағымдағы мәнге тәуелді болады және генератор тек бір тұқым ұстайды. Сондықтан, үлкен кезең (немесе бүкіл кеңістіктің толық мерзімі) пайдалы деп саналады. Дегенмен, rand генераторының ішкі кезеңі 32 биттен әлдеқайда үлкен болуы мүмкін, сондықтан 32-битке қайта салыстыру кезінде ішкі көріністе қайталанбайтын болса, көшірмелер болуы мүмкін.
қосылды автор Stephen Chung, көзі
@ChrisGregg Әрине, бұл кездейсоқ емес. Сондықтан, ол жалған кездейсоқ сандар генераторы деп аталады.
қосылды автор doug65536, көзі
Мен көрген көптеген қосымшалар бірдей біркелкі таратуды қайтарады, онда ешқандай нөмір қайталанбайды және әр нөмір қайтарылады. Мен rand (1) 32 массивімен (4Гб) тексеріп, rand() қоңырауының бұл мән бұрын қайтарылмағанын және әр нөмірдің қайтарылғандығын тексерді. Кезектілік мінез-құлқы әр түрлі болмайды. Кез келген ұрықтан бастап, кездейсоқ сандардың кезектілігі әрқашан бірдей болады.
қосылды автор doug65536, көзі
@ChrisGregg Не? Мен мұны кездейсоқ емес, өйткені «псевдо» деп атадым. Псевдом дегеніміз - «жалған», «болмайтын нәрсені дәлелдеу». Сіз құмар ойындар үшін rand() қолдануға болатын деп ойладыңыз, енді кенеттен кездейсоқ сандар теориясы бойынша сарапшы болдыңыз ба? Кәне.
қосылды автор doug65536, көзі
@ doug65536 іс жүзінде шынымен жақсы нүктені көтереді - PRNG қайталаудан аулақ болу қабілеті - оның кезеңділігі ғана жақсы. Бұл туралы кейбір мәліметтерді Wikipedia мақаласын қараңыз.
қосылды автор GalacticCowboy, көзі
@ doug65536 «... онда ешқандай нөмір қайталанбайды» - бұл кездейсоқ емес! Мен rand() дисктері кез-келген нөмір қайтарылмағанша екі рет екі рет қайтпаған болса, зейнеткерлікке шыққан кезде зейнеткерлікке шықтым.
қосылды автор Chris Gregg, көзі
@ doug65536 Жоқ, бұл псевдо кездейсоқ сандар генераторы деп аталмайды. «Псевдос кездейсоқ сандар генераторы» атауын қайталаудан бұрын әрбір комбинациямен ешқандай байланысы жоқ және барлық алгоритмдік құралдар арқылы кездейсоқ мінез-құлықты жақындатуға ешқандай қатысы жоқ.
қосылды автор Chris Gregg, көзі
@GalacticCowboy Жеке сандарды қайталау арқылы мерзімділікті қателеспеңіз. Википедия мақаласынан сіз: «қайталанған нәтиже кезеңнің аяқталуына қол жеткізбеді, өйткені оның ішкі жағдайы оның шығуынан үлкен болуы мүмкін». Егер PRNG мәні құндылыққа ие болса, онда барлық құндылықтар қайтарылмайынша, сол мәнді қайта шығармауға кепілдік берілді.
қосылды автор Chris Gregg, көзі
Сондай-ақ, rand() дәл жұмыс істеуі кітапхананың орындалуының егжей-тегжейі екенін ескеріңіз (мен бұған сенімдімін). Сондықтан бірдей тұқымдарды басқа компиляторға немесе тіпті стандартты кітапханалық нұсқаға ауыссаңыз да, бірдей нәтиже алуға кепілдік берілмейді. Осындай сұрақтарға байланысты, қоршаған ортаны (компилятор және стандартты кітапхана аты және нақты нұсқасының нөмірі) көрсету керек.
қосылды автор Michael Kjörling, көзі
Doug65536, ешкім де жекпе-жектер жинамайды. Олар дұрыс емес деп дұрыс айтады. Егер 1-ден 10-ға дейінгі аралықта 2-нен 10-ға дейінгі аралықта 2-ші және 7-ші раундтарға қарамастан, ПРГ-ны төмендегідей қуанышқа айналдыруға болады: 2 4 7 2 8 1 5 9 7 3. Менің ойымша, PRNG-ді сіздің iPhone-дағы шатастыруға арналған құрылғымен шатастырып жатырсыз.
қосылды автор Relaxing In Cyprus, көзі
Өкінішке орай, сіз дұрыс атқа ставка жасайсыз. Тұқым сіздің проблемаңыз болмауы керек. Сіздің проблемаңыз дұрыс күтілмеген тарату. Бейтарап бағдарламашы біркелкі бөлінген нөмірлерді қайтару үшін rand() күтуге болатындықтан, бұл мәселе болашақ оқырмандар үшін пайдалы деп ойламаймын. Міне, сондықтан төмен дауыс, бірақ ол сізді SO пайдаланудан бас тартуға мүмкіндік бермейді.
қосылды автор Emperor Orionii, көзі

9 жауаптар

2 25 және 2 30 арасында емес 1 және 2 30 арасында сандардың тек 3% ғана бар. Мәселен, бұл қалыпты көрінеді :)

2 25 /2 30 = 2 -5 = 1/32 = 0.03125 = 3.125%

476
қосылды
Көптеген бағдарламашылар үшін бұл түсінікті болар еді деп күтетін едім: 2 ^ 25-ден аз белгісі бар бүтін сан он бірінші 7 битін 0 -ге тең және әрбір бит кездейсоқ болса ...
қосылды автор BlueRaja - Danny Pflughoeft, көзі
Ия. 0-ден 1-ке дейін, 32-ге дейін (float ретінде) кездейсоқ флот жасаңыз, оның логарифмін (float) қабылдаңыз, 2-логарифммен (float) бөліп, нәтиженің экспоненталық мәнін (float) алып, бұл бүтін санға дейін. Сіз өзгермелі сандарды аласыз, бірақ логарифмдік таратуда. Менің ойымша: int (exp (log (rand() * 32)/log (2))). Бұл дегеніміз, төменгі экспоненттері бар сандар үлкен пайда болатындығын білдіреді, мысалы 2 ^ 10 <2 ^ 11 2 ^ 11 <2 ^ 12 сияқты ықтималдығы болады.
қосылды автор peterh, көзі
@BrettHale - Бағдарламашылар казинодағы демографиялық көрсеткіш деп ойлаймын.
қосылды автор EkoostikMartin, көзі
@TallaronMathias Санды нөмірлеуді >> bitshifting арқылы қарастырайық - бұл сізге кіші сандарды береді. (Немесе % модулін қолданыңыз.)
қосылды автор Sean Allred, көзі
@ BlueRaja-DannyPflughoeft - егер ықтималдықтар айқын болса, казино бизнес болмайды.
қосылды автор Brett Hale, көзі
сол мәселе: «5 теңестірілу әдісі әділетті монеталарды тастаудың ықтималдығы қандай?» :-)
қосылды автор Ant, көзі
Жазба ескерту: Кезеңдегі 2-ші базалық тәртібін жеткілікті біркелкі таратумен кездейсоқ 32-биттік бүтін сан алу үшін, сіз: rand() & ((1 << (rand ()% 33)) - 1). Мұны істеудің бірнеше жолы болуы мүмкін, бірақ мен бұл жай ғана тез арада пайда бола аламын. Іс жүзінде дұрыс мәселе.
қосылды автор gkimsey, көзі
Міне, жақсы нүкте! Жылдам жауап үшін алғыс айтамыз, 2 ^ 25 және 2 ^ 30 арасында 1 және 2 ^ 25 аралығындағы 31 есе көп сандар бар. Содан кейін бағдарламаны қайта қарастырып шығуым керек. Сұрақ жауап берді.
қосылды автор Tallaron Mathias, көзі

Ашық жасыл - 0 мен 2 аралығындағы аймақ; 25 ; қараңғы жасыл - бұл 2 25 және 2 30 арасындағы аймақ. Кенелер - бұл 2.

distribution

272
қосылды
қосылды автор Mathias Bynens, көзі

Сіз неғұрлым дәлірек болуыңыз керек: әртүрлі база логарифмінің мәндерін алғыңыз келеді, бірақ бұл үшін тарату қандай? Стандартты rand() функциялары біркелкі таратуды тудырады, сіз бұл шығымды қалаған таратылыммен байланысты квантильді функциясын қолданып түрлендіруіңіз керек.

Бөлу туралы айтатын болсаңыз, сізге қажет quantile функциясын айтуға болады.

42
қосылды
+1, тарату - бұл шешуші термин. Дистрибуция туралы ештеңе білмеген кезде кездейсоқ сандар туралы сөйлесудің шын мәнінде мағынасы жоқ. Бірыңғай формасы - маңызды оқиға болса да, ерекше оқиға. C ++ 11 стандартты кітапханасынан түрлі үлестірулерді көрсету үшін жақсы орын болуы мүмкін.
қосылды автор leftaroundabout, көзі

Егер сіз әртүрлі тәртіпте тапсырыс бергіңіз келсе, pow (2, rand ()) дегенді ғана емес көріңіз? Немесе, мүмкін, тапсырыс ретінде таңдай аласыз ретінде rand (), Гарольд ұсынды?

18
қосылды
@ Флорис: егер сіз өте үлкен диапазонда кішігірім сандарды ауқымға бөлсеңіз, сізде көпшіліктің күткені емес, мүмкін, LOTS тесіктері болады.
қосылды автор André Caron, көзі
rand() RAND_MAX дейін шығуы мүмкін болғандықтан, сіз кездейсоқ санды ауқымдауыңыз керек, сондықтан нәтиже толып кетпейді ...
қосылды автор Floris, көзі
жақсы идея, бірақ сіз өзіңіздің жауапты орнына ^ (күштік емес, логикалық хор операторы, C тілінде) көмегімен орната аласыз.
қосылды автор kriss, көзі

Негізгі (дұрыс) жауап жоғарыда берілді және қабылданды: 0-ден 9-ға дейінгі 10 нөмір, 10-нан 99-ға дейінгі сандар, 100-ден 999-ға дейін және т.б.

шамамен логарифмдік тарату арқылы бөлуді есептеудің тиімді әдісі үшін кездейсоқ санды кездейсоқ санды оң жаққа ауыстыру керек:

s = rand() & 31;//a random number between 0 and 31 inclusive, assuming RAND_MAX = 2^32-1
r = rand() >> s;//right shift

Бұл керемет емес, бірақ pow (2, rand() * scalefactor)) есептеуінен әлдеқайда жылдам. Бұл 2-фактордағы сандарға (128-ден 255-ке дейін бірдей, 256-дан 1023-ке дейінгі тығыздықтың жартысы және т.б.) бірдей болады.

Міне, сандардың 0-ден 31-ге дейінгі жиілігінің гистограммасы (1M үлгілерінде):

enter image description here

13
қосылды
Менің ойымша, бұл мәселе 0-ден 1 бит санымен ойланудан келеді ... бұл бүтін сандар мен логарифмдерді араластырған кездегі құмарлықтың түрі. Бұл жақсы жаттығу болса да, маған ойлануға бір нәрсе берді. «Алгоритміңіздің шекараларын тексер» - ешқашан ескірмейді.
қосылды автор Floris, көзі
Hmmm, бұл таңқаларлық. Мен сіздердің кодтарыңызды block [log2 (0)] ++; ) арқылы қалай түсіріп жатырсыз? NVM - Мен сізді log2 деп анықтадыңыз. Бұл туралы көбірек ойлануға тура келеді. Кері байланыс және код үлгілері үшін рақмет!
қосылды автор Floris, көзі
Жақсы - бұның бәрі кішігірім нөмірлерді көтеру болып табылады, сондықтан мен жұмыс істегеніне қуаныштымын! Мен Монте-Карло симуляциясына жүгірдім, бұл маған екі есе көбейеді - бұл журналдың таратылуына ұқсас емес. Суретке жаңартылды.
қосылды автор Floris, көзі
Менің «біркелкі таратылған» нұсқам ешқашан нөлге тең болмайды. О, жақсы.
қосылды автор Mooing Duck, көзі
Сондай-ақ, 32 битпен нәтиже жоқ екенін ескеріңіз
қосылды автор Mooing Duck, көзі
Мен сіздің кодыңыздың дұрыс емес екенін айтқым келмейді. Мүмкін, мен не істейтін едім. Нәтижелер әбден деп күтуге болмайды деп ескертуге лайық.
қосылды автор Mooing Duck, көзі
Иә, менің өлшемім менің теориямызға сәйкес . X-ось логарифмдік емес болғандықтан, сіз бұл мәселеге назар аудармайсыз.
қосылды автор Mooing Duck, көзі
rand ()> (rand() & 31)) дегенді білдіретін болсақ, сандардың 1/32 санының 32 бит болуы және сандардың 1/32 31 бит және 30/30-ға дейінгі сандар 30 бит болады. Бірақ бұл емес нәтижелерін алған кезде, сандардың 1/64 санының шамамен 32 бит болса, жартысына тең болуы керек. Менің ойым математикаңыз өлшемдеріңізге келіспегендіктен, мен оны өлшеу үшін өзімнің өлшеулерімді жасауым керек.
қосылды автор Mooing Duck, көзі
Нитпик: бұл өте аз санайды, ол күтуге болады. Нөлге жету ықтималдығы 10-ға қарағанда айтарлықтай жоғары.
қосылды автор Mooing Duck, көзі

@ C4stor тамаша нәрсе жасады. Алайда, адам үшін түсінікті неғұрлым қарапайым және түсінікті (10-база): 1-ден 10-ға дейінгі диапазонда, ~ 90% сандар 10 ^ (n-1) -дан 10 ^ n-ға дейін, ~ 99% -дан 10 ^ (n-2) -дан 10 ^ n-ға дейін. Қалағаныңызша он сантиметрді қосыңыз.

Күлкілі математика, егер сіз мұны n үшін орындасаңыз, онда 1-ден 10-ға дейін көре аласыз, 99.9999 .. Бұл әдіспен сандардың 10% = 100% -ын құрайды.

Енді код туралы кездейсоқ сандарды кездейсоқ тәртіпте 0-ден 10-ға дейін,

  1. Generate a small random number from 0 to n

  2. If you know the range that n has, generate a big random number of order 10^k where k > max{n}.

  3. Cut the longer random number to get the n digits of this big random number.

13
қосылды
Сіз толығымен түзетіңіз, бірақ жауапты түсінуге оңай болғанда, ОП өзіне 1 мен 100 аралығындағы кездейсоқ сандардың 90% неге екі сан болатындығын сұрауы керек.
қосылды автор kbelder, көзі

0 және 2 ^ 29 және 2 ^ 29 және 2 ^ 30 аралығындағы сандардың тең саны бар.

Мәселені қараудың тағы бір тәсілі: Сіз жасаған кездейсоқ санның бинарлық көрінісі, ең үлкен биттің 1/1-ге тең болуы ықтималдығы және, демек, сіз жартысы жағдайда 29 тапсырыс бересіз. Сіз қаласаңыз, 2 ^ 25-тен төмен болатын санды көресіз, бірақ бұл 5 ең жоғары биттің бәрі нөлге тең, бұл 1/32 ықтималдығы төмен. Ұзақ уақыт бойы жұмыс істесеңіз де, сіз ешқашан 15-тен төмендегі нұсқаны ешқашан көре алмасаңыз да (ықтималдығы 6 6 рет қатарынан жылжыту сияқты).

Енді сіздің тұқым туралы сұрағыңыздың бөлігі. Жоқ, ұры сандардың пайда болатын ауқымын анықтай алмайды, ол тек алғашқы, бастапқы элементін анықтайды. Rand() диапазонындағы барлық ықтимал сандардың кезектілігі ретінде (алдын ала берілген ауысу) ойлап көріңіз. Тұқым реттік сандарды қайдан бастағанын анықтайды. Міне, сондықтан сіз (жалған) кездейсоқтықты қаласаңыз, жүйелікті инициализациялау үшін ағымдағы уақытты пайдаланасыз: басталатын ұстаным біркелкі таратылмағандықтан, бәрі маңызды, яғни сіз ешқашан бірдей позициядан басталмайсыз.

5
қосылды

Егер онлайн-қызметтен кездейсоқ сандарды пайдаланғыңыз келсе, оны wget-ді қолдануға болады, сіз көргіңіз келуі мүмкін сіз кездейсоқ сандардың генерациясы үшін random.org сияқты қызметтерді пайдалана аласыз, оларды wget арқылы ұстап, содан кейін жүктелген файлдан

wget -q https://www.random.org/integers/?num=100&min=1&max=100&col=5&base=10&format=html&rnd=new -O new.txt

http://programmingconsole.blogspot.in /2013/11/a-better-and-different-way-to-generate.html

2
қосылды
жауапты редакциялау туралы қамқорлық жасайды.
қосылды автор Namit Sinha, көзі
SO-қа қош келдіңіз. сілтемелерді жауап ретінде орналастырудан аулақ болыңыз. Сілтемелер арқылы оқылатын бөлшектерді қалдырып, жауаптың егжей-тегжейлі эскизін бере аласыз.
қосылды автор Shai, көзі

пайдалану pow (2, rand ()) ол жауаптарды қажетті шамаға қарай береді.

2
қосылды