forum.boolean.name - Делить нельзя, умножить

forum.boolean.name (http://forum.boolean.name/index.php)

- FAQ (http://forum.boolean.name/forumdisplay.php?f=15)

- - Делить нельзя, умножить (http://forum.boolean.name/showthread.php?t=102)

:user:
Настоятельно рекомендую использовать операцию *.5 вместо /2, и вот почему.
Простенький тест уменьшит все числа ряда от 1 до 30000 двумя способами, измерив при этом время выполнения:

Код:

time1=MilliSecs()

For i=1 To 30000

        a=i/2

Next

time1=MilliSecs()-time1

time2=MilliSecs()

For i=1 To 30000

        a=i*.5

Next

time2=MilliSecs()-time2

Print " [\2] "+time1

Print " [*.5] "+time2

WaitKey()

У меня результаты 75 и 4 :o
Комментарии излишни...

101 к 8 проиграло деление умножению при работе с float

Код:

time1=MilliSecs()

For i=1 To 30000

a#=i*0.3/2

Next

time1=MilliSecs()-time1

time2=MilliSecs()

For i=1 To 30000

a#=i*0.3*.5

Next

time2=MilliSecs()-time2

Print " [\2] "+time1

Print " [*.5] "+time2

WaitKey()

140 к 10
при случайной подборке чисел (int/float)

Код:

time1=MilliSecs()

For i=1 To 30000

If Rand(0,1)=1

        a#=i*0.3/2

Else

        a=i/2

EndIf

Next

time1=MilliSecs()-time1

time2=MilliSecs()

For i=1 To 30000

If Rand(0,1)=1

        a#=i*0.3*0.5

Else

        a=i*0.5

EndIf

Next

time2=MilliSecs()-time2

Print " [\2] "+time1

Print " [*.5] "+time2

WaitKey()

Всё по нулям, по этой причине увеличил цикл на несколько порядков :)
в первом - /2 в 3 раза быстрее *.5 ;)
в остальных - почти поровну, ну 0.5 немного впереди.
П4 2.8, 512.

7,7
7,6
16,13

и кто же у нас быстрее ? :o

а теперь дружненько напишем у кого какой проц... чтоб точно знать как оно и где вполняется.. :) :)

вижу появление запятой в названии темы!

А если часто надо использовать что-то вроде этого: value = value + 1.0/koef
тогда как?
Если koef не меняется, то понятно, а если меняется? Можно ускорить как-то?

тогда прийдется делить..... да ладно вы так, все это всерьез принимать... не так уж это и страшно... вы просмотрите свой код, через сколько итераций у вас наберется 30000 действий деления?? не через 5000 ли??

оно (умножение) конечно и увеличивает скорость но не надо этим увлекаться, а то щас начнем писать функцию в которой будем просматривать, что если значение четное, то использовать ротацию и т.п....

УМНОЖАЙТЕ ПРИ СЛУЧАЕ, А В ОСТАЛЬНОМ НЕ БЕСПОКОЙТЕСЬ! :)

Цитата:

Originally posted by SubZer0@Sep 22 2005, 03:34 PM
конечно и увеличивает скорость но не надо этим увлекаться, а то щас начнем писать функцию в которой будем просматривать, что если значение четное, то использовать ротацию и т.п....

или с криками "долой выгрузку в стек!" на GOTO кодить ;)
да гото чуть быстрее, но сомневаюсь, что в вашей проге применение оператора безусловного перехода будет оправдано

Тесты выполнять надо несколько раз и брать среднее - я поторопился и не автоматизировал этот процесс, сорри :o''

интересно :) пять раз проверил - одно и тоже было , pentium 4 1.7ghz

у мя на Athlon XP Pro3+ работает где деление на два у мя быстрей деление работает, а вот такой код

Код:

time1=MilliSecs()

For i=1 To 1000000

 a=i/10

Next

time1=MilliSecs()-time1

time2=MilliSecs()

For i=1 To 1000000

 a=i*.1

Next

time2=MilliSecs()-time2

Print " [/2] "+time1

Print " [*.5] "+time2

WaitKey()

то результат обычно 42 и 14

вот такой код

Код:

time1=MilliSecs()

For i=1 To 1000000

 a=i/5

Next

time1=MilliSecs()-time1

time2=MilliSecs()

For i=1 To 1000000

 a=i*.2

Next

time2=MilliSecs()-time2

Print " [/2] "+time1

Print " [*.5] "+time2

WaitKey()

работает 46 и 15

умножение рулит! :rolleyes:

Цитата:

Originally posted by SubZer0@Sep 22 2005, 10:01 PM
у мя на Athlon XP Pro3+ работает где деление на два у мя быстрей деление работает, а вот такой код

Код:

time1=MilliSecs() For i=1 To 1000000 a=i/10 Next time1=MilliSecs()-time1 time2=MilliSecs() For i=1 To 1000000 a=i*.1 Next time2=MilliSecs()-time2 Print " [/2] "+time1 Print " [*.5] "+time2 WaitKey()

то результат обычно 42 и 14

вот такой код

Код:

time1=MilliSecs() For i=1 To 1000000 a=i/5 Next time1=MilliSecs()-time1 time2=MilliSecs() For i=1 To 1000000 a=i*.2 Next time2=MilliSecs()-time2 Print " [/2] "+time1 Print " [*.5] "+time2 WaitKey()

работает 46 и 15

умножение рулит! :rolleyes:

Рулит не умножение, а знание алгоритмов, по которым работает транслятор/компилятор конкретного языка (вернее, конкретной реализации). Например, операции целочисленного деления или умножения могут выполняться заменой на операции сдвига и суммирования, то есть

x / 2 = x shl 2

x / 5 = 10 * x / 2 = ((x shr 3)+(x shr 1)) shl 2

и т.д.

Blitz3D из вышеперечисленного оптимизирует только деление на два.
Поэтому, заменив в примере из предыдущегого поста x / 5 на вышеприведенную формулу, умножение больше не рулит:

Код:

time1=MilliSecs()

For i=1 To 1000000

a=((i Shr 3) + (i Shr 1)) Shl 2

;a=i / 5

Next

time1=MilliSecs()-time1

time2=MilliSecs()

For i=1 To 1000000

a=i * .2

Next

time2=MilliSecs()-time2

Print " [/2] "+time1

Print " [*.5] "+time2

WaitKey()

А для разработчиков Blitza было бы лучше вообще перейти на арифметику с фиксированной точкой, (даже тип double не спасет за счет относительно низкой скорости). Тем более сейчас уже наступила эра 64-битных процессоров.
Хотя Марку все равно респект и уважение.

Сорри за описку в предыдущем посте - Новый год, все-таки был!
Нужно поменять местами команды SHL и SHR (естественно, сдвиг вправо делит целое число на два, а сдвиг влево - умножает. Хотя именно в том примере это не принципиально, но тем не менее прокол-с.)

Цитата:

Originally posted by impersonalis@Sep 19 2005, 04:39 PM
:user:
Настоятельно рекомендую использовать операцию *.5 вместо /2, и вот почему.
Простенький тест уменьшит все числа ряда от 1 до 30000 двумя способами, измерив при этом время выполнения:

Код:

time1=MilliSecs() For i=1 To 30000 a=i/2 Next time1=MilliSecs()-time1 time2=MilliSecs() For i=1 To 30000 a=i*.5 Next time2=MilliSecs()-time2 Print " [\2] "+time1 Print " [*.5] "+time2 WaitKey()

У меня результаты 75 и 4* :o
Комментарии излишни...

Quoted post

Возвращаясь к вышеизложенному, с прискорбием сообщаю, что ув. г-н Impersonalis не прав абсолютно. Меня заинтересовала полученная разница во времени, которая не может быть объяснена никакими таймингами и тактами процессора, FPU и т.д.

Итак, ищем причину странного явления.

Добавим в самое начало программы простую строку - Delay 3000.
Происходит чудо :)) - времена выравниваются! Если задержку уменьшать, то, соответственно, первое время начинает возрастать. Что происходит? Смотрим - режим отладки включен! Вот он, мерзавец, и вступил в тайный сговор с Impersonalisom!
Но нет, если поменять местами а=i/2 и a=i*.5, то есть a=i*.5 вставить в первый цикл, то НИЧЕГО не меняется!

Просто - напросто при включенной отладке запускается дополнительно в фоне основной программы инициализация отладчика - выделяется память под символьные переменные, переключается стек, нумеруются строки и пр. Это может длится пару секунд (чем слабее процессор, тем дольше). Соответственно, самый первый тест выполняется медленнее.

Чтобы это устранить, нужно задать в цикле не 30 тысяч вычислений, а три миллиона. Тогда этот эффект нивелируется. Ну а лучше вообще отключить отладку и попробовать посчитать:

Код:

time1=MilliSecs()

For i=1 To 3000000

 * *a = i * .5

Next

time1=MilliSecs()-time1



time2=MilliSecs()

For i=1 To 3000000

 * *a = i / 2

Next

time2=MilliSecs()-time2



time3=MilliSecs()

For i=1 To 3000000

 * *a = i Shr 2

Next

time3=MilliSecs()-time3



time4=MilliSecs()

For i=1 To 3000000

 * *b# = i / 3

Next

time4=MilliSecs()-time4



Print " [*.5] " * + time1

Print " [/2] " * *+ time2

Print " [shr 2] " + time3

Print " [/3#] " * + time4

WaitKey()

Теперь все встает на свои места. У множение на .5 использует FPU, естественно, оно медленнее регистрового сдвига SHR 1. Деление на 2 целого числа компилятор заменяет на сдвиг, поэтому деление целых чисел на 2 ГОРАЗДО БЫСТРЕЕ умножения на .5. Ну и медленне всего (из представленных вариантов) выполняется деление на 3.

ЛОГИЧЕСКИЙ СДВИГ РУЛИТ - это делается одним сдвигом процессорного регистра!

Предлагаю тов. Impersonalis заменить рекламный слоган.

Ну, то что "сдвиг рулит" - это очевидно. Я как-то заметил вот такую констукцию на С++

Код:

x=N>>1;

и теперь стараюсь её юзать при написании быстрых алгоритмов.
В остальных же случаях это не критично.

Не совсем правда понял - почему AsmLover сдивгает на 2 разряда (т.е. делит на 2^2=4, а не на один разряд :dontknow: )

Вот за дополнительные расследования - респект.
Переходим на деление обратно.

Кстати - лишнее доказательство тезиса Декарта:
сомнение есть способ познания.
Сомневаться нельзя лишь в необходимости сомнений.

Исходя из этого не стоит 100% доверять какой-либо теории.

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

Цитата:

Originally posted by impersonalis@Jan 17 2006, 08:17 PM
Не совсем правда понял - почему AsmLover сдивгает на 2 разряда (т.е. делит на 2^2=4, а не на один разряд :dontknow: )

Да какая разница для топика? Время выполнение SHR 1 и SHR $FFFFFFF одинаковое.

Для тех, кто интенсивно использует вычисления (матрицы транспонирует всякие :) ), необходимо знать, что если в примере

Код:

time4=MilliSecs()

For j=1 To 3000000

  b# = j / 3

Next

time4=MilliSecs()-time4

написать b# = j / 3.0,

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

b = j / 3.0

время, по сраснению с вариантом с b# возрастет процентов на 5 и сравняется с циклом умножения.
Это связано с использованием неявного приведения типов в компиляторе.

Вообще говоря, сдвиг не по-любому рулит. Как бы Impersonalisu снова слоган не поменять... Сдвиг рулит на языках, не имеющих нормальной возможности обработки битов, таких как Бейсик.
На ассемблере релизация, например, целочисленного умножения сдвигом и сложением уже не является самой быстрой, хоть и быстрее команды IMUL (14 тактов на P4). Быстрее выполняется команды LEA (4 такта), например вот как выглядит умножение на 9:
lea eax, [eax+eax*8],
и это выполняется быстрее, кстати, (в тактах) на P3, чем на P4. Также можно оптимизировать и одновременное выполнение (4 инструкций для АЛУ P4) RISC-подобное умножение командами MOV и ADD или, с интерливом, плюс LEA. Хотя из описания оптимизации кода под процессоры P4 уже интерлив не упоминается, однако он по-прежнему эффективен, как и для P3. А оптимальным алгоритмом целочисленного умножения ax на bx по-прежнему является:

Для каждого бита слева направо, если бит =1 выполняется
add ebx, eax
add eax, eax,
а если бит =0, то
add eax, eax.

Быстрее этого ничего нет ( разве оптимизация шитого кода, но это уже доступно только самим разработчикам процессоров).

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

Кстати, использование LEA эффективнее по тактам на AMD, чем на P4.

Знание архитектуры процессоров рулит! :super:

Re: Делить нельзя, умножить

Звиняюсь что поднимаю старую тему, но
Для вещественных переменных обе операции будут равны по скорости, ибо обе идентичны по коду, обе используют FPU (FDIVRP и FMULP)
Для целочисленных переменных в умножении так же используется FPU, а в делении битовый сдвиг, поэтому быстрее выполняется он, но только для целочисленных.

Re: Делить нельзя, умножить

при 30000000 повторах деление стабильно выигрывает у умножения :)
ПС у мну 64битный атлончег :)