Генератор списка случайных чисел по коду

← →
MasterKolyan (2004-02-25 15:10) [0]

Hi coder"s! {Пожалуйста!!! помогите начинающему мастеру}Я хотел создать генератор случайных чисел по заданному коду (каждый код должен генерировать только один список случайных чисел). Это сделать было очень просто, но передо мной встала задача быстрого извлечения из этого генератора чисел по их порядковому номеру. Я реализовал такой генератор, но работает очень медленно(с частотой 2 МГЦ на компе 733МГЦ). Сравнительные характеристики стандартного Random-а: 20МГЦ. А памяти: 324МГЦ.

вот мой генератор:
function myrandom(number: integer): extended;
begin
asm
push eax;
push ebx;
push ecx;
push edx;
push esi;
push edi;//Запомнить значения регистров

mov eax, $08088405;
mov ebx, number;
mov esi, code;//Code: integer - это код
add esi, ebx;
mov edi, $ffffffff;
mov edx, 32;
@0: dec edx;
mov ecx, edx;
jecxz @2;
imul esi, eax;
inc esi;

sal ebx, 1;
jae @0;
xor edi, esi;
not edi;
jmp @0;
@2:
mov [ebn], edi;
pop edi;//Вернуть на место значения регистров
pop esi;
pop edx;
pop ecx;
pop ebx;
pop eax;

end;
result:=(ebn/$ffffffff);
end;

Очень хотелось бы получить у ВЕЛИКИХ МАСТЕРОВ простенький ассемблерный код подобного генератора, который бы работал чуть по быстрее.

P.S. Такой генератор можно использовать например в генераторе случайных поверхностей ....... экономия памяти однако... и скорости(если оперативка слабая).

Извиняюсь что шрифт один и тотже: Message(JavaScript Alert, под NN не работает!)

← →
SPIRIT (2004-02-25 15:24) [1]

А ф и г е т ь

← →
MasterKolyan (2004-02-25 15:31) [2]

А чо непонятно чтоли :)

← →
Defunct (2004-02-25 16:02) [3]

Пожалуйста, будет работать как минимум в 8 раз быстрее:

function myrandom(number: integer): extended; var Ebn : Dword; begin asm push eax; push ecx; push esi; push edi; mov eax, $08088405; mov esi, code;//Code: integer add esi, number; mov edi, $ffffffff; mov ecx, 8; @0: imul esi, eax; inc esi; xor edi, esi; not edi; loop @0 mov [ebn], edi; pop edi; pop esi; pop ecx; pop eax; end; result:=(ebn/$ffffffff); end;

Если нужно еще сильнее ускорить, уменьшите число циклов
Mov ecx,4

← →
Defunct (2004-02-25 16:17) [4]

Ps: если поменять местами регистры eax, esi (т.е. в eax загнать code+number, а в esi - константу) - будет работать еще быстрее, т.к. большинство команд x86 с eax выполняются быстрее, чем с другими регистрами.

цикл тогда примет вид:
@0: imul esi, eax; inc eax; xor edi, eax; not edi; loop @0

← →
MasterKolyan (2004-02-25 16:24) [5]

ха-ха. При уменьшении числа циклов теряется всякая случайность. Хочешь проверить - нарисуй на этом генераторе двумерную картинку на экране, и посмотри.

← →
default (2004-02-25 16:28) [6]

MasterKolyan (25.02.04 16:24) [5]
что значит теряется случайность?
её вообще нет в природе, просто не имея достаточной инфы об чём-то это что-то считают случайным или просто так удобней...
откуда генератор взял?
у Кнута посмотри во втором томе про генераторы...

← →
MasterKolyan (2004-02-25 16:31) [7]

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

← →
MasterKolyan (2004-02-25 16:35) [8]

генератор я сам написал, голова хорошо работает, да и в Delphe есть такая фишка: можно прогу смотреть как Delphi её откомпилировала в ассемблерном коде построчно.
И кто такой Кунт и как книга называется, хочу почитать

← →
Defunct (2004-02-25 16:40) [9]

> ха-ха. При уменьшении числа циклов теряется всякая случайность. Хочешь проверить - нарисуй на этом генераторе двумерную картинку на экране, и посмотри.

При 8 работает нормально, сгенерил картинку, вроде повторений нет, тем более наглядных.

procedure TForm1.Button4Click(Sender: TObject); Var I,J:Integer; begin For I := 0 To Image1.Width Do For J := 0 To Image1.Height Do With Image1.Canvas Do Pixels[i,j] := MyRandom(J*Image1.Width + I); end;

Тока MyRandom возвращал у меня не Extended, а сразу TColor.

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

← →
MasterKolyan (2004-02-25 16:54) [10]

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

← →
Defunct (2004-02-25 16:58) [11]

да это я заметил, но вот при 7-ми уже ничего не видно, а при 8-ми тем более.

← →
MasterKolyan (2004-02-25 17:01) [12]

ты чегото про книгу какую-то говорил. чо за книга-то?

← →
default (2004-02-25 17:06) [13]

яндекс рулит)
ты хоть скажи на чём основан твой алгоритм?
а то я думаю(разубели меня) что ты методом тыка перепробовал куча комбинаций xor-ов, not-ов и тд и тп и остановился на такой которая больше всех понравилась(типа случайна она!)
а обсуждать оптимизацию не пойми чего тоже нет желания

← →
Defunct (2004-02-25 17:07) [14]

Вот вариант который даже при 2-х итерациях избавляется от зависимости от константы:

mov ecx, 2; @0: xor esi,edi mul esi xor edi, eax; not edi; loop @0

← →
MasterKolyan (2004-02-25 17:14) [15]

алгоритм(исходный (я с него начинал)): берётся небольшой массив (A) с заранее закинутыми туда числами(это можно назвать кодом генерации). Представим номер случайного числа в двоичном виде (1010011101) и за xor-м все элементы массива (A) которым соответствует единица((1010011101)) и получим случайное число.

← →
Defunct (2004-02-25 17:23) [16]

Да алгоритм и так был понятен из ассемблерного кода. Тока вот реализован не очень красиво. Особенно команды jecxz, и лишняя jea проверка, которая при sal особой случайности не добавит.

В общем, мне в отличие от default все равно какой код оптимизировать, цель ясна - нужно чтобы быстро генерировалась разная ерунда, вот она и генерируется [14].

← →
Defunct (2004-02-25 17:30) [17]

default © (25.02.04 16:28) [6]
что значит теряется случайность?
её вообще нет в природе, просто не имея достаточной инфы об чём-то это что-то считают случайным или просто так удобней...

Позвольте с Вами не согласиться, после выполнения:

Xor Ax,Ax Int 1Ah

В регистре DX - "несуществующая в природе" случайность. Причем в явном виде.

← →
MasterKolyan (2004-02-25 17:38) [18]

Wao super. You MASTER..... Нуу я в ассме не ас, в отличие от тебя. А у тебя лучше получилось. Хотя можно еще немного поработать...
Благодарю за столь детальное рассмотрение моего вопроса.....
P.S. I"am by back.

← →
MasterKolyan (2004-02-25 17:46) [19]

функция MyRandom уже работает с частотой 3 МГЦ. Кто больше!

← →
default (2004-02-25 17:56) [20]

Defunct © (25.02.04 17:30) [17]
но "почему-то" именно определённое значение появится там(наверно...), не с проста...для нас это конечно случайность...
[16]
просто может рез-та который ему нужно можно достичь более просто(более быстрым и коротким кодом)...скажи умножать-то там зачем?

← →
Defunct (2004-02-25 18:12) [21]

MasterKolyan (25.02.04 17:46) [19]
Почему только 3?
Там 16-ти кратное ускорение должно быть.
Может, описать функцию как

function MyRandom(...);Extended;assembler; asm .. End;

чтобы не было лишних дерганий стека.

default © (25.02.04 17:56) [20]
эх.. это уже философия... закономерность и случайность..

← →
default (2004-02-25 18:14) [22]

рег-ры EAX, ECX, EDX можно не сохранят в стеке...

← →
MasterKolyan (2004-02-25 18:14) [23]

умножение я взял из откомпилированного Delphi random-а:
функция Random(стандартный):
push ebx xor ebx,ebx imul edx,[edx+RandSeed],$08088405 inc edx mov [ebx+RandSeed],edx mul edx mov eax,edx pop ebx ret
mov eax,eax

← →
MasterKolyan (2004-02-25 18:16) [24]

незнаю почему 3МГЦ, наверное прогу не циклы тормозили

← →
MasterKolyan (2004-02-25 18:21) [25]

Defunct © (25.02.04 18:12) [21]
как тогда значение типа Extended возвращать?

← →
Defunct (2004-02-25 18:23) [26]

default © (25.02.04 17:56) [20]
просто может рез-та который ему нужно можно достичь более просто(более быстрым и коротким кодом)...скажи умножать-то там зачем?

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

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

← →
Defunct (2004-02-25 18:25) [27]

MasterKolyan (25.02.04 18:21) [25]
Точно также, тока вместо мифической переменной Ebn, использовать Result. А асме тоже можно выполнить деление пл. запятой:

FDIV ...

← →
DVM (2004-02-25 18:26) [28]

Нельзя по-настоящему случайное число сгенерировать по каким-то пусть очень даже сложным формулам. Есть формула -есть закономерность среди случайных чисел. Только привлечение физических процессов к генерации даст случайное число в чистом виде.

← →
Digitman (2004-02-25 18:27) [29]

> А памяти: 324МГЦ

это впечатляет)

← →
Defunct (2004-02-25 18:32) [30]

> DVM © (25.02.04 18:26) [28]

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

← →
MasterKolyan (2004-02-25 18:36) [31]

Defunct
Поздравляю 80МГЦ

← →
MasterKolyan (2004-02-25 18:39) [32]

MasterKolyan (25.02.04 18:36) [31]
Упс ошибочка не 80 а 8МГЦ всего)

← →
Defunct (2004-02-25 18:50) [33]

Последнее, что я могу предложить: выбросить цикл и просто продублировать код:

xor esi,edi mul esi xor edi, eax; not edi; xor esi,edi mul esi xor edi, eax; not edi;

← →
MasterKolyan (2004-02-25 18:55) [34]

← →
MasterKolyan (2004-02-25 18:59) [35]

function myrandom(number: Longword): Longword;assembler; asm push esi; push edi; mov eax, $08088405; mov esi, code;//Code: integer add esi, number; mov edi, $ffffffff; ///////////// xor esi,edi mul esi xor edi, eax; not edi; xor esi,edi mul esi xor edi, eax; not edi; ///////////// mov [result], edi;//Почему-то эта строка возвращает мне левый result(не меняющийся) { mov result, edi;//а так вообще не пашет } pop edi; pop esi; end;

← →
Defunct (2004-02-25 20:03) [36]

Вот такой будет ваша функция:

function myrandom(number: integer): Cardinal; Assembler; asm mov esi, $08088405; add eax, code;//Code: integer mov edi, $ffffffff; xor esi,edi mul esi xor edi, eax; not edi; xor esi,edi mul esi xor eax, edi end;

EAX - на входе Number, а т.к. резултат Dword, то результат передается через EAX.

Кстати, походу оптимизации Вашей функции наткнулся на конкретный баг в компиляторе Delphi: Delphi время от времени вставляет такие команды: MOV EAX,EAX!!!!!!!

С ума сойти.. оптимизатор называется..

← →
Defunct (2004-02-25 20:06) [37]

PS: мона сразу сделать чтобы возвращался RGB цвет:

function myrandom(number: integer): Cardinal; Assembler; asm mov esi, $08088405; add eax, code;//Code: integer mov edi, $ffffffff; xor esi,edi mul esi xor edi, eax; not edi; xor esi,edi mul esi xor eax, edi shr eax,8 end;

← →
Тимохов (2004-02-25 20:07) [38]

> Defunct © (25.02.04 20:03) [36]

Я чессо слово не знаю асм совсем (только cpu могу как-то с трудом понимать), но сделаю предположение, что mov eax,eax делается для какого нибудь выравнивания.

← →
Defunct (2004-02-26 02:17) [39]

Задача мне понравилась. продожаем оптимизировать дальше, сталкиваемся с проблемой (при включенной оптимизации кода компилятором иногда выбивает Access Violation) убираем регистры ESI, EDI, вместо них используем ECX, EDX. Раскладываем функцию из [37], убираем лишнее, остается 5 команд! Полнофункциональный генератор псеводслучайных чисел, с только одним обращением к памяти, и без дерганий стека. Должно летать, по скорости уделает Borlandoвский Random раза в полтора!

Function MyRandom(Number:Integer):Cardinal;Assembler; asm mov ecx, 0F7F77B0Ah add eax, Code // Integer randomize mul ecx xor ecx,edx mul ecx shr eax,8 // If RGB result is needed else comment it end;

← →
MasterKolyan (2004-02-26 03:26) [40]

Defunct © (26.02.04 02:17) [39]
Ты немного не прав: твой генератор уделал Borland-овский rendom не в полтора а почти в три раза.
Сравнительные характеристики:(на компе 733МГЦ)(память DIMM)
сек частота/Гц сравнение скорости (Borland) random 1.159e-07 8"628"127 x1.000 (super) Myrandom 4.567e-08 21"896"211 x2.537 Обращение к ОЗУ 8.429e-09 118"638"035 x13.75

Генератор списка случайных чисел по коду_Выбор элемента по номеру Найти похожие ветки