rand() в с++ - Codeforces

→ Обратите внимание

До соревнования
2024-2025 ICPC, NERC, Southern and Volga Russian Regional Contest (Unrated, Online Mirror, ICPC Rules, Preferably Teams)
4 дня
Зарегистрироваться »

→ Лидеры (рейтинг)

№	Пользователь	Рейтинг
1	tourist	4009
2	jiangly	3821
3	Benq	3736
4	Radewoosh	3631
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3388
10	gamegame	3386

Страны | Города | Организации

Всё →

→ Лидеры (вклад)

№	Пользователь	Вклад
1	cry	164
1	maomao90	164
3	Um_nik	163
4	atcoder_official	161
5	-is-this-fft-	158
6	awoo	157
7	adamant	156
8	TheScrasse	154
8	nor	154
10	Dominater069	153

Всё →

→ Найти пользователя

→ Прямой эфир

Детальнее →

Блог пользователя _dangerous_

rand() в с++

Автор _dangerous_, 13 лет назад, По-русски

На днях возник такой вопрос: как реализуется функция rand() в с++? попутно и srand().

я знаю, как примерно выглядят эти функции, но хотел бы точно увидеть код или узнать библиотеку, в которой они лежат (облазив весь cstdlib, stdlib.h их реализации не нашел)

нашел такой вариант реализации

но 1) верен ли он? 2) что такое 1103515245m? точнее, что такое m?

help, rand, random

_dangerous_
13 лет назад
31

Комментарии (31)

Написать комментарий?

qwaker.00

13 лет назад, # |

← Rev. 2 →

Верность проверяем просто вычисляя рандом этим алгоритмом и родным: ответ — нет (как минимум на моем гну) Префикс m не компилируется (опять же на моем гну), как и отсутствие плюса (или что там должно быть??) перед 2768 :)

→ Ответить

riadwaw

13 лет назад, # |

Где-то может и так. А вообще — по разному.

→ Ответить

yoihito

13 лет назад, # |

тут есть код, только там без m http://goo.gl/nPbEJ

→ Ответить

andreyv

13 лет назад, # |

← Rev. 2 →

Например, так: stdlib/random_r.c в GNU C Library. А в стандарте POSIX можно найти более простой пример, который предлагается к использованию.

→ Ответить

_dangerous_

13 лет назад, # ^ |

не пойму, где там реализация rand()

→ Ответить

andreyv

13 лет назад, # ^ |

В glibc rand() вызывает функцию __random(), которая вызывает функцию __random_r(), которая определена в этом файле.

→ Ответить

gen

13 лет назад, # ^ |

+27

→ Ответить

PooPS

13 лет назад, # ^ |

+11

Скорее,

→ Ответить

petro.ivanov

13 лет назад, # ^ |

+42

→ Ответить

gen

13 лет назад, # ^ |

← Rev. 2 →

Nevermind.

→ Ответить

Endagorion

13 лет назад, # |

Стандарт вроде бы ничего не говорит про реализацию, предъявлены только некоторые формальные требования, так что вопрос не совсем корректен, надо спрашивать "как реализован rand() в моем компиляторе".

А если в общем, то на этот вопрос все-таки можно ответить — rand() в c++ реализован плохо. Практически везде, насколько мне известно.

→ Ответить

antivlad

13 лет назад, # ^ |

А чем он плох?

→ Ответить

Endagorion

13 лет назад, # ^ |

Ну, начиная хотя бы с того, что числа получаются не случайные. =) Это не шутка, сгенерировать достаточно "равномерную" и "независимую" псевдослучайную выборку очень сложно. На википедии хорошо про это написано.

Мне даже кто-то рассказываел баечку про то, что в каком-то из компиляторов (возможно, не сишном) ГСЧ никогда не выкидывал ноль, в принципе.

По сути вопроса конкретных тестов привести не готов, просто из собственного опыта говорю. Предлагаю поверить на слово или проверить самому. =)

→ Ответить

qwaker.00

13 лет назад, # ^ |

← Rev. 2 →

Хороший генератор случайных чисел это такой что мы не можем предсказать по некоторой последовательности сгенерированных псевдослучайных чисел, что будет за следующее число. Тут такого свойства не наблюдается :)

UPD Придумался пример. Пусть у нас seed просто увеличивается на 1, а генератор возвращает sha-хэш (или его часть) от seed. Тогда в общем случае мы не можем по последовательности хэшей сказать, что будет дальше.

→ Ответить

al13n

13 лет назад, # ^ |

Точнее это свойство ГСЧ называется криптостойкостью.

→ Ответить

goo.gl_SsAhv

13 лет назад, # ^ |

← Rev. 2 →

Что значит "плохо"? Это смотря какие требования мы выдвигаем. Понятно что для некоторых вероятностных алгоритмов нужны случайные числа, и в зависимости от задачи иногда лучше использовать сторонние крутые библиотеки, нежели встроенную функцию, но для ацм вполне хватает rand()

→ Ответить

Endagorion

13 лет назад, # ^ |

Да, для этого хватает, конечно.

Хотя вот у некоторых компиляторов rand() не выкидывает числа больше 2^15 — 1. Неприятно во время какого-нибудь контеста это обнаружить, наверное.

→ Ответить

goo.gl_SsAhv

13 лет назад, # ^ |

-13

Я всегда считал, что числа до 15 бит на MS и 31 или 32 на линуксах, поэтому проблемы здесь не вижу. Нужно аккуратно использовать, иногда надо сгенерить число 64-битное, проблемы нет в том чтобы подвигать да поксорить.

→ Ответить

Fefer_Ivan

13 лет назад, # ^ |

cerr << RAND_MAX << endl;

→ Ответить

nk.karpov

13 лет назад, # ^ |

Так сейчас в c++0x есть нормальные рандомы куча распределений) и они по моему более менее адекватно работают...

→ Ответить

goo.gl_SsAhv

13 лет назад, # |

http://www.velocityreviews.com/forums/t435632-rand-implementation.html

→ Ответить

qwaker.00

13 лет назад, # |

← Rev. 2 →

+18

void _srand(int x) {
    seed = x;
}

int _rand(){
    return (((seed = seed * 214013L + 2531011L) >> 16) & 0x7fff);
}

int main(){
    srand(123);
    _srand(123);
    for (int i = 0; i < 10;i++) printf("%d ", rand());
    puts("");
    for (int i = 0; i < 10;i++) printf("%d ", _rand());
    puts("");
}

Совпадает :) Код любезно взят из visual studio. При отладке нужно просто зайти вглубь rand и там почти тоже самое написано. Так как стандартом rand походу не закреплен — на linux может и не совпасть. Кто проверит — отпишитесь ниже пожалста :)

Полный код для лентяев

→ Ответить

_dangerous_

13 лет назад, # ^ |

магия) где вы это нашли?

→ Ответить

goo.gl_SsAhv

13 лет назад, # ^ |

Ну например в моем комментарии выше, первый результат гугла по запросу rand implementation

→ Ответить

_dangerous_

13 лет назад, # ^ |

спасибо

→ Ответить

SkyHawk

13 лет назад, # ^ |

← Rev. 2 →

На gcc 4.4.3 не совпадает и даже не похоже — выдаёт какие-то подозрительно маленькие числа.

UPD: "подозрительно маленькие" — видимо, вот причина

→ Ответить

qwaker.00

13 лет назад, # ^ |

Windows? У меня gnu 4.5.2 и visual studio 2010 на windows согласны. Тут вопрос в том пользуется ли твой компилятор услугами msvcrt.dll и какой версии.

→ Ответить