Форум программистов, компьютерный форум CyberForum.ru

Генерация случайных чисел в заданном диапазоне. - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 65, средняя оценка - 4.68
SIvan
2 / 2 / 1
Регистрация: 10.05.2011
Сообщений: 19
18.07.2011, 18:11     Генерация случайных чисел в заданном диапазоне. #1
Здесь сказано
Не используйте % (получение остатка от деления) для ограничения получаемых случайных чисел. Это не самый лучший метод получения случайных чисел определенного диапазона значений
Почему?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
sandye51
программист С++
 Аватар для sandye51
677 / 579 / 39
Регистрация: 19.12.2010
Сообщений: 2,016
18.07.2011, 18:32     Генерация случайных чисел в заданном диапазоне. #2
мне кажется это бред)
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
18.07.2011, 18:46     Генерация случайных чисел в заданном диапазоне. #3
Цитата Сообщение от sandye51 Посмотреть сообщение
мне кажется это бред)
А мне нет!



Я думаю так:

Рассмотрим такой подход:
C++
1
int a=rand()%100;//получаем число от 0 до 99
при таком подходе очень высокая вероятность повторения получаемого числа, даже если rand() будет каждай раз возвращать неповторяющиеся числа. Т.е. при rand()=150 и rand()=250 (350, 450 и т.д.) мы получим число 50 (а в диапазоне от 0 до RAND_MAX у нас очень большая вероятность получить одинаковые числа), что, естественно, нам не нужно.
А так, как показанно по ссылке:
C++
1
2
3
4
5
6
7
8
int randomNumber(int hi)  // Правильный генератор случайных чисел для области значений [0,hi]
    {
       // Получение области значений [0,1)
       const float scale = rand()/float(RAND_MAX);
 
       // Возврат значения в области значений [0,hi]
       return int(scale*hi + 0.5); // неявное приведение типа и отброс дробной части числа
    }
повторяющееся число мы имеем шанс получить только, если rand() вернула число, которое уже было. При всех других значениях числа повторяться не будут (это исключено логикой получения числа).
Поэтому, при желании получить много случайных чисел в нужном диапазоне, вариант 2 конечно предпочтительней.
An1ka
65 / 70 / 2
Регистрация: 30.06.2011
Сообщений: 176
18.07.2011, 18:48     Генерация случайных чисел в заданном диапазоне. #4
Ну подобные генераторы не совершенны... и генерируют они псевдослучайные числа, у которых дальнейшая генерация полностью зависит от первой инициализации seed.
C
1
void srand ( unsigned int seed);
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
18.07.2011, 18:51     Генерация случайных чисел в заданном диапазоне. #5
Цитата Сообщение от An1ka Посмотреть сообщение
Ну подобные генераторы не совершенны... и генерируют они псевдослучайные числа, у которых дальнейшая генерация полностью зависит от первой инициализации seed.
C
1
void srand ( unsigned int seed);
Ну об этом речи нет, мы же о другом говорим.
А действительно случайное число можно получить используя аппаратные генераторы.
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
18.07.2011, 20:22     Генерация случайных чисел в заданном диапазоне. #6
По-моему это из маразматического шаманства что-то... Просто из любопытства сделал вот такую штуку
C
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
    
#define NUM_TESTS 100000000
    
int randomNumber(int hi)  // Правильный генератор случайных чисел для области значений [0,hi]
{
    // Получение области значений [0,1)
    const float scale = rand()/(float)RAND_MAX;
 
    // Возврат значения в области значений [0,hi]
    return (int)(scale*hi + 0.5); // неявное приведение типа и отброс дробной части числа
}
    
int main(void){
    int counters[2][10] = { 0 }, i;
    
    srand(time(NULL));
    for ( i = 0; i < NUM_TESTS; ++i ){
        ++counters[0][rand() % 10];
        ++counters[1][randomNumber(9)];
    }
    
    printf("Distribution of %d numbers from 0 to 9:\n", NUM_TESTS);
    printf("#       Use %%          Use function\n");
    for ( i = 0; i < 10; ++i )
        printf("%d%15d%15d\n", i, counters[0][i], counters[1][i]);
    
    return 0;
}
вывела
Код
C:\cpp\other>gcc -o many_randoms many_randoms.c

C:\cpp\other>many_randoms.exe
Distribution of 100000000 numbers from 0 to 9:
#       Use %          Use function
0       10003390        5555490
1       10001169       11105983
2       10001368       11105353
3        9994094       11111500
4        9997676       11117890
5       10003123       11113689
6       10001206       11113432
7       10003832       11104756
8        9996405       11116064
9        9997737        5555843

C:\cpp\other>many_randoms.exe
Distribution of 100000000 numbers from 0 to 9:
#       Use %          Use function
0        9995435        5553140
1       10004696       11115578
2       10001687       11104934
3       10003189       11114208
4       10000565       11116535
5       10000915       11108100
6       10002122       11110761
7        9999504       11105725
8       10000108       11112267
9        9991779        5558752

C:\cpp\other>many_randoms.exe
Distribution of 100000000 numbers from 0 to 9:
#       Use %          Use function
0        9997536        5555975
1       10003821       11110893
2        9998371       11113640
3        9998315       11113127
4       10002654       11107470
5       10002168       11110817
6       10001548       11110728
7        9997697       11105850
8        9999866       11111303
9        9998024        5560197

C:\cpp\other>
Если я правильно понимаю, значение каждого счётчика должно к 10000000 стремиться, так с оператором % оно как-то лучше получилось...
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
18.07.2011, 20:32     Генерация случайных чисел в заданном диапазоне. #7
Цитата Сообщение от easybudda Посмотреть сообщение
Если я правильно понимаю, значение каждого счётчика должно к 10000000 стремиться
Почему?
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
18.07.2011, 20:37     Генерация случайных чисел в заданном диапазоне. #8
Цитата Сообщение от Kastaneda Посмотреть сообщение
Почему?
Потому, что на 100000000 испытаний при равномерном распределении каждого из 10 чисел от 0 до 9 должно получаться по 100000000 / 10 = 10000000 штук, нет?
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
18.07.2011, 20:43     Генерация случайных чисел в заданном диапазоне. #9
Цитата Сообщение от easybudda Посмотреть сообщение
при равномерном распределении
Ну хз, на то они и (псевдо)случайные ))

Почему-то пограничных значений в случае с ф-цией наполовину меньше...
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
18.07.2011, 21:14     Генерация случайных чисел в заданном диапазоне. #10
easybudda, просто для полноты картины, покажи значение RAND_MAX.

Теперь по числам. Второй способ, по-моему, в статье описан с ошибками. Мне совершенно не понятно, к чему там округление вместо простого отбрасывания.
Больше похожей на правду кажется такая формула:
C
1
(int)(rand()/(RAND_MAX+1.0)*hi);
Диапазон [0, hi), то есть верхний предел не включается.
Ну и о качестве. Исследований я пока не проводил, но в случае, когда hi намного меньше RAND_MAX, результат по-моему должен быть примерно одинаково хорошим. А когда hi близко к RAND_MAX, то оба генератора представляются мне плохими. Хотя и по разному плохими
Короче, авторы статьи, мне кажется, излишне педантичны. Там, где требуется высокое качество псевдослучайной последовательности вряд ли будут использовать rand().
Evg
Эксперт С++Автор FAQ
 Аватар для Evg
16825 / 5246 / 321
Регистрация: 30.03.2009
Сообщений: 14,126
Записей в блоге: 26
18.07.2011, 21:23     Генерация случайных чисел в заданном диапазоне. #11
Цитата Сообщение от easybudda Посмотреть сообщение
Потому, что на 100000000 испытаний при равномерном распределении каждого из 10 чисел от 0 до 9 должно получаться по 100000000 / 10 = 10000000 штук, нет?
Ты не правильно проверяешь. Вопрос не только в том, какие будут числа, но и в их последовательности. Т.е. последовательность 1 1 1 1 2 2 2 2 3 3 3 3 .... по твоему методу будет равномерно распределённой, хотя такая последовательность никому не нужна. Как проверять правильность - хз, это вопрос к математикам
easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
18.07.2011, 21:29     Генерация случайных чисел в заданном диапазоне. #12
Цитата Сообщение от grizlik78 Посмотреть сообщение
Там, где требуется высокое качество псевдослучайной последовательности вряд ли будут использовать rand().
Полностью согласен. А там, где хватает rand() вполне подойдёт и rand() % HI, и незачем такие вот марсианские конструкции наворачивать. Я вообще за простые решения - они может и не всегда лучшие, за то понятные...

Добавлено через 5 минут
Цитата Сообщение от Evg Посмотреть сообщение
Ты не правильно проверяешь. Вопрос не только в том, какие будут числа, но и в их последовательности.
Это разные тесты. Тест на равномерное распределение чисел способ с шаманской формулой явно не прошёл, а последовательность, видимо, нужно проверять количеством идущих подряд одинаковых чисел...
Masel
4 / 4 / 0
Регистрация: 01.04.2009
Сообщений: 72
18.07.2011, 21:34     Генерация случайных чисел в заданном диапазоне. #13
Да вы че, ребят

оба предложенных варианта абсолютно равноценны в вопросе "случайности". Софистикой занимаетесь)
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
18.07.2011, 21:42     Генерация случайных чисел в заданном диапазоне. #14
Цитата Сообщение от easybudda Посмотреть сообщение
а последовательность, видимо, нужно проверять количеством идущих подряд одинаковых чисел...
Ну, вообще-то существует огромное количество различных статистических тестов. Пожалуй кое-какие из них я даже попробую, попозже. Правда гарантированно определить, что генератор является плохим нельзя, это можно утверждать лишь с некоторой заданной вероятностью.
Цитата Сообщение от Masel Посмотреть сообщение
оба предложенных варианта абсолютно равноценны в вопросе "случайности". Софистикой занимаетесь)
Masel, не факт. То есть оба неслучайны по определению, это да. Но хороший псевдослучайный генератор должен иметь свойства как можно ближе к свойствам истинно случайной последовательности. В статистическом смысле, конечно. Если интересно, можно про это почитать во втором томе "Искусства программирования" Дональда Кнута. Там же и некоторые тесты описаны.
Что же касается rand(), он обычно реализован с использованием линейного конгруэнтного генератора, а у него младшие биты имеют характеристики хуже старших, поэтому вариант с остатком рискует оказаться "менее случайным". Но не думаю, что сильно, ведь самые младшие биты rand() и не выдаёт.
Kastaneda
Модератор
Эксперт С++
 Аватар для Kastaneda
4236 / 2769 / 218
Регистрация: 12.12.2009
Сообщений: 7,104
Записей в блоге: 1
Завершенные тесты: 1
18.07.2011, 21:58     Генерация случайных чисел в заданном диапазоне. #15
А я в своей логике (пост#3) ошибку нашел!
Например имеем MAX_RAND = 32767, а hi=10, тогда одинаковые значения (например 5) мы будем иметь при

(int)(scale*hi + 0.5)=5
4.6 <= scale*hi <= 5.4
0.46 <= scale <=0.54


т.е. при 15072 <= rand() <= 17694, т.е. имеем диапазон 17694-15072=2622 при котором вернутся одинаковые значения. А при rand()%11 имеем RAND_MAX/11=2978 чисел, при которых вернутся одинаковые числа.

Не по теме:

Вот, теперь вроде правильно, хотя сплю уже, могу ошибаться...

easybudda
Модератор
Эксперт С++
 Аватар для easybudda
9372 / 5422 / 914
Регистрация: 25.07.2009
Сообщений: 10,423
18.07.2011, 23:01     Генерация случайных чисел в заданном диапазоне. #16
Цитата Сообщение от grizlik78 Посмотреть сообщение
Правда гарантированно определить, что генератор является плохим нельзя, это можно утверждать лишь с некоторой заданной вероятностью.
Ну я бы немного по-другому сказал: не важно, какой из способов плохой, а какой ещё хуже. Если сложный способ добиться чего-либо не имеет явных преймуществ перед простым способом добиться того же самого, какой смысл использовать сложный способ?
А тестов случайной последовательности на случайность действительно много...
Bers
Заблокирован
18.07.2011, 23:23     Генерация случайных чисел в заданном диапазоне. #17
Цитата Сообщение от grizlik78 Посмотреть сообщение
Правда гарантированно определить, что генератор является плохим нельзя, это можно утверждать лишь с некоторой заданной вероятностью.
Кнут, том второй.
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
18.07.2011, 23:25     Генерация случайных чисел в заданном диапазоне. #18
Цитата Сообщение от Bers Посмотреть сообщение
Кнут, том второй.
А ничё, что я на него в том сообщении сослался?
Bers
Заблокирован
18.07.2011, 23:37     Генерация случайных чисел в заданном диапазоне. #19
Цитата Сообщение от grizlik78 Посмотреть сообщение
А ничё, что я на него в том сообщении сослался
Да нет, ничего. Правда, что-то ссылки невидать. Да и не писал Кнут ничего подобного:
Цитата Сообщение от grizlik78 Посмотреть сообщение
Правда гарантированно определить, что генератор является плохим нельзя, это можно утверждать лишь с некоторой заданной вероятностью.
Он лишь предложил разные методики определения "качества" рандома.

Если кому то захочется состряпать что нибудь этакое - могут почитать, проникнуться, и выбрать для себя подходящие.

Добавлено через 2 минуты
а.... извиняюсь, не увидил просто ссылки
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
18.07.2011, 23:39     Генерация случайных чисел в заданном диапазоне.
Еще ссылки по теме:

генерация случайных чисел C++
генерация рандомных чисел в диапазоне C++
Генерация случайных чисел в диапазоне 0 - 1 C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
grizlik78
Эксперт C++
 Аватар для grizlik78
1882 / 1414 / 101
Регистрация: 29.05.2011
Сообщений: 2,958
18.07.2011, 23:39     Генерация случайных чисел в заданном диапазоне. #20
Bers, стоит яснее выражать свою мысль, а не просто "Кнут, том второй." Я вот до сих пор так и не понял, к чему это было.
Процитированные мои слова, это мои слова, Кнуту я их не приписывал. А ссылка до сих пор есть. Вернее не ссылка, а отсылка к той книге.
Yandex
Объявления
18.07.2011, 23:39     Генерация случайных чисел в заданном диапазоне.
Ответ Создать тему
Опции темы

Текущее время: 21:06. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru