Вопрос по быстродействию div и mod

[Climber]

Допустим, у меня есть некое число N типа integer или longint.
Насколько я знаю, компьютеру намного проще вычислить N div 256, чем N div 10, и тоже самое с mod. Так ведь?
Вроде были какие-то операции битового сдвига (я только забыл, как они записываются), компилятор сам оптимизировать сможет или ему надо явно указать?

[VirtUX]

я только забыл, как они записываются

Битовые операции

i shl j - сдвиг содержимого i на j разрядов влево; освободившиеся младшие разряды заполняются нулями;

i shr j - сдвиг содержимого i на j разрядов вправо; освободившиеся старшие разряды заполняются нулями.

[alexrayne]

А что компилятор ненастока умен чтоб самому оптимизировать такие деления в сдвиги?

[Climber]

А что компилятор ненастока умен чтоб самому оптимизировать такие деления в сдвиги?

Вот я и хотел это узнать.

Есть еще вопрос по div: зависит ли время выполнения этой операции от величины числа? Имеются ввиду случаи деления на числа, не являющиеся степенями двойки. Например, насколько большой будет разница между вычислениями 63456 div 10000, 63456 div 10 и 54 div 10?

[Иван Шихалев]

Проще всего узнать, посмотрев ассемблерный файл, который создается при использовании fpc -a. Кстати, получается действительно интересно: у меня по крайней мере, div оптимизируется, а mod — нет.

[Climber]

Для меня ассемблер - китайская грамота.
Написал такой код:

Код: Выделить всё

var
  w, t, i, k, l: integer;
begin
  k:=345634;
  l:=23;
  i:=10;
  w:=k div i;
  w:=l div i;
  w:=k div 10000;
end.

Получилось (там много чего получилось, я не уверен, что нужный кусок скопировал ):

Код: Выделить всё

PASCALMAIN:
.globl   _main
_main:
   pushl   %ebp
   movl   %esp,%ebp
   call   FPC_INITIALIZEUNITS
   movl   $345634,U_P$BIGFACT_K
   movl   $23,U_P$BIGFACT_L
   movl   $10,U_P$BIGFACT_I
   movl   U_P$BIGFACT_K,%eax
   cltd
   idivl   U_P$BIGFACT_I
   movw   %ax,U_P$BIGFACT_W
   movl   U_P$BIGFACT_L,%eax
   cltd
   idivl   U_P$BIGFACT_I
   movw   %ax,U_P$BIGFACT_W
   movl   U_P$BIGFACT_K,%ecx
   movl   $1759218605,%eax
   imull   %ecx
   movl   %ecx,%eax
   sarl   $12,%edx
   shrl   $31,%eax
   addl   %eax,%edx
   movw   %dx,U_P$BIGFACT_W
   call   FPC_DO_EXIT
   leave
   ret
# End asmlist al_procedures


[SII]

Вообще, деление элементарно заменяется на сдвиг только в том случае, если делитель является степенью двойки (1, 2, 4, 8, 16 и т.д.). Если он -- не степень двойки, но константа, тогда операцию деления можно заменить на группу операций сложения-вычитания, сдвига и умножения. Наконец, если делитель во время трансляции неизвестен, ни на что заменить деление нельзя.

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

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

[Odyssey]

Для меня ассемблер - китайская грамота.

Так специально для таких как мы с тобой есть fpc -al, которая добавляет в комментарии к командам ассемблера строчки исходного кода на паскале. А когда видно, какая строчка в какой ассемблерный код превращается, ассемблер сразу становиться ближе и дружелюбнее
http://www.freepascal.org/docs-html/use ... 450005.1.4

[Climber]

Odyssey
Во! Вот с этого и надо было начинать!!! Спасибо!