Результаты для каждого окружения будут разные, в общем случае можно составить такую зависимость при обращении к одному значению Код (Text): страницы 4Кб линии 32б линии 32б HDD -------------------> RAM -----------------> L2 ---------------> L1 10000-100000 тактов 1000-10000 тактов 10 - 100 тактов Обычно от этого отказываются, если не возможно держать всю таблицу в L1
bogrus Насчет L1, это слишком Все определяется соотношением времени расчета и вытаскивания значения из того или иного уровня памяти. Таблица должна быть в L1, если нужно время вытаскивания в несколько тиков. В рассматриваемом случае речь идет о полусотне тактов расчета Range или 100-150 тактов для Number. А эта величина как раз сравнима с временем подгрузки линейки кэша из ОЗУ. Поэтому принципиальным вопросом здесь является то, как использовать вычисленные значения number. Если они будут читаться подряд одно за другим, то это одно дело и можно использовать достаточно большую таблицу. Если же в случайном порядке, то использовать таблицы более нескольких размеров L2 не имеет никакого смысла.
Мда? Разве? Имеем: Seed: E33DAD5B Seed: 05D688D7 Они оба дают одинаковое значение генератора. Как они связаны? Вообще говоря, я был малость не прав. Дело все в том, что 2^32 и m не являются взаимно простыми. Поэтому результат вычислений (a*b+1) mod m и (a*b+1) mod 2^32 mod m будет, вообще говоря, различным... Если все вычисления рассматривать mod 2^64, то да - все сводится к стандартному умножению.
aSL Разумеется я имел ввиду вычисление seed стандартными imul и idiv c 64-битным промежуточным результатам в EDX:EAX. Поэтому имхо mult это просто извращение под С для работы с 32-бит переменными. Насчет отрицательных seed действительно не все ясно. И непонятка тут заключается в типах переменных: входные long, а промежуточные unsigned long (эту фишку я поначалу и не приметил). Не знаю как тут поступает C, а вот в дельфях результат операции расчитывается исходя из типа операндов (в данном сл.как long, т.е imul, idiv) и только затем присваивается переменной результата - если влезает в диапазон, то OK, если нет, то exception при вкл.RangeCheck или скрытая ошибка в проге если выкл. Что будет в данном сл.при вычислении p1 и p0 при отрицательном p - вопрос. Но последующие вычисления уже производятся с unsigned (т.е. mul,div) поэтому в любом сл. результат mult лежит в диапазоне 0..m-1 А чего это volodya пропал ? Ему вопрос о допустимости начального seed < 0 уже не раз задавали - "а в ответ тишина - он вчера не вернулся из боя" )
Да ладно, фиг с ним со знаком - будем считать что его нет Можно сократить число умножений до 4 без всякой разбивки на части если по аналогии с методом обратного делителя использовать целочисленное представление (b/m)*2^x и (range/m)*2^y. Тогда вычисление NextRandomNumber может выглядеть так Код (Text): m = 100000000 b = 31415821 range = 256 ;unsigned long NextRandomNumber(unsigned long* seed); stdcall ;--------------------------------------------------- mov eax,[esp+4] ;*seed push ebх push edi push esi push ebp mov ebx,[eax] ;seed xor edi,edi ;result mov esi,4 ;счетчик _loop: mov eax,ebx mov ecx,506CAC25h ;[(b/m)*2^32] mul ecx mov ebp,edx ;[seed*b/m], для 2^32 сдвиг edx не нужен mov eax,ebx mov ecx,b mul ecx mov ebx,eax ;мл.дворд seed*b для выч.остатка mov eax,ebp mov ecx,m mul ecx ;eax = мл.дворд [seed*b/m]*m add ebx,1 ;seed*b+1 shl edi,8 ;сдвигаем result (n1<<24)|(n2<<16)|(n3<<8)|n4 sub ebx,eax ;остаток = новый seed (достаточно вычесть младшие дворды) <font color="grey] ;--- исправление 1) эту фигню убираем вообще: пусть будут seed и seed+m ;cmp ebx,m ;jne _OK ;xor ebx,ebx ;_OK: ;-----------------</font><!--color--> mov eax,ebx <font color="grey];--- исправление 2) нужно брать число на 1 больше: 0ABCC7712h, а не 0ABCC7711h</font><!--color--> mov ecx,0ABCC771[b]2[/b]h ;[(range/m)*2^(32+18)] ;----------------- mul ecx shr edx,18 ;*2^(-18) <font color="grey];--- исправление 3) добавляем коррекцию range, т.к. здесь м.б. seed >= m</font><!--color--> and edx,0FFh ;----------------- or edi,edx ;копируем в result _next: sub esi,1 jnz _loop mov ecx,[esp+20] ;*seed mov eax,edi ;result <font color="grey];--- исправление 4) добавляем коррекцию seed, если нужно</font><!--color--> sub ebx,m jge _OK: add ebx,m _OK: ;---------------- mov [ecx],ebx ;seed pop ebp pop esi pop edi pop ebx ret 4 На P3 получается порядка 110 тиков против 140 при разбивке на 16 бит Lo\Hi, а на P4 Northwood (без HT) 210 против 430. Для сравнения: простой дубовый метод с mul+div для seed и fmul+fistp для range дает 200-220 тиков на P3 и 320-360 на P4 - в соответствии с прогнозом гидрометцентра PS: была шальная мысля еще одно умножение выкинуть, если считать остаток как произведение дробной части на m. Но к сожалению 32-битной точности представления b/m не хватает, а на fpu получается дольше из-за медленных frndint или fistp+fisub.
Ну, в принципе, да. После первой итерации NextRandomRange получим уже число "без знака". Завтра проверю код на "повторяемость".
В моем первозданном варианте закралась пара ошибочек: выбранные множители иногда занижают результат на единичку. Лечится это так. Множитель (r/m) достаточно просто увеличить на 1, т.е. брать 0ABCC7712h. Скорректировать множитель (b/m) не получается, да и фиг с ним, т.к. есть еще более простой вариант. Множитель 506CAC25h в проценте случаев занижает результат умножения и в итоге seed оказывется = seed+m, ну и ладно, т.к. на последующие вычисления seed это не влияет, а range легко скорректировать простым and edx,0FFh. Если выходное значение seed должно быть от 0 до m-1, то можно добавить коррекцию на выходе из процедуры: если seed >= m, то вычитаем m. Шоб не занимать места, внес указанные исправления в первоначальный вариант (см.выше). Работает по кр.мере для всех неотрицательных seed (0..7FFFFFFFh) Вот вариант аналогичной реализации на SSE2: Код (Text): align 16 ;!!! если не выравнено, то нужно заменить загрузку с movdqa на movdqu prngm1: dd 506CAC25h, 0ABCC7712h, b, 0 ;(b/m)*2^32, (r/m)*2^(32+18), b, 0 prngm2: dd m, 255,1,0 ----------------------- ;unsigned long NextRandomNumber(long* seed); stdcall ;--------------------------------------------------- mov edx,[esp+4] ;*seed movd xmm1,[edx] ;dd0=seed movdqa xmm2,[prngm1] ;dd0=bm,dd1=rm,dd2=b,dd3=0 movdqa xmm3,[prngm2] ;dd0=m, dd1=FF,dd2=1,dd3=0 pxor xmm0,xmm0 ;result pshufd xmm4,xmm2,0FDh ;=11111101b -> dd0=rm,dd1-dd3=0 mov ecx,4 _loop: punpcklqdq xmm1,xmm1 ;dd0=seed,dd1=0,dd2=seed,dd3=0 pmuludq xmm1,xmm2 ;dq0=seed*bm (dd0=fraq,dd1=int), dq1=seed*b pslld xmm0,8 ;сдвигаем result pshufd xmm5,xmm1,1 ;dd0=int(seed*bm) остальное мусор pmuludq xmm5,xmm3 ;dq0=[seed*bm]*m paddq xmm1,xmm3 ;dq0=мусор, dq1=sid*b+1 punpckhqdq xmm1,xmm1 ;dq0=sid*b+1,dq1=sid*b+1 psubq xmm1,xmm5 ;dd0=seed*b-[seed*bm]*m = остаток movq xmm5,xmm1 ;dd0=new seed pmuludq xmm5,xmm4 ;dq0=seed*rm, dq1=0 psrld xmm5,18 ;dd0=мусор,dd1=number,dq1=0 pand xmm5,xmm3 ;коррекция dd1=number and 255 por xmm0,xmm5 ;dd0=0,dd1=result,dd2=dd3=0 sub ecx,1 jnz _loop movd ecx,xmm1 ;seed (0..2*m-1) pshufd xmm1,xmm0,1 ;dd0=number movd eax,xmm1 sub ecx,m ;коррекция seed jge _OK ;возможен штраф +15-20 тиков за непредсказ.прыжок - около 1% всех seed add ecx,m _OK: mov [edx],ecx ;seed (0..m-1) ret 4 Результаты неплохие, но опять же неоднозначные - на P4 Northwood значительно лучше, а вот на Pentium M получается чуть хуже чем предыдущий вариант с умножением на 32бит регистрах: Код (Text): Проц mul-16 mul-32 SSE2 <-- метод ---- ------ ------ ---- P3 140 110 - PM 130 95 110(120) P4 430 210 140(160) В скобках с учетом штрафа за непредсказанный переход при коррекции seed (по идее ее можно и не делать или делать чуть длиннее без jcc, хотя вроде вероятность на уровне процента - не стоит свеч)
aSL стукнул в мыло, не зная чем аукнется Такой налет таинственности на "конкретных деталях применения" - лишнего слова из вас с volodya не вытянишь )
