VPF::Остаток от деления на десять - Форум программистов

cardinal

Дата 29.11.2010, 22:40 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 2
Всего: 99

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

--------------------

Немецкая оппозиция потребовала упростить натурализацию иммигрантов
В моем блоге: Разные истории из жизни в Германии

"Познание бесконечности требует бесконечного времени, а потому работай не работай - все едино". А. и Б. Стругацкие

mes

Дата 29.11.2010, 22:50 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

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

Это сообщение отредактировал(а) mes - 29.11.2010, 22:57

--------------------

http://opendots.net

cardinal

Дата 29.11.2010, 22:55 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 2
Всего: 99

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

--------------------

mes

Дата 29.11.2010, 23:00 (ссылка)

(нет голосов)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(cardinal @ 29.11.2010, 21:55

)

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

и зря..

Добавлено через 1 минуту и 50 секунд
и с чего вобще такое желание оптимизировать это деление ? Вы уверены, что это (самое) узкое место ?

--------------------

http://opendots.net

sQu1rr

Дата 29.11.2010, 23:10 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13

Цитата

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

Добавлено через 1 минуту и 42 секунды
Это я не как способ ( он к 10 не подходит ) - а как подтверждение нецелесообразности использование оптимизации того, с чем либо компилятор справиться, либо не существенно для скорости выполнения

cardinal

Дата 29.11.2010, 23:22 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 2
Всего: 99

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

--------------------

mes

Дата 30.11.2010, 00:22 (ссылка)

(голосов:2)

Загрузка ...

любитель

Профиль
Группа: Участник Клуба
Сообщений: 7954
Регистрация: 14.1.2006

Репутация: 144
Всего: 250

Цитата(cardinal @ 29.11.2010, 22:22

)

а есть еще и другие процессоры, для которых ВСЕ существенно, каждая строка кода.

для таких пишут на других языках, позволяющих вручную контролировать каждую строчку кода..

--------------------

http://opendots.net

sQu1rr

Дата 30.11.2010, 01:28 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 597
Регистрация: 11.11.2008
Где: london

Репутация: 3
Всего: 13

Цитата

#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 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 2
Всего: 99

Цитата(mes @ 29.11.2010, 22:22

)

для таких пишут на других языках, позволяющих вручную контролировать каждую строчку кода..

Ассемблером зовется... Тогда переформулирую вопрос: как мне наиболее эффективно на ассемблере написать функцию "остаток от деления на 10"? Только не надо меня посылать теперь в другой подфорум...

sQu1rr, мне нужна не функция, а ее реализация!!! Причем простую я и сам знаю.

--------------------

Леопольд

Дата 30.11.2010, 08:15 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Цитата(cardinal @ 30.11.2010, 01:46

)

на ассемблере

Всё зависит от ассемблера.

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

Это сообщение отредактировал(а) Леопольд - 30.11.2010, 08:21

--------------------

вопросов больше чем ответов

azesmcar

Дата 30.11.2010, 08:22 (ссылка)

(голосов:1)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

Цитата(cardinal @ 29.11.2010, 23:22

)

а есть еще и другие процессоры, для которых ВСЕ существенно

Есть такое, сталкивался, оптимизировал деление на 2 и разница довольно существенная (с учетом того, что процессор был 70 мегагерцовый) smile

Код


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).

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

Это сообщение отредактировал(а) azesmcar - 30.11.2010, 09:36

Леопольд

Дата 30.11.2010, 08:52 (ссылка)

(нет голосов)

Загрузка ...

Опытный

Профиль
Группа: Участник
Сообщений: 943
Регистрация: 17.6.2009

Репутация: 10
Всего: 13

Цитата(azesmcar @ 30.11.2010, 08:22

)

требуется 64-х битный int

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

Это сообщение отредактировал(а) Леопольд - 30.11.2010, 08:54

--------------------

вопросов больше чем ответов

azesmcar

Дата 30.11.2010, 09:18 (ссылка)

(голосов:1)

Загрузка ...

uploading...

Профиль
Группа: Участник Клуба
Сообщений: 6291
Регистрация: 12.11.2004
Где: Армения

Репутация: 81
Всего: 211

Немного поигрался с отладчиком.
Этот код сгенерировала Visual Studio 2010 с настройками оптимизации, как и просил, на ассемблере smile

Используется аналогичный алгоритм.

Код


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
из той же книги.

Это сообщение отредактировал(а) azesmcar - 30.11.2010, 09:50

cardinal

Дата 30.11.2010, 10:38 (ссылка)

(нет голосов)

Загрузка ...

Инженер

Профиль
Группа: Экс. модератор
Сообщений: 6003
Регистрация: 26.3.2002
Где: Германия

Репутация: 2
Всего: 99

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

--------------------

MrYuran

Дата 30.11.2010, 11:40 (ссылка)

(нет голосов)

Загрузка ...

Новичок

Профиль
Группа: Участник
Сообщений: 2
Регистрация: 19.11.2010

Репутация: нет
Всего: нет

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

Ассемблер нужно уметь читать, но писать на нём не надо!

0 Пользователей читают эту тему (0 Гостей и 0 Скрытых Пользователей)
0 Пользователей:
« Предыдущая тема \| C/C++: Общие вопросы \| Следующая тема »