powered by simpleCommunicator - 2.0.59     © 2025 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Случайный конь в вакууме
25 сообщений из 223, страница 3 из 9
Случайный конь в вакууме
    #39925733
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
если бы числовая ось была вещественная, то всю историю можно было бы видеть
как растяжение/сжатие с коэффициентом M/N

Пусть есть N чисел от n0 до n0+N
и M числе от m0 до m0+M
N<M

тогда
произвольный n(k) можно было преобразовать в
m0 + (n(k) + m0)*M/N
для целых я пока не вижу как сделать идеально гладкое преобразование...

зачем идеально гладкое, обычное округление приведет к тому что надо
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925742
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Leonid Kudryavtsev
Т.е. вспомогательный рандом явно не нужен, но нужно хранить накопленный остаток от пред. последовательности


Ну вот тоже об этом думаю. Непонятно, как применить остаток.

Вот так идеальное распределение получается
Результат
Код: plaintext
989855744: 0.1667 0.1667 0.1667 0.1667 0.1667 0.1667

Код: plaintext
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
#define N 10
#define M 6

int my_rand() {
	static int sum = 0;
	sum = (sum + rand() % N + rand() % N) % M;
	return sum;
}

void test_rand() {
	
	int arr[M] = {0};
	for (int i = 1; i < 1000000000; i++) {
		if ((i & 0xFFFFFF) == 0) {
			printf("\r%d: ", i);
			for(auto &x : arr) printf("%0.4f ", (double)x / i);
		}
		arr[my_rand()]++;
	}
}


Я не могу объяснить как это работает, но оно работает на любых парах (N, M)
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925745
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby,
кхе
...
m0 + (n(k) - n0)*M/N
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925746
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T,

хороший программист :)
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925749
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ViPRos
...
зачем идеально гладкое, обычное округление приведет к тому что надо

обычное неравномерно на пятерке.
что-то типа "банковского" для "достаточно длинных" диапазонов.
на малых диапазонах края останутся неравномерно заполненными.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925757
ViPRos
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
ViPRos
...
зачем идеально гладкое, обычное округление приведет к тому что надо

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

я думаю, этого хвосту будет достаточно
А так все это можно сделать точнее, конечно
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925762
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
ViPRos,

точнее и для произвольной пары целочисленный последовательностей,
это, если на бегу, то заветы Имя пользователя1
надо использовать со вторым генератором.
например
M<N
тогда первые M из последовательности [N] мапятся 1:1 на последовательность [M]
а оставшиеся (N-M) распределяются случайным генератором.
может какая-то схема равномерного распределения остатка и есть,
но с разбегу не вижу подходящего косоугола.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925763
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T,

double - не наш метод!
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925765
booby
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby,
впрочем, для N-M можно держать последнюю использованную позицию,
и использовать всегда следующую с циклом по модулю M
вот.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925766
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
вариант со вспомогательным рандомом, который иллюстрируется картинкой 22078294


Код: javascript
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
function mapNtoM(x, n, m) {
    if (x === 0) return 0;
    var ratio = m / n;
    if (n % m === 0) return Math.floor(x * ratio);
    var fx = x / n;
    var fmax = (x + 1) * ratio;
    var fmin = x * ratio;
    var max = Math.ceil(fmax) - 1;
    var min = Math.floor(fmin);
    if (min === max) return min;
    var r = (x + Math.random()) / n;
    var destFMin = (min + 1) / m, destFMax = max / m;
    if (r < destFMin) return min;
    if (r >= destFMax || max - min === 1) return max;
    return min + 1 + Math.floor((r - (destFMin - fx)) / (max - min));
}

result = 2 + mapNtoM(x, 10, 6); // для кейса из примера




тест на распределение https://jsfiddle.net/6xkz7tap/
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925768
iOracleDev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt
Во! А нужно хоть какое-то вшивое доказательство )

Опровергнуть применимость метода циклической прокрутки меньшего массива можешь? Если не можешь, зачем завел топик о том в чем совершенно не разбираешься?))

PS: тут математик нужен, техник-программист для решения подобных задач не пригоден
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925769
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T

Код: plaintext
1.
	sum = (sum + rand() % N + rand() % N) % M;



Тут - математическая ошибка. Нельзя складывать случайные распределения. Это меняет их форму.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925772
Dima T
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton
Dima T

Код: plaintext
1.
	sum = (sum + rand() % N + rand() % N) % M;



Тут - математическая ошибка. Нельзя складывать случайные распределения. Это меняет их форму.

Есть подозрение что это работает из-за какой-то особенности ГПСЧ в С++. Надо в других ЯП затестить.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925778
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
iOracleDev
Опровергнуть применимость метода циклической прокрутки меньшего массива можешь? Если не можешь, зачем завел топик о том в чем совершенно не разбираешься?))


У меня щас когнитивный диссонанс случился.
Если не можешь, зачем завёл топик?
А если можешь, нафига завёл топик?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925779
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Не надо тестить. Ты получишь Гауссово распределение если сделаешь таких штук 20 сложений.

На двух - незаметно. Но форма уже меняется.

Представь что мы с тобой играем в кости на сумму.

И я регулярно ставлю на то что сумма равна 6 или 7 и выигрываю.

Ты - можешь ставить на любое число и с большей вероятностью проиграешь.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925786
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
booby,
впрочем, для N-M можно держать последнюю использованную позицию,
и использовать всегда следующую с циклом по модулю M
вот.

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

а здесь, есть очень большое опасение, что
mayton

Нельзя складывать случайные распределения. Это меняет их форму.


Но, с другой стороны, даже если "форма" портится, то мы всегда можем "перепортить" ее обратно в нужную

т.ч. дальше нужно сидеть за листочком бумаги и выводить формулы

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

Тут математик нужен
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925788
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
Не очень понятно практическая ценность данной задачи, т.е. бюджет на решение


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

Касательно приведённых статей, конечно же определённое распределение и вероятность, это немного разные задачи.


Leonid Kudryavtsev
Как мне кажется (доказать не возьмусь) - напрмер можно просто лишние числа выкидывать.


Это вынес в исключение к задаче.


Leonid Kudryavtsev
Если задачу делать чисто теоретически-дискретной, то я бы предложил 0...9 заменить на 0 / 1, мы же все же программисты ))) и живем в эпоху цифровой техники ))))


Ну можно на биты разложить. И получать на входе случайные биты. Что никак не противоречит задаче.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925789
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
booby
m0 + (n(k) + m0)*M/N
для целых я пока не вижу как сделать идеально гладкое преобразование...


Для целых мы получим разные вероятности, ага (
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925790
Leonid Kudryavtsev
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
hVostt

Если не можешь, зачем завёл топик?
А если можешь, нафига завёл топик?

совершенно верно

Что бы правильно задать вопрос, нужно знать 90% ответа. ( C ) народная мудрость

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

а так, какой-то вброс и очередное изобретение квадратуры круга с требованием математического доказательтва
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925792
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev

Но, с другой стороны, даже если "форма" портится, то мы всегда можем "перепортить" ее обратно в нужную

Я рассматриваю также это как некую криптографическую уязвимость которая позволяет делать прогнозы
относительно SUM. Из просто случайных они становятся ... более закономерными что-ли. Дальше - куда нас
заведет логика задачи. Предсказывать следующее значение?

Или может вообще в топике мы просто проектируем очередной линейный конгруэнтный генератор
только сами еще этого не поняли.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925794
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Dima T
Есть подозрение что это работает из-за какой-то особенности ГПСЧ в С++.


Нужно брать аппаратный. Например CryptGenRandom .
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925798
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
Что бы правильно задать вопрос, нужно знать 90% ответа. ( C ) народная мудрость


Я знаю как проверить, провести эксперимент как минимум.
Если будет доказательство, могу и над ним посидеть.
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925799
Фотография Имя пользователя1
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
давайте ещё раз уточним, что именно требуется.

на вход поступает некое случайное число 0...9, надо на выход отдать 2...7

поскольку входное число равновероятное, то мы могли бы плюнуть на него и просто вернуть 2 + floor(random() * 6). Это число было бы равновероятным 2...7, только независимым от входа.

но мы хотим, чтобы результат зависел от входа, и даже одноразовое применение давало равную вероятность. Так?
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925801
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Leonid Kudryavtsev
Топик какой-то наброс на вентелятор. Или опиши _реальную_задачу_ или запишись в детский(или не очень) клуб любителей математики (из тех, что по математическим олимпиад ездят) и задай вопрос преподавателю )))

а так, какой-то вброс и очередное изобретение квадратуры круга с требованием математического доказательтва


Извините, но ни о чём. Это задача для ума. Если вам такое решать не интересно, то я не навязываю :)
...
Рейтинг: 0 / 0
Случайный конь в вакууме
    #39925808
Фотография hVostt
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Имя пользователя1
на вход поступает некое случайное число 0...9, надо на выход отдать 2...7


Это для примера.
Лучше конечно обобщить.
Приходит [0..N), с равной вероятностью получения любого из значений.
Нужно получить [M0..M1], или [0..M) (не так важно на самом деле).

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

Вероятность получения любого значения на диапазоне [0..M) должна быть одинаковая.
...
Рейтинг: 0 / 0
25 сообщений из 223, страница 3 из 9
Форумы / Программирование [игнор отключен] [закрыт для гостей] / Случайный конь в вакууме
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]