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

Кто-то в MITе под пиво запилил, жуя крошки из бороды и взяв 16-bit int для значения.

Да машины скорее всего 16-битные были во времена первых юниксов вот и тянут наследие

почему именно этот диапазон

Видимо, потому что это распространённый размер int. Алгоритм ее смотрел, но наверняка что-то простейшее, оно же не для криптографии там.

Но зачем signed int? Он же всегда положительный. 0 - 65535 было бы логично.

А первые юниксы были 18-бит, если мы про PDP-7, и в одном байте 6 бит.

Это 15-bit int. Либо 16-bit signed int.

Переменная $RANDOM возвращает псевдослучайное число в диапазоне 0 - 32767.

Реализация $RANDOM в Bash основана на линейном конгруэнтном генераторе (LCG) — одном из самых простых и старых алгоритмов генерации псевдослучайных чисел.

Конкретные параметры LCG в Bash (как и во многих других реализациях) следующие:

    Формула:
    Xn+1=(a⋅Xn+c)mod  m
    

    Параметры (типичные для glibc и многих Unix-систем):

        a=1103515245

        c=12345

        m=231 (но в Bash используется обрезка до 15 бит, поэтому диапазон 0–32767)

Или более понятный пример функции на C:

static unsigned int seed = 1;  // начальное значение

int bash_random() {
    seed = (1103515245 * seed + 12345) & 0x7FFF;  // обрезка до 15 бит
    return seed;
}

По сути это цикл, но для целей скриптования на баше его должно быть достаточно.

Ты в чукотской нотации пишешь чтоле? Выпей певка, int знаковый, если не указано обратное, так что 16-bit int или 15-bit unsigned int, а не наоборот.

int знаковый

Но он не знаковый.

Да, там так и тянут первый генератор из изначального юникса:

rseed = rseed * 1103515245 + 12345;
return ((unsigned int)(rseed & 32767));       /* was % 32768 */

Обоснуй

Знаковый int кодирует значения от -32767 до 32767. В баше диапазон значений от 0 до 32767. Знака нет. Куда дели бит, зачем?

Куда дели бит, зачем?

Нет знака у random, исходный код реализации из bash я привел.

Да, и там insigned int. Unsigned int кодирует значения от 0 до 65535, в баше от 0 до 32767. Всё равно бит пропадает :-)

Всё равно бит пропадает

Ничего там не пропадает, старший бит в этой говномамонтовой быстрой формуле не имеет равномерное распределение и потому гасится.

В баше диапазон значений от 0 до 32767. Знака нет. Куда дели бит, зачем?

Бит никуда не делся, его тупо не использовали. Почему, зачем, история умалчивает.

Почему, зачем, история умалчивает.

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

Тут вопрос не в том, что возвращает rand, а почему знаковое целое использовали, вместо беззнакового.

Тут вопрос не в том, что возвращает rand, а почему знаковое целое использовали, вместо беззнакового.

Перечитайте коммент, на который отвечали, там ответ есть.

Почему, зачем, история умалчивает.

Дык. Вот у меня и вопрос :-)

старший бит в этой говномамонтовой быстрой формуле не имеет равномерное распределение

Почему? Я смотрю на формулу и ничто не мешает сделать там & 65535 и будет равномерное.

Ну т.е., как я и сказал, это было сделано потому что какой-то бородач в MITе так решил. Теоритического обоснования нигде не приведено.

У функции rand() тип возврата int. Видимо сделали так чтобы в него всегда влезало без отрицательных чисел.

А функция rand() выполняется не в баше, это функция из libc? Тогда понятно.

Насколько я помню Кнута, это младшие биты в этом ГПСЧ неравномерные.

Почему? Я смотрю на формулу и ничто не мешает сделать там & 65535 и будет равномерное.

Ну это уже смешно. Там оно гасится специально, потому что ставилась задача сделать функцию согласно POSIX стандарту в виде int, а не unsigned int, потому в формуле подобраны коэффициенты максимально равномерного распределения в диапазоне [0, RAND_MAX], если получится RAND_MAX=INT_MAX, то это будет наилучшее решение, оно и найдено. Для 16-бит INT_MAX=32767. Для этой формулы, если не гасить старший бит, то он не равномерен. А когда он погашен, то он погашен вообще, отсутствует, у него нет распределения.

Там оно гасится специально, потому что ставилась задача сделать функцию согласно POSIX стандарту в виде int, а не unsigned int

Вот это понятно.

А почему для этой формулы, если не гасить старший бит, то он не равномерен?

А почему для этой формулы, если не гасить старший бит, то он не равномерен?

Да собственно потому как и везде: если старший бит не в виде битовых вычислений, а в виде арифметических операций, то у него не сколько функция как значение результата, сколько как переполнение. А раз так, то на его значение лучше не полагаться если возможно. Тут возможно и задача полностью выполнена.

Прочитал про LCG, там чем старше бит, тем больше у него период. А значит, случайность старших битов чуть хуже младших. По этой причине, например, в Java генерируется 48-битное СЧ, из которого затем достаётся 32-битное. Возможно, в работе 88-го года показали, что 15 бит норм.

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

Возможно, в работе 88-го года показали, что 15 бит норм.

Да боже мой, вы так ничего и не поняли. Да можно было сделать коэффициенты для полных 16 бит, но такой задачи не стояло и была бы не тупая арифметическая формула, а медленный алгоритм, который применяется при расчётах с переполнением, который не то что написать, а понять то не каждый может что там происходит.

решение элементарное возьми $RANDOM + $RANDOM столько раз сколько нужно, не совсем то что нужно, но что то похожее:)

вероятность любого бита в рандомном числе одинакова.

Да боже мой, вы так ничего и не поняли.

Да, ты так и не сказал, почему старший бит неравномерен.

Да можно было сделать коэффициенты для полных 16 бит, но такой задачи не стояло и была бы не тупая арифметическая формула, а медленный алгоритм,

Была бы точно такая же формула с другими коэффициентами. Вон в Java генерируют 32 бит и не жужжат.

медленный алгоритм, который применяется при расчётах с переполнением

У нас тут коэффициент 1103515245 умножается на положительный seed, переполнение происходит в 100%. Ты о каком переполнении речь ведёшь?

решение элементарное возьми $RANDOM + $RANDOM столько раз сколько нужно, не совсем то что нужно, но что то похожее:)

Это будет совсем не равномерное распределение.

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

Да, ты так и не сказал, почему старший бит неравномерен.

Много раз сказал.

Была бы точно такая же формула с другими коэффициентами.

Ну слава богу, что с коэффициентами разобрались. Теперь о формуле: она может быть ровно такой же, если забить на быстрый int и делать через long, что на тех процессорах было умножение через одно место с применением ассемблерных функций как в libc так и встроенных в компилятор.

Ты о каком переполнении речь ведёшь?

Воот, почти дошло. О таком, что сколько их там было? И тогда как верить значению бита, если оно взводится и тогда, когда там в результате должен быть 0 в этом бите, но еще и когда произошло хоть одно переполнение по пути?

с чего бы не равномерное ?? ^) $RANDOM + $RANDOM даст значение аккурат от 0 до 2*max($RANDOM)=65534.

0 = 0 + 0, вероятность 1/32768 * 1/32768 = 2^-30.

1 = 0 + 1 = 1 + 0, вероятность 1/32768 * 1/32768 + 1/32768 * 1/32768 = 2^-29.

Т.е. уже на этих двух примерах видим, что единица будет появляться в 2 раза чаще нуля. С вероятностью других значений всё будет ещё кудрявей. А нам нужна одинаковая вероятность каждого значения, равная 2^-16.

с чего бы не равномерное ?? ^) $RANDOM + $RANDOM даст значение аккурат от 0 до 2*max($RANDOM)=65534.

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

И тогда как верить значению бита, если оно взводится

Чо? Мы говорим о старшем бите в 16-разрядном числе. Он не взводится.

Чо? Мы говорим о старшем бите в 16-разрядном числе. Он не взводится.

Успокойтесь и давайте конструктивно. При арифметике (а не логике) старший бит выполняет функцию не результата, а переполнения, то есть он будет взведен чаще, чем в более расширенной разрядности в значещем бите стояло бы там 0.

Начнём с того, что в информатике (а не арифметике) старший бит в int выполняет функцию знака. Тогда всё становится логично — в стандарте написано, что rand() должен возвращать int, а не unsigned int, а поскольку работать с отрицательными случайными числами неудобно, отрицательный отменили.

Начнём с того, что в информатике (а не арифметике)

Начнём с того, что в информатике бывают логические и арифметические выражения. Арифметические могут давать результаты, которые не помещаются в разрядность. При сложении и вычитании старший бит действительно отражает знак если его так интерпретировать, это простое следствие из того, что при двоичной системе исчисления при сложении и вычитании результат не может превысить удвоенное значение максимума, потому переполнение можно интерпретировать как значащий бит при приведении результата вначале к безнаковому, а потом к расширенной битности. Но это всё не относится к умножению и делению. И так далее на несколько лекций. Мне это влом и неприятно, так как по умолчанию я предполагал, что это с Вами не требуется.

В большинстве слкчаев его достаточно (выбрать картинку из десяти)

Да. И кстати ещё забыл добавить. Тип возврата int там по причине вредной традиции сувать этот signed int дефолтно везде без раздумий, и традиция эта до сих пор не искоренена, хотя и стала сильно меньше (впрочем даже год назад на лоре кто-то мне доказывал что signed по дефолту это проактивно-хорошая идея). На самом деле там конечно же должен был быть тип возврата unsigned int.

И если в случае с rand() это породило всего лишь такой казус, то в некоторых других местах из-за этой антикварной привычки получались баги и уязвимости.

signed там потому что функция получается простая и удобная в использовании. Особо смешно, когда речь поднята о bash, где работа с unsigned - такой секс, что в гробу его все видали.

Так это не в баше signed rand() придумали, а в libc. Баша в те времена ещё не существовало скорее всего (а он вообще существовал в 16-битном виде?).

И ничего «простого и удобного» от этого signed (в Си) не добавляется.

Так это не в баше rand() придумали

А кто это говорил?

Баша в те времена ещё не существовало скорее всего

Ясен пень.

Вообще говоря, оставить 16-битный $RANDOM придумали в том числе и в bash, наверняка для совместимости с вероятно каким ksh, где в 16 бит оно таки было. Ибо в libc другого варианта кроме как RAND_MAX=INT_MAX никогда и не было и о совместимости там не пахнет.

И ничего «простого и удобного» от этого signed (в Си) не добавляется.

О да, долой отрицательные числа, они так неудобны!

О да, долой отрицательные числа, они так неудобны!

Так и есть. signed типы надо использовать только для математических (научных) вычислений (которые при этом почему-то не float/double), и для тех редких случаев когда тебе прямо точно нужны знаковые числа в этом месте. Дефолтным int-ом должен был быть unsigned, тогда бы кучи багов в софте из 70-х - 80-х не случилось.

Вы явно с (un)signed char путаете. Вот для них действительно никакого особенного смысла в дефолте на signed нет. Но это надо спрашивать у авторов процессора PDP, там нет (а ведь это целое семейство, куча кодов) инструкций для работы с unsigned char, компилятору приходилось вставлять следующей инструкцией сброс 8-го бита. А для (un)signed int нет никаких проблем со старым софтом кроме как завязанность на конкретное количество бит и равнозначность short=int, но эти проблемы значность никак не решит.

ну первое число - это 2 в 15 минус 1. предположу, что в эпоху 16-битных компьютеров оно появилось, где один бит из 16 зарезервирован для хранения знака.

Я ничего не путаю. Сувание знаковых типов туда, где знак не нужен - один из больших источников багов в старом софте. И дело не в ассемблере и архитектурах железа, дело в логике работы программы. Необходимость корявых проверок (i>=0 && i<limit) вместо нормальных (i<limit), при этом i>=0 часто забывают, неинтуитивно работающее переполнение (когда положительное число превращается в отрицательное вместо простого отброса старших бит числа), а если «повезло» с забытым -fno-strict-overflow то так вообще местами битый код на ровном месте.

Ну и не совсем баг, но наглядная демонстрация уродливости знаковых типов: компиляторы часто оптимизируют деление/умножение через сдвиги, и деление на 2 это сдвиг вправо на 1. В случае unsigned там будет действительно просто сдвиг (одна очевидная инструкция). В случае signed - бесполезная портянка с ветвлением, просто потому что нуб по гайдам из 80-х сделал где-то счётчик типа int.

Какое-то 50-летнее говно дидов помноженное на костыли и Legacy.

1. Ограничение до 16-bit signed из-за того, что int в те времена был 16-bit’ным: −32,768...32,767

2. Диапазон 0...32,767 вместо −32,768...32,767 выбран потому что с отрицательными случайными числами работать неудобно, их нужно было бы abs’ировать чтобы получить случайные числа внутри нужного диапазона. И распределение бы нарушилось? Хотя наверное нет.

3. Диапазон 0...32,767 вместо 65,535 т.е. int вместо unsigned выбран чтобы сохранить поддержку с дидовьем говнокодом, где int на int сидит и int’ом погоняет.

Вердикт:

1. Все распределения случайных тут – шиза, никак не коррелирующая с современностью.
2. Если бы Bash был нормальным скриптовым языком, а не говном, то там была бы версионность, где при использовании какого-нибудь #!/bin/bash3 шебанга этот $RANDOM перенаправлялся бы в rand() из libc, а не в их костыль.