Случайные целые числа в C, насколько плохо rand ()% N по сравнению с целочисленной арифметикой? Каковы его недостатки?

EDIT: Мой вопрос: rand()%N считается очень плохой, тогда как использование целочисленной арифметики считается превосходным, но я не вижу разницы между ними.

Люди всегда упоминают:

Может ли кто-нибудь объяснить, есть ли здесь какой-либо из этих пунктов и как это увидеть?

Идея неслучайности младших бит – это то, что должно сделать PE из двух случаев, которые я показываю, различаются, но это не так.

Я думаю, что многие, как я, всегда избегают использования rand() или rand()%N потому что нас всегда учили, что это довольно плохо. Мне было любопытно узнать, насколько эффективны «неправильные» случайные целые числа, сгенерированные с помощью c rand()%N Это также является ответом на ответ Райана Райха в « Как создать случайное целое число из диапазона .

По правде говоря, объяснение звучит очень убедительно; тем не менее, я думал, что попробую. Итак, я сравниваю дистрибутивы ОЧЕНЬ наивным образом. Я запускаю оба случайных генератора для разных чисел образцов и доменов. Я не видел смысла вычислять плотность вместо гистограмм, поэтому я просто вычислил гистограммы и, просто посмотрев, я бы сказал, что они оба выглядят так же единообразно. Что касается другой точки, которая была поднята, о фактической случайности (несмотря на равномерное распределение). I – снова наивно-компромиссная энтропия перестановок для этих прогонов, которые одинаковы для обоих наборов образцов, которые говорят нам, что нет никакой разницы между тем, как упорядочить возникновение.

Итак, для многих целей мне кажется, что rand()%N будет в порядке, как мы можем увидеть их недостатки?

Здесь я покажу вам очень простой, неэффективный и не очень элегантный (но, я думаю, правильный) способ вычисления этих образцов и получения гистограмм вместе с энтропиями перестановок. Я показываю графики для доменов (0, i) с i в {5,10,25,50,100} для различного количества образцов:

5 значений, 5k выборок

10 значений 10k образцов

25 значений, 250 тыс. Выборок

100 значений, 1M образцов

В коде, который, я думаю, мало что можно увидеть, поэтому я оставлю как C, так и код matlab для целей репликации.

 #include  #include  #include  int main(int argc, char *argv[]){ unsigned long max = atoi(argv[2]); int samples=atoi(argv[3]); srand(time(NULL)); if(atoi(argv[1])==1){ for(int i=0;i<samples;++i) printf("%ld\n",rand()%(max+1)); }else{ for(int i=0;i<samples;++i){ unsigned long num_bins = (unsigned long) max + 1, num_rand = (unsigned long) RAND_MAX + 1, bin_size = num_rand / num_bins, defect = num_rand % num_bins; long x; do { x = rand(); } while (num_rand - defect <= (unsigned long)x); printf("%ld\n",x/bin_size); } } return 0; } 

И вот код Matlab, чтобы построить это и вычислить PE (recursion для перестановок, которые я взял с нее: https://www.mathworks.com/matlabcentral/answers/308255-how-to-generate-all-possible- перестановки-без использования-функции-perms-randperm ):

 system('gcc randomTest.c -o randomTest.exe;'); max = 100; samples = max*10000; trials = 200; system(['./randomTest.exe 1 ' num2str(max) ' ' num2str(samples) ' > file1']) system(['./randomTest.exe 2 ' num2str(max) ' ' num2str(samples) ' > file2']) a1=load('file1'); a2=load('file2'); uni = figure(1); title(['Samples: ' num2str(samples)]) subplot(1,3,1) h1 = histogram(a1,max+1); title('rand%(max+1)') subplot(1,3,2) h2 = histogram(a2,max+1); title('Integer arithmetic') as=[a1,a2]; ns=3:8; H = nan(numel(ns),size(as,2)); for op=1:size(as,2) x = as(:,op); for n=ns sequenceOcurrence = zeros(1,factorial(n)); sequences = myperms(1:n); sequencesArrayIdx = sum(sequences.*10.^(size(sequences,2)-1:-1:0),2); for i=1:numel(x)-n [~,sequenceOrder] = sort(x(i:i+n-1)); out = sequenceOrder'*10.^(numel(sequenceOrder)-1:-1:0).'; sequenceOcurrence(sequencesArrayIdx == out) = sequenceOcurrence(sequencesArrayIdx == out) + 1; end chunks = length(x) - n + 1; ps = sequenceOcurrence/chunks; hh = sum(ps(logical(ps)).*log2(ps(logical(ps)))); H(n,op) = hh/log2(factorial(n)); end end subplot(1,3,3) plot(ns,H(ns,:),'--*','linewidth',2) ylabel('PE') xlabel('Sequence length') filename = ['all_' num2str(max) '_' num2str(samples) ]; export_fig(filename) 

    Оба подхода имеют свои подводные камни, а ваши графики – не что иное, как хорошая проверка центральной предельной теоремы! Для разумной реализации rand() :

    1. % N страдает от эффекта «голубей», если 1u + RAND_MAX не кратно N

    2. /((RAND_MAX + 1u)/N) , как правило, равномерно распределяет возврат rand по вашему диапазону из-за эффектов округления целых чисел.

    В остальном, если N мало, см. RAND_MAX , я бы RAND_MAX % за его приемлемость. В любом случае проверьте, чтобы ваш генератор увидел его, он имеет соответствующие статистические свойства для вашего приложения.

    rand() % N считается крайне бедной не потому, что распределение плохое, а потому, что случайность является бедной до несуществующей. (Если что-то будет распространяться слишком хорошо.)

    Если N не мало по отношению к RAND_MAX, то оба

     rand() % N 

    а также

     rand() / (RAND_MAX / N + 1) 

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

    Глядя на гистограммы распределения, вы не увидите, что для некоторых реализаций rand() % N имеет гораздо более худшую проблему, чтобы показать, что вам придется выполнять некоторые корреляции с предыдущими значениями. (Например, попробуйте взять rand() % 2 , затем вычитаем из предыдущего значения, которое вы получили, и построите гистограмму различий. Если разница не равна 0, у вас есть проблема.)

    Я хотел бы сказать, что реализации, для которых младшие разряды rand() не являются случайными, просто ошибочны. Хотелось бы подумать, что все эти неудачные реализации исчезли бы к настоящему времени. Я хотел бы думать, что программистам не нужно беспокоиться о вызове rand()%N Но, к сожалению, мои пожелания не меняют того факта, что это, кажется, одна из тех ошибок, которые никогда не исправляются, а это значит, что программистам все равно приходится беспокоиться.

    См. Также список вопросов C , вопрос 13.16 .

    В связи с тем, что по модулю арифметики работает, если N является значительным по сравнению с RAND_MAX, делая% N, это сделает так, что вы значительно чаще получите некоторые значения, чем другие. Представьте себе, что RAND_MAX равно 12, а N равно 9. Если распределение хорошее, вероятность получения одного из 0, 1 или 2 равна 0,5, а шансы получить один из 3, 4, 5, 6, 7, 8 0,5. В результате вы в два раза чаще получаете 0 вместо 4. Если N является точным делителем RAND_MAX, эта проблема распределения не происходит, и если N очень мало по сравнению с RAND_MAX, проблема становится менее заметной. RAND_MAX не может быть особенно большим (возможно, 2 ^ 15 – 1), что делает эту проблему хуже, чем вы можете ожидать. Альтернатива делать (rand() * n) / (RAND_MAX + 1) также не дает четного распределения, однако будет иметь место любое m е значение (для некоторого m ), которое будет более вероятным, чем более вероятными значениями, находящимися в нижней части распределения.

    Если N равно 75% от RAND_MAX, то значения в нижней трети вашего дистрибутива в два раза превышают значения в двух верхних трети (так как это означает, что дополнительные значения отображают)

    Качество rand() будет зависеть от реализации системы, в которой вы находитесь. Я считаю, что некоторые системы имеют очень плохую реализацию, страницы руководства OS Xs объявляют rand устаревшими. На странице руководства Debian указано следующее:

    Версии rand () и srand () в библиотеке Linux C используют один и тот же генератор случайных чисел как случайный (3) и srandom (3), поэтому младшие разряды должны быть столь же случайными, как бит более высокого порядка. Тем не менее, в старых реализациях rand () и в текущих реализациях в разных системах младшие разряды намного менее случайны, чем бит более высокого порядка. Не используйте эту функцию в приложениях, предназначенных для переноски, когда требуется хорошая случайность. (Вместо этого используйте случайный (3).)