Сейчас на форуме: tyns777, zds, JustLife, 2nd, morgot, Rio (+5 невидимых)

 eXeL@B —› Программирование —› Оптимизация (int * int) div int
. 1 . 2 . >>
Посл.ответ Сообщение

Ранг: 8.6 (гость)
Активность: 0=0
Статус: Участник

 Создано: 06 июля 2009 16:58 · Поправил: LKS128
· Личное сообщение · #1

Имеется процедура написанная на дельфях.
Общий вид:

Code:
  1. procedure foo;
  2. var i,j :integer;
  3. begin
  4.   // ... code
  5.  
  6.   i := (i * j) div 255;
  7.  
  8.   // ... code
  9. end;


i := (i * j) div 255;
Эта операция жрёт половину времени процедуры.

Замена на i := round((i * j) / 255);
немного улучшает ситуацию, но не намного.

Есть ли какие-нибудь варианты оптимизации?



Ранг: 8.6 (гость)
Активность: 0=0
Статус: Участник

 Создано: 06 июля 2009 17:29
· Личное сообщение · #2

Хотя, может это и не имеет смысла, если максимальное значение i,j = 255, при делении на 256, что гораздо быстрее максимальная ошибка равна 0,99609375, что не критично.
Но если у вас есть какие-либо предложения, с радостью выслушаю.




Ранг: 533.6 (!), 232thx
Активность: 0.45↘0
Статус: Uploader
retired

 Создано: 06 июля 2009 18:25 · Поправил: BoRoV
· Личное сообщение · #3

LKS128 пишет:
i := (i * j) div 255;
Code:
  1. i := (i * j) shr 8;

это значительно ускорит.

вот во что компилит твое деление
Code:
  1.   
  2.   MOV EAX,EDI   <- EDI = i * j
  3.   MOV ESI,0FFh
  4.   CDQ
  5.   IDIV ESI


а вот слегка оптимизированый, который предложил
Code:
  1.   SHR EDI, 8 <- EDI = i * j


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

-----
Лучше быть одиноким, но свободным © $me

Ранг: 65.3 (постоянный), 10thx
Активность: 0.02↘0
Статус: Участник

 Создано: 06 июля 2009 19:54
· Личное сообщение · #4

BoRoV
А это не div 256 получится?




Ранг: 533.6 (!), 232thx
Активность: 0.45↘0
Статус: Uploader
retired

 Создано: 06 июля 2009 20:12 · Поправил: BoRoV
· Личное сообщение · #5

tomac пишет:
BoRoVА это не div 256 получится?
да, согласен, погорячился, на всех примерах что проверил срабатывало

вот немного себя поправлю
Code:
  1. i := (i *j) shr 8 + 1;


всеравно оптимальней

-----
Лучше быть одиноким, но свободным © $me

Ранг: 122.2 (ветеран)
Активность: 0.04↘0
Статус: Участник

 Создано: 06 июля 2009 22:45
· Личное сообщение · #6

BoRoV пишет:
вот немного себя поправлю
Code:

1. i := (i *j) shr 8 + 1;



Все-равно неправильно. x/256 + 1 != x/255

Можно попробовать вот так:

i := round((i * j) * 0.003921568)

Еще можно посмотреть во что дельфи это компилит. Взять этот код и убрать оттуда fwait.




Ранг: 533.6 (!), 232thx
Активность: 0.45↘0
Статус: Uploader
retired

 Создано: 06 июля 2009 22:55 · Поправил: BoRoV
· Личное сообщение · #7

egorovshura пишет:
Все-равно неправильно. x/256 + 1 != x/255
а я такого и не говорил!

я говорил что:
Code:
  1. x/255 == x >> 8 + 1;


-----
Лучше быть одиноким, но свободным © $me


Ранг: 605.2 (!), 341thx
Активность: 0.47↘0.25
Статус: Модератор
Research & Development

 Создано: 06 июля 2009 23:35
· Личное сообщение · #8

BoRoV
даже если поставить скобки, всё равно получится неправильно.

твоя формула:
x/255 == x >> 8 + 1;

проверка:
x=777

777/255 = 3.047

777 >> 8 + 1 = 1

(777 >> 8) +1 = 4

777 >> 8 = 3

-----
EnJoy!

Ранг: 20.8 (новичок), 7thx
Активность: 0.01↗0.02
Статус: Участник

 Создано: 06 июля 2009 23:40 · Поправил: int_256
· Личное сообщение · #9

BoRoV пишет:
я говорил что:
x/255 == x >> 8 + 1;
сие будет верно када х=255*256

сдвиг вправо на N есть деление на 2^N

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




Ранг: 527.7 (!), 381thx
Активность: 0.16↘0.09
Статус: Участник
Победитель турнира 2010

 Создано: 06 июля 2009 23:40 · Поправил: OKOB
· Личное сообщение · #10

x/255 == (x >> 8 + 1 == x/256 + 1) != x/255
........ \.............................................. \
........ я говорил что .......................... а такого и не говорил

суровое выражение получается, т.к. x >> 8 и есть x/256

-----
127.0.0.1, sweet 127.0.0.1


Ранг: 533.6 (!), 232thx
Активность: 0.45↘0
Статус: Uploader
retired

 Создано: 06 июля 2009 23:56
· Личное сообщение · #11

все я понял, я не совсем прав!

НО!
сначала я утверждал что истено это x >> 8, и я сам в это верил так как перепробывав пару комбинаций, все сходилось....
потом мне сказали что я не прав, я перепроверил, и вправду не прав, потом попробывав пару комбинации которые не шли по правилу x >> 8, но зато они шли по правилу (x >> 8) + 1, и я стал утвержлать что вот истено...

потому и вышла такая не разбериха, простите если кого-то ввел в заблуждение, да я был не прав

-----
Лучше быть одиноким, но свободным © $me


Ранг: 756.3 (! !), 113thx
Активность: 0.61↘0.05
Статус: Участник
Student

 Создано: 07 июля 2009 00:01 · Поправил: Isaev
· Личное сообщение · #12

Jupiter пишет:
777 >> 8 + 1 = 1
(777 >> 8) +1 = 4
это же не си shr по умолчанию приоритет больший имеет

to LKS128
самое приближённое получается при таком раскладе
Code:
  1. asm
  2.   mov eax,D
  3.   mov edx,1010101h
  4.   mul edx
  5.   mov B, dl
  6. end;

кто сделает лучше, дайте знать, самому интересно стало, надо на 255 делить
в результате работает быстрее, т.к. деление меняем на умножение и со всего диапазона в 2^32 имеем 1485 результатов с погрешностью в 1
при A div 256 ты имел 16678 левых результатов и писал, что
LKS128 пишет:
при делении на 256, что гораздо быстрее максимальная ошибка равна 0,99609375, что не критично.

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh

Ранг: 8.6 (гость)
Активность: 0=0
Статус: Участник

 Создано: 07 июля 2009 02:28
· Личное сообщение · #13

2 Isaeм
Интересный способ.
Если не ошибаюсь, вроде прога была, которая конвертирует деление в умножение с переполнением?



Ранг: 309.8 (мудрец), 21thx
Активность: 0.17↘0
Статус: Участник

 Создано: 07 июля 2009 02:35
· Личное сообщение · #14

автор проги bart^xt помоему.

-----
Shalom ebanats!


Ранг: 756.3 (! !), 113thx
Активность: 0.61↘0.05
Статус: Участник
Student

 Создано: 07 июля 2009 02:49
· Личное сообщение · #15

LKS128 что за прога? есть у кого глянуть?

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh


Ранг: 209.5 (наставник), 42thx
Активность: 0.1↘0
Статус: Участник
WinCE ARM M@sTeR

 Создано: 07 июля 2009 06:07 · Поправил: Getorix
· Личное сообщение · #16

Можно деление на 255 вот так сделать:

__int64 tmp, res;
__int32 val = [значение (i*j например)];

res = ((__int64)val * 0x80808081) >> 39;
tmp = (res >> 31) & 1;
res = res + tmp;

а если val всегда беззнаковый, то еще проще:

res = ((__int64)val * 0x80808081) >> 39;

думаю это быстрее чем div будет

-----
Get busy living or get busy dying ©

Ранг: 251.3 (наставник), 81thx
Активность: 0.14↘0.11
Статус: Участник

 Создано: 07 июля 2009 12:45
· Личное сообщение · #17

Isaev пишет:
что за прога? есть у кого глянуть?
Прога называется AMD Optimization Manual
Там замена деления на умножение детально расписана.
Кому лень разбираться - берёте VS нормальную или интеловский компилятор, оптимизатор сам это делает.



Ранг: 203.3 (наставник)
Активность: 0.22↘0
Статус: Участник
UPX Killer -d

 Создано: 08 июля 2009 22:08 · Поправил: AlexZ
· Личное сообщение · #18

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

-----
Я медленно снимаю с неё UPX... *FF_User*


Ранг: 756.3 (! !), 113thx
Активность: 0.61↘0.05
Статус: Участник
Student

 Создано: 08 июля 2009 22:38
· Личное сообщение · #19

а можно логическую операцию (AND например) на математическую формулу заменить (т.е. без логических операций)?

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh

Ранг: 203.3 (наставник)
Активность: 0.22↘0
Статус: Участник
UPX Killer -d

 Создано: 08 июля 2009 22:45
· Личное сообщение · #20

В линейной постановке нельзя.
В нейросетях этот пример рассматривается, почти как классический.
Если не путаю.

-----
Я медленно снимаю с неё UPX... *FF_User*

Ранг: 122.2 (ветеран)
Активность: 0.04↘0
Статус: Участник

 Создано: 09 июля 2009 03:08
· Личное сообщение · #21

Дело не только в линейности. Логические функции сильно разрывные. Так что чтобы аппроксимировать тот же and в диапазоне значений от 0 до 255 и получить верное значение в каждой точке (а это 65536 точек) нужно брать полином 65536 порядка (если не ошибаюсь).
Для примера прицепил график And и его аппроксимации полиномом 20-ой степени.

4e11_08.07.2009_CRACKLAB.rU.tgz - graph.GIF




Ранг: 605.2 (!), 341thx
Активность: 0.47↘0.25
Статус: Модератор
Research & Development

 Создано: 09 июля 2009 09:58 · Поправил: Jupiter
· Личное сообщение · #22

Getorix

в твоём коде для 32-х бит нужно будет двигать на 7 вправо (если не нужно работать с 64 битами)

-----
EnJoy!

Ранг: 36.1 (посетитель)
Активность: 0.01↘0
Статус: Участник

 Создано: 09 июля 2009 11:01
· Личное сообщение · #23

Если памяти не жалко и i,j=255 максимум, то:

Code:
  1. procedure foo;
  2. var i,j :integer;
  3. tb: array [0..256*256] of byte;
  4. begin
  5. for i:=0 to 256*256 do tb[i]:=i div 255;
  6. // ... code
  7.      
  8. i := tb [i * j];
  9.  
  10. // ... code
  11. end;


Ранг: 605.2 (!), 341thx
Активность: 0.47↘0.25
Статус: Модератор
Research & Development

 Создано: 09 июля 2009 11:19
· Личное сообщение · #24

прилагаю тулзу Magic Divider, созданную The Svin
(я эту тулзу малость причесал)

для делителя 255:

Code:
  1. ; divider = 255
  2. MagicNumber = 80808081h
  3. mov      eax,X
  4. mov      edx,MagicNumber
  5. mul      edx
  6. shr      edx,7



Malice

оно того явно не стоит ;)

be19_09.07.2009_CRACKLAB.rU.tgz - MagicDivider.v1.02.rar

-----
EnJoy!


Ранг: 209.5 (наставник), 42thx
Активность: 0.1↘0
Статус: Участник
WinCE ARM M@sTeR

 Создано: 09 июля 2009 12:00 · Поправил: Getorix
· Личное сообщение · #25

Jupiter пишет:
в твоём коде для 32-х бит нужно будет двигать на 7 вправо (если не нужно работать с 64 битами)
код рабочий, можешь скопмилить и проверить
сдвиг на 7 (то что для 255) уже заложен в код:
умножаем число на magic, получаем в старшем дворде результат, двигаем на 32 вправо чтобы получить его в младшем дворде. потом еще на 7 бит двигаем чтобы получить правильный результат для делителя 255.
32 + 7 = 39 что и получаем в ((__int64)val * 0x80808081) >> 39;
на асме на 32 бита двигать конечно ненадо у тебя нужное число уже в edx как я понимаю.

-----
Get busy living or get busy dying ©


Ранг: 605.2 (!), 341thx
Активность: 0.47↘0.25
Статус: Модератор
Research & Development

 Создано: 09 июля 2009 12:07
· Личное сообщение · #26

я ж не говорю, что код не рабочий
мои слова относились к 32-х битным значениям
к тому же код на асме я привёл выше

в принципе, можно вообще макро использовать
например, такой для делителя 255:

Code:
  1. mdiv_255 Macro    dividend
  2.          mov     eax,dividend
  3.          mov     edx,80808081h
  4.          mul     edx
  5.          shr     edx,7
  6.          ExitM   <edx>
  7. EndM


-----
EnJoy!


Ранг: 756.3 (! !), 113thx
Активность: 0.61↘0.05
Статус: Участник
Student

 Создано: 09 июля 2009 22:05
· Личное сообщение · #27

ну и поклал бы с сырками новыми... по мелочам, но приятнее стало

-----
z+Dw7uLu5+jqLCDq7vLu8PvpIPHs7uMh

Ранг: 516.1 (!), 39thx
Активность: 0.28↘0
Статус: Участник

 Создано: 10 июля 2009 15:59 · Поправил: Av0id
· Личное сообщение · #28

к теме о тулзах и магических числах

ps. по теме - по-моему использование LUT (look-up table) самый жизненный вариант (Malice предложил выше)

e8de_10.07.2009_CRACKLAB.rU.tgz - xt_muldiv10.zip



Ранг: 251.3 (наставник), 81thx
Активность: 0.14↘0.11
Статус: Участник

 Создано: 10 июля 2009 16:27
· Личное сообщение · #29

Замена на умножение тоже имеет смысл.
Будет намного быстрее деления.




Ранг: 605.2 (!), 341thx
Активность: 0.47↘0.25
Статус: Модератор
Research & Development

 Создано: 10 июля 2009 16:57
· Личное сообщение · #30

Av0id
умножение и сдвиг на регистрах однозначно быстрее доступа к памяти

-----
EnJoy!
. 1 . 2 . >>
 eXeL@B —› Программирование —› Оптимизация (int * int) div int
:: Ваш ответ
Жирный  Курсив  Подчеркнутый  Перечеркнутый  {mpf5}  Код  Вставить ссылку 
:s1: :s2: :s3: :s4: :s5: :s6: :s7: :s8: :s9: :s10: :s11: :s12: :s13: :s14: :s15: :s16:


Максимальный размер аттача: 500KB.
Ваш логин: german1505 » Выход » ЛС
   Для печати Для печати