Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Остаток от деления на десять

Автор: cardinal 29.11.2010, 22:40

собственно хотелось бы с более простыми операциями типа сдвига...

Автор: mes 29.11.2010, 22:50

если делите (берете остаток) на константу, то компилятор сам сделает то что нужно..

Автор: cardinal 29.11.2010, 22:55

А я ему не доверяю и поэтому все оптимизации выыключены.

Автор: mes 29.11.2010, 23:00

Цитата(cardinal @  29.11.2010,  21:55 ) А я ему не доверяю и поэтому все оптимизации выыключены.  и зря.. Добавлено через 1 минуту и 50 секунд и с чего вобще такое желание оптимизировать это деление ? Вы уверены, что это (самое) узкое место ?

Автор: sQu1rr 29.11.2010, 23:10

Цитата  В общем случае результат выполнения конструкции a&b равен a%(b+1), где b = 2^n - 1. (% - оператор нахождения остатка от деления левого операнда на правый). Теоретическая причина по которой конструкция a&b более популярна для нахождения остатка, в том что она исполняется быстрее чем её более понятный для чтения аналог. На практике, последние версии популярных компиляторов в состоянии проводить подобную оптимизацию кода самостоятельно, не говоря уже о том что разница в эффективности исполнения этих двух конструкций вообще не существенна на современных процессорах. В идеале, вы должны знать об этом и других подобных трюках для того чтобы понимать код написанный несколькими годами ранее, но случаи в которых их использование будет оправдано вами в настоящее время действительно встречаются редко. Добавлено через 1 минуту и 42 секунды Это я не как способ ( он к 10 не подходит ) - а как подтверждение нецелесообразности использование оптимизации того, с чем либо компилятор справиться, либо не существенно для скорости выполнения

Автор: cardinal 29.11.2010, 23:22

Вы люди избалованные Intel, AMD... а есть еще и другие процессоры, для которых ВСЕ существенно, каждая строка кода. Компилятор в таких случаях может наваять чего угодно и поэтому оптимизацию принято отключать, а писать сразу эффективный код. То есть пока вы мне ничем не помогли.

Автор: mes 30.11.2010, 00:22

Цитата(cardinal @  29.11.2010,  22:22 ) а есть еще и другие процессоры, для которых ВСЕ существенно, каждая строка кода. для таких пишут на других языках, позволяющих вручную контролировать каждую строчку кода..

Автор: sQu1rr 30.11.2010, 01:28

Цитата #include <stdlib.h> div_t div(int numer, int denom); DESCRIPTION The div() function computes the value numer/denom and returns the quotient and remainder in a structure named div_t that contains two integer members named quot and rem. RETURN VALUE The div_t structure. В VC++ возвращает тип параметров

Автор: cardinal 30.11.2010, 01:46

Цитата(mes @  29.11.2010,  22:22 ) для таких пишут на других языках, позволяющих вручную контролировать каждую строчку кода.. Ассемблером зовется... Тогда переформулирую вопрос: как мне наиболее эффективно на ассемблере написать функцию "остаток от деления на 10"? Только не надо меня посылать теперь в другой подфорум... sQu1rr, мне нужна не функция, а ее реализация!!! Причем простую я и сам знаю.

Автор: Леопольд 30.11.2010, 08:15

Цитата(cardinal @  30.11.2010,  01:46 ) на ассемблере Всё зависит от ассемблера. cardinal, сомневаюсь что с помощью бинарных операций можно это сделать быстрее чем это сделает сам процессор (который, возможно, сам всё к этому сведёт), 10 ведь не степень двойки.

Автор: azesmcar 30.11.2010, 08:22

Цитата(cardinal @  29.11.2010,  23:22 ) а есть еще и другие процессоры, для которых ВСЕ существенно Есть такое, сталкивался, оптимизировал деление на 2 и разница довольно существенная (с учетом того, что процессор был 70 мегагерцовый)   Код unsigned int mod10(unsigned int n) {     const unsigned __int64 m = 0x1999999A;     return n - ((n * m) >> 32) * 10; } где m - magic number ~ 2^32 / делитель (10 в нашем случае) алгоритм взял из книги "алгоритмические трюки для программистов". Рекомендую, незаменимая вещь в работе такого рода. к сожалению для алгоритма требуется 64-х битный int (если делится 32-х битный int). стоит протестировать скорость работы, но вообще умножение намного быстрее деления. можно еще попробовать оптимизировать умножение..

Автор: Леопольд 30.11.2010, 08:52

Цитата(azesmcar @  30.11.2010,  08:22 ) требуется 64-х битный int Или второй (32-битный) регистр, куда пишется переполнение. В нем как раз будет результат: (n * m) >> 32

Автор: azesmcar 30.11.2010, 09:18

Немного поигрался с отладчиком. Этот код сгенерировала Visual Studio 2010 с настройками оптимизации, как и просил, на ассемблере   Используется аналогичный алгоритм. Код inline unsigned int mod10(unsigned int n) {     int x;     __asm     {         mov         esi,n         mov         eax,66666667h         imul        esi         sar         edx,2         mov         eax,edx         shr         eax,1Fh         add         eax,edx         lea         ecx,[eax+eax*4]         add         ecx,ecx         sub         esi,ecx         mov         x,esi     }     return x; } еще один способ Код int remu10(unsigned n) {     static char table[16] = {         0, 1, 2, 2, 3, 3, 4, 5,         5, 6, 7, 7, 8, 8, 9, 0};     n = (0x19999999*n + (n >> 1) + (n >> 3)) >> 28;     return table[n]; } http://www.hackersdelight.org/divcMore.pdf из той же книги.

Автор: cardinal 30.11.2010, 10:38

Во, вот это уже то, что нужно! Спасибо, azesmcar!

Автор: MrYuran 30.11.2010, 11:40

А в результате окажется, что у процессора есть аппаратный умножитель, который за 1 такт может расщёлкать все ваши /%10 Ассемблер нужно уметь читать, но писать на нём не надо!

Автор: azesmcar 30.11.2010, 12:24

MrYuran Обычно программисты, которые сталкиваются с такой необходимостью и пишущие под конкретный процессор в курсе процессорных команд, которые он поддерживает и процессоры, на которых приходиться вот так оптимизировать больше напоминают калькулятор, чем современные процессоры и с 99% вероятности они этого не умеют. А то, что ты описал я не знаю умеет ли вообще какой либо из современных процессоров.

Автор: bsa 30.11.2010, 15:20

Цитата(MrYuran @  30.11.2010,  12:40 ) А в результате окажется, что у процессора есть аппаратный умножитель, который за 1 такт может расщёлкать все ваши /%10 Это что за процессор такой? intel pentium, например, тратит 17, 25 и 41 (8bit, 16bit, 32bit) такт на операцию DIV. А у Intel 8080 или Zilog Z80 вообще операций деления и умножения нет.

Автор: MrYuran 30.11.2010, 16:01

Цитата(bsa @ 30.11.2010,  15:20) Это что за процессор такой? intel pentium, например, тратит 17, 25 и 41 (8bit, 16bit, 32bit) такт на операцию DIV. А у Intel 8080 или Zilog Z80 вообще операций деления и умножения нет. А кроме интела, надо думать, никто процессоры не производит. И х86 форева    Большинство ARM контроллеров, даже начального уровня, имеют аппаратный умножитель. А постарше/подороже - ещё и FPU или отдельную DSP голову, как TI OMAP, к примеру. И ничего руками настраивать не надо, достаточно указать компилятору на использование аппаратных средств Если что - извиняйте, что возьмёшь с тупого жестянщика... По мне - так div_t - оптимальный вариант, ибо обычно нужно одновременно как частное, так и остаток, и за одно действие можно получить и то, и другое.

Автор: Леопольд 30.11.2010, 18:24

Цитата(MrYuran @  30.11.2010,  16:01 ) аппаратный умножитель Делит нацело за один такт?

Автор: bsa 30.11.2010, 18:56

Цитата(MrYuran @  30.11.2010,  17:01 ) Большинство ARM контроллеров, даже начального уровня, имеют аппаратный умножитель. А постарше/подороже - ещё и FPU или отдельную DSP голову, как TI OMAP, к примеру. Cortex-M3 Processor хвастается тем, что умеет делить за 2-12 тактов. За 1 такт делить ооочень сложно. Только если по таблице. А ты попробуй таблицу для 32-х битного деления запихать в проц (подсказка - ее размер будет 2^64 слов, каждое из которых по 64 бита (остаток+частное)).

Автор: cardinal 30.11.2010, 19:43

MrYuran, посмотри примеры, которые привел azesmcar. В них никто на ассемблере не настаивает.

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)