Исторические предпосылки RANDOM в bash

Есть ли способ проверить случайность выборки?
У меня из музыкальной коллекции (6тыс +) один трек выбирался 16 раз, а остальные от 2 до 5 за период 6 лет. Т.е. выключение компьютера, переустановка системы, виндовс, линукс.

Total Tracks: 6127

PlayCount Tracks
--------- ------
        1     42
        2   1936
        3   1289
        4   1298
        5    753
        6    437
        7    221
        8     81
        9     45
       10     17
       11      5
       12      1
       13      0
       14      0
       15      1
       16      1
       17      0
       18      0
       19      0
       20      0

У Страуструпа мнение противоположенное, по его мнению и size_t должен был быть со знаком, что бы можно было уйти в минус, убрать невидимые преобразования signed - unsigned (все signed).

В случае signed - бесполезная портянка с ветвлением

Каким еще ветвлением?

Ух ты, не знал. Вот он значит один из тех вредителей которые signed пропихивают куда не следует и баги провоцируют. Впрочем, если задуматься, то неудивительно.

Хм, да, значит ветвление где-то в другом месте было (помню что сталкивался при реверсе, ещё удивился что это за ерунда, а потом понял что там просто знаковый тип вставили не к месту). Ну всё равно, вместо одной инструкции какая-то длинная чушь на ровном месте.

Смотрим intel64:

div2_signed:
        shr     eax, 31
        add     eax, edi
        sar     eax
div2_unsigned:
        shr     eax

div2_signed:
        add     w0, w0, w0, lsr 31
        asr     w0, w0, 1
div2_unsigned:
        lsr     w0, w0, 1

Я вот не думаю что он способствует багам, скорее наоборот, мнение как у Страуструпа. Если какая то проблема с переполнением, то причем тут знак? Так же может и unsigned переполниться. Это надо все проверять. И программисту который проверяет переполнение, signed помогает тем, что компилятор сразу вычеркивает варианты с переполнением, потому что UB и типа невозможно.

Знак при том, что у unsigned-а переполнение нормальное, а у signed-а мало того что портит число неинтуитивным способом, так ещё и при неудачных опциях компилятора портит код вообще.

signed помогает тем, что компилятор сразу вычеркивает варианты с переполнением,

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

Для unsigned например можно писать так:

x += 10;
if(x<10) goto err;

Для знаковых проверку придётся мало того что в несколько раз усложнить, так ещё и придётся, кроме неудобства знаковых чисел, учитывать ещё и потенциальное вредительство компилятора, могущего эту проверку частично или полностью вырезать на основании «переполнения быть не может» (если забудешь -fno-strict-overflow).

В итоге она будет выглядеть, например, так:

int x;
if(x<0) x += 10;
else {
  x = (int)(((unsigned int)x) + 10);
  if(x<10) goto err;
}

а у signed-а мало того что портит число неинтуитивным способом

У unsigned все тоже самое, просто в другую сторону:

for (auto i = size(); i >= 0; --i) // oops

Если ты хочешь найти переполнение, соответствующий код вырезать нельзя.

Я говорил что это полезно для корректных программ, для некорректных полезен -fsantize + -fanalyzer.

Для unsigned например можно писать так:

Для signed так:

if (ckd_add(&x, x, 10)) goto err;

add edi, 10
jo .err

for (auto i = size(); i >= 0; --i) // oops

Так это дефективный код, сразу видно. Скорее всего писался кем-то далёким от нормального программирования. Проверять переход в цикле через ноль через i<0 даже для signed это что-то плохо пахнущее. Ну и auto, да ещё и всунутое внутрь императивного кода, выдаёт с++ника. А ещё скорее всего тут баг - цикл будет сделан size()+1 раз, а не size() раз, как обычно нужно в таких циклах. Вобщем, куда ни глянь, везде проблема в программисте. И да, именно такие недопрограммисты любят int-ы везде сувать, возможно потому что они сглаживают их слабоумие.

Нужно переписать так:

size_t i;
for(i=size(); i--; ) {
}
или так
for(i=size(); i; i--) {
}

size_t i;
i = size();
do {
} while(i--);

Я говорил что это полезно для корректных программ, для некорректных полезен -fsantize + -fanalyzer.

Я и пишу про корректные программы.

if (ckd_add(&x, x, 10)) goto err;

Это только в новых компиляторах будет работать, для переносимого кода не годится.

Так это дефективный код, сразу видно

Тоже самое можно сказать про код плохо обрабатывающий поведение signed.

Я и пишу про корректные программы.

Я про корректные с точки зрения стандарта.

Это только в новых компиляторах будет работать, для переносимого кода не годится.

Это стандартизация __builtin_add_overflow который есть в gcc 3 и clang 3. Может и раньше появился, на godbolt старее нету.

Тоже самое можно сказать про код плохо обрабатывающий поведение signed.

Я про то, что корректная обработка unsigned делается проще и понятнее чем signed, и при её реализации меньше шанс о чём-то забыть и допустить баг.

Я про корректные с точки зрения стандарта.

Прекращай демагогию.

__builtin_add_overflow который есть в gcc 3 и clang 3

А в каком-нить другом компиляторе нету.

В любом случае, это не единственная причина предпочитать unsigned. Знаковость так или иначе 1) требует специальной обработки в ряде мест, 2) отжирает на себя диапазон представления полезных положительных чисел на целых бит. Там, где она при этом ничего не даёт взамен - не надо её вводить. Аргументы вида «я не понимаю беззнаковую математику» отвергнем, т.к. умственно отсталым личностям в любом случае нечего делать в Си.

А в каком-нить другом компиляторе нету.

Каких? Для таких можно свою версию __builtin_add_overflow написать. Простой алиас удобнее чем ручное повторение значений.

требует специальной обработки в ряде мест

Тоже самое могу сказать про unsigned.

отжирает на себя диапазон представления полезных положительных чисел на целых бит

А unsigned отжирает диапазон отрицательных. И потом нормально не сконвертируешь большой unsigned в int, а int много где используется, так что иногда имеет смысл unsigned держать ограниченным по INT_MAX.

аргументы вида «я не понимаю беззнаковую математику» отвергнем, т.к. умственно отсталым личностям в любом случае нечего делать в Си.

Там основной аргумент что много боли от того что смешиваются часто signed и unsigned, и это приводит к проблемам.

signed предлагают использовать по умолчанию, там где нужен бит или полный диапазон целых, надо использовать unsigned. Так что эти аргументы на самом деле мимо.

Тоже самое могу сказать про unsigned.

Ну это враньё.

А unsigned отжирает диапазон отрицательных.

В местах, где отрицательные не нужны и вредны, это заявление - очередная клоунада.

И потом нормально не сконвертируешь большой unsigned в int,

Что за идиотизм?

а int много где используется

Вот надо избавляться от этих пережитков прошлого.

Там основной аргумент что много боли от того что смешиваются часто signed и unsigned, и это приводит к проблемам.

Чтобы уменьшить смешивание, надо убрать signed типы отовсюду где в них нет острой нужды.

Вот же ты упёртый. Пиши дальше кривой код, раз так нравится.

#!/bin/bash3 шебанга этот $RANDOM перенаправлялся бы в rand() из libc

Такое себе предложение, с учётом того, что в bash не определён RAND_MAX.

но в Bash используется обрезка до 15 бит,

Раз так, то могу предположить, что это простой и быстрый способ получить нечётный модуль (32767). У конгруэнц-генераторов с четным модулем откровенно плохое качество. Было бы лучше использовать в качестве модуля простое число.

Сам когда-то занимался моделированием и приходилось исследовать качество разных генераторов псевдослучайных чисел.

Все делители числа 1 7 31 151 217 1057 4681 32767

Так что качество такого модуля тоже не очень. Весь диапазон пробежаться не будет это точно.

В местах, где отрицательные не нужны и вредны, это заявление - очередная клоунада.

Я уже показал примеры когда они нужны. size()-1 тоже имеет довольно предсказуемое поведение с int, и очень плохое с unsigned. Про вред придумал ты, пользу я назвал - лучшая оптимизация правильный программ, меньше неожиданных конвертаций.

И потом нормально не сконвертируешь большой unsigned в int

Что за идиотизм?

Мощная аргументация. Ну вот у тебя unsigned превышает INT_MAX, а теперь тебе нужно передать его значение в функцию которая принимает int и включает проверку int > 0.

Вот же ты упёртый. Пиши дальше кривой код, раз так нравится.

Почему кривой это с signed? В крайнем случае это спорная тема. Я склоняюсь что кривой с unsigned. И это не новая тема, коллекции в Qt, Java используют signed.

Я уже показал примеры когда они нужны. size()-1 тоже имеет довольно предсказуемое поведение с int, и очень плохое с unsigned. Про вред придумал ты, пользу я назвал - лучшая оптимизация правильный программ, меньше неожиданных конвертаций.

А не надо делать size()-1 наобум. И size()+1 тоже, кстати. Меньше конвертаций будет если убрать signed-ы отовсюду.

Ну вот у тебя unsigned превышает INT_MAX, а теперь тебе нужно передать его значение в функцию которая принимает int и включает проверку int > 0.

А представь, у тебя signed int, а функция принимает только char (уже не важно какой знаковости). Как быть? Твой пример аналогичный.

Чтобы было равномерное, надо писать что-то вроде $(((RANDOM * 32768 + RANDOM) % 65536))

Нет. Максимальное 16-разрядное простое число это 65521. Чтобы было равномерно надо писать (a*x+b)%65521 Такой генератор будет пробегать весь диапазон от 0 до 65521 за исключением решения уравнения (a*x+b)%65521=x. Тут и старший бит будет распределен как надо. Коэффициент a следует выбрать примерно 1/3 от 65521.

Если число не простое, то циклов, по которым бегает генератор будет столько же сколько простых множителей. У используемого числа 32767 (1, 7, 31, 151, 32767 ) будет 5 циклов, один из которых тривиальный, являющийся решением уравнения. В зависимости от начального значения мы попадает в одни из циклов и бегаем по нему. Отсюда и проблемы с качеством генерации.

Сидит физик с математиком перед компом, а на мониторе периодически выскакивает цифра: 8… 8… 8… 8… 8… Подходит к ним программист:

— А это что у вас такое?

— Это абсолютный генератор случайных чисел.

— Так он же не работает!

— А ты докажи!

Если число не простое, то циклов, по которым бегает генератор будет столько же сколько простых множителей.

Тут соврал. Всё несколько хитрее. Может быть начальная последовательность, которая сваливается в цикл длинной равной одному из простых множителей. Вроде как. То есть для 32767 максимальная длина цикла 151. Сразу видно, какое низкое качество рандома было заложено бородатыми дядьками.