Пытаюсь упростить следующую задачу: На входе имеем произвольное 64-битное число. Вычисляем кол-во единиц в двоичном представлении данного числа тем самым классическим безбранчевым методом, что описан в Уоррене. Кол-во единиц обозначим символом n. Далее используем генератор случайных чисел, чтобы получить число в промежутке [0, n - 1]. Обозначим это число символом m. Возвращаем позицию m-ной единицы во входном 64-битном значении. Вот и всё. Таким образом, имеем "продвинутый" ГСЧ с распределением, отвечающим требованиям какой-то другой задачи (общую задачу приводить, думаю, не стоит, т.к. это будет отдельная тема, возможно) и диапазоном [0, 63]. Как видите, задача на данном этапе решается в 3 шага. Есть мнение, что можно организовать аналогичный ГСЧ более простым образом. Теперь более конкретный вопрос Как бы соптимизировать 3й шаг, т.е. вычисление позиции m-ной единицы. В Уоррене есть алгоритм подсчёта ведущих нулей, т.е. вычисление позиции первой единицы в заданном числе, но мне нужна не первая, а m-ная... Инструкция bsf тоже ищет именно пурвую единицу и есть подозрение, что в x64 этой инструкции уже нет.
Quantum У меня есть подозрение, что если числа на входе и m распределены равномерно, то в выходной последовательности тоже будут равномерно распределённые числа. Зачем тебе такой навороченный генератор равномерно распределённых чисел?
Black_mirror m выдаёт генератор с равномерным распределением (конкретно Mersenne Twister). 64-битное число на входе берётся не из ГСЧ, а подбирается таким образом, чтобы распределение комплексного ГСЧ максимально приближалось к некоторой полиномиальной функции. Таким образом, правильно подобрав это ключевое число можно получить ГСЧ с практически любым распределением и без лишних затрат на арифметику. "Точность" аппроксимации зависит от разрешения ключевого слова (пока 64 бит, но можно повысить и до 128 бит и т.д.)
EvilsInterrupt Спасибо! В качестве первичного ГСЦ вполне годится даже сишный random(). Наиболее критичным вопросом пока остаётся 3й шаг, т.е. вычисление позиции заданной единицы в 64-битном числе. bsf для этой цели совсем не рулит.
Quantum Первая версия не пригодная для практического применения: Код (Text): bitm: mov ebx,eax shr ecx,1 adc ebx,ebx xor ebx,eax lea edx,[ebx*4] xor ebx,edx imul edx,ebx,$10 xor ebx,edx imul edx,ebx,$100 xor ebx,edx imul edx,ebx,$10000 xor ebx,edx and eax,ebx lea ebx,[eax-1] test eax,ebx jnz bitm bsf eax,eax ret На входе eax - число, ecx - m, результат в eax.
Табличный метод: Код (Text): bitm: xor eax,eax mov ebx,bit_count mov edx,esi .l0: lodsb sub cl,[ebx+eax] jge .l0 add cl,[ebx+eax] sub esi,edx movzx eax,byte [bit_index+eax*8+ecx] lea eax,[eax+esi*8-8] ret bit_count:;256 байт repeat 256 v = %-1 v = (v and $55) + ((v shr 1) and $55) v = (v and $33) + ((v shr 2) and $33) db (v and 15) + (v shr 4) end repeat bit_index: ;256*8=2Кб repeat 256 v = %-1 repeat 8 n=% c = 0 repeat 8 if v and (1 shl (%-1)) n=n-1 if n else c=(%-1) end if else end if end repeat db c end repeat end repeat esi - указатель на число, ecx - m (не более 255), результат в eax.
Black_mirror Извини, что сразу не ответил, но у меня пол дня ушло, чтобы осмыслить второй код Сильно! Коммерческое применение этого алгоритма пока не планируется, но, возможно, будет статья в каком-нибудь научном издании и я позабочусь, чтобы твой копирайт сохранился. Спасибо большое! EvilsInterrupt В принципе, период всегда меньше или равен диапазону (2 exp n - 1, n - кол-во бит в сиде). Если в сиде меньше бит, то период заявлен с завышением.
Изменив немного код и таблицу можно выкинуть одну команду: Код (Text): bitm: xor eax,eax mov ebx,bit_count mov edx,esi .l0: lodsb sub cl,[ebx+eax] jge .l0 ;здесь был [b]add[/b] sub esi,edx movzx eax,byte [bit_index+eax*8+ecx[b]-248[/b]] lea eax,[eax+esi*8-8] ret ;таблица bit_count не меняется bit_index: ;256*8=2Кб repeat 256 v = %-1 repeat 8 n = [b]8-%[/b] c = 0 repeat 8 if v and ([b]$80 shr (%-1)[/b]) if n else c=[b]7-(%-1)[/b] end if n=n-1 else end if end repeat db c end repeat end repeat Quantum Я так и не понял что происходит с 64х битным числом, оно просто является параметром генератора или каким либо образом меняется при каждом вызове? Что за полиномиальная функция к которой приближается распределение? Если в 64х битном числе один из битов нулевой то на выходе просто не будет чисел равных его индексу. Или в интервале [0,63] некоторые значения могут вообще отсутствовать?
Black_mirror Это число подбирается, чтобы распределение имело нужную форму (Гауса, Пуассо с некоторым параметром ламбда, фрактальную и т.д.). Обычно, она задаётся один раз (в самом начале) и не изменяется для каждого этапа. Распределение зависит от плотности и количества единиц на каждом этапе данной формулы. Я назвал эту функцию полиномиальной, потому что 64-битное число - это полином с коэффициентами от 0 до 63. К примеру, если все биты установлены, имеем равномерное распреление (при условии, что первичный ГСЧ имеет равномерное распределение). Верно. Можно сказать, что эти значения имеют вероятность = 0, если данное число константно. Теоретически это не совсем правильно (нулевая вероятность не должна означать, что значений не будет вообще), но на практическую сторону задачи этот факт никак не отражается.
