[iiv 18]

Добрый день,

 

долго занимаясь вычислительной математикой прошел стороной сабж, и, к своему стыду, кроме x_{i+1}=(c+x_i*a)/b ничего не знаю...

 

Посоветуйте, пожалуйста, простой в вычислении генератор случайных чисел для такой задачи:

 

есть 2-3-4-...гиперкуб размерности n1*n2*...*nk

 

Мне необходимо получить в нем M псевдослучайных точек, так чтобы для всех гиперплоскостей n1*...*ni*...*nk было не менее [M/ni] и не более [M/ni]+1 точек, полагая, что [M/ni] больше 0, и [] - операция целое.

 

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

 

Очень желательно иметь еще возможность сгенерить такие M точек, а потом увеличить до M_+, и догенерить (M_+)-M оставшихся точек.

 

Хочу формулу или понятный алгоритм в виде блок-схемы, так как мне надо имплементировать его на CUDA, FPGA, и восьмибитнике, так чтобы не было использовано много памяти (не более 512 байт в восмибитнике, или 128 четырехбайтных слов в CUDA или один M9K в плиске). Из-за этого ограничения я не могу запомнить предыдущие сгенеренные точки и их использовать при вычислении следующих точек.

 

Как я понимаю, это очень распространенная задача для Монтекарловки, но, как-то на раз ничего хорошего ни на гуглить, ни на матскинетить я не смог.

 

Долго и упорно читать монографии и совеццкие книги - времени нет, да и мало вероятно, что там это есть.

 

Нужна идея, ссылка на статью по теме, или ссылка на описание похожего алгоритма.

 

Кто в теме, пожалуйста, посоветуйте!

 

Спасибо

 

ИИВ

[Major 0]

Не спец в МК, но заинтересовало следующее:

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

С какой вероятностью не отличается?

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

Если всегда не более чем на 1 с вероятностью 1, то это случайным не будет. Любой момент случайной величины(выборки) всегда случайная величина.

[Гость TSerg]

Что-то не пойму в чем проблема.

Используйте RNG на N точек в плотном диапазоне целых чисел, к примеру 0..10 на 11 чисел.

Затем масштабируете ( растягиваете ) на необходимый диапазон.

К примеру, для диапазона 0..1000 надо умножать очередное число на 100.

Получите случайные числа 0, 100, 200...1000.

P.S.

Если я правильно Вас понял.

[Dimidrol 0]

МБ как-нибудь это поможет. http://en.wikipedia.org/wiki/Xorshift

[Major 0]

Извиняюсь. Похоже я ТС не понял.

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

В МК важна независимость выборок. А так как они все случайные, то с вероятность 1 нельзя гарантировать разброс в 1 точку (в силу случайности).

 

[iiv 18]

А так как они все случайные, то с вероятность 1 нельзя гарантировать разброс в 1 точку (в силу случайности).

 

вот возьмем пару примеров

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

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

первых N точек мы будем аксептировать только те пары, которые появляются в в такой строке и столбце, в котором до этого ничего не было,

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

и так далее...

 

... а еще лучше, для многомерного случая...

 

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

[Major 0]

Я понял что вам надо. Но это скорее всего не имеет отношения к МК (я ошибочно на нем зацепился).

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

В этом смысле мне не понятно что имеется в виду под "получить хороших псевдослучайный генератор матриц перестановок".

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

 

Может вам нужны М-последовательности?

На периоде (после полного прогона) бинарной МП число единиц минус число нулей равно 1. Фабрика МП даст искомые вектора/матрицы.

 

 

[Гость TSerg]

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