Генератор случайных чисел, для многомерной монтекарловки (monte carlo simulation/integration) Опции

[iiv]

Добрый день,

долго занимаясь вычислительной математикой прошел стороной сабж, и, к своему стыду, кроме 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]

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

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

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

[Guest_TSerg_*]

Что-то не пойму в чем проблема.
Используйте RNG на N точек в плотном диапазоне целых чисел, к примеру 0..10 на 11 чисел.
Затем масштабируете ( растягиваете ) на необходимый диапазон.
К примеру, для диапазона 0..1000 надо умножать очередное число на 100.
Получите случайные числа 0, 100, 200...1000.
P.S.
Если я правильно Вас понял.

[dm.pogrebnoy]

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

[Major]

Извиняюсь. Похоже я ТС не понял.
Ему не надо Монте-Карло, ему нужен генератор расстановки и похоже случайность его не интересует в смысле МК.
В МК важна независимость выборок. А так как они все случайные, то с вероятность 1 нельзя гарантировать разброс в 1 точку (в силу случайности).

[iiv]

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

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

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

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

[Major]

Я понял что вам надо. Но это скорее всего не имеет отношения к МК (я ошибочно на нем зацепился).
Подобный селективный отбор пар(векторов) вносит зависимость (корреляции), что приведет к смещению вычисления результатов в методах МК.
В этом смысле мне не понятно что имеется в виду под "получить хороших псевдослучайный генератор матриц перестановок".
Какие статистические тесты должны выполняться и на каких уровнях значимости, на какой длине выборки?

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

[Guest_TSerg_*]

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