Форум программистов, компьютерный форум CyberForum.ru

Модульное деление на степень двойки - C++

Восстановить пароль Регистрация
 
 
Рейтинг: Рейтинг темы: голосов - 17, средняя оценка - 4.94
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 14:30     Модульное деление на степень двойки #1
Раньше я всегда использовал примерной такой подход :
C++
1
2
3
4
5
6
int mod = 8;
int a = 90412488;
char b = 113;
int modA, modB;
modA = a & int(mod-1);
modB = b & char(mod-1);
Понятное дело, что можно написать функцию, которая определала бы тип и была бы красивой оберткой для такого подхода, но мне хватало. Сейчас встал опять вопрос с модульным делением на 2^x. Я бы использовал этот подход, но кто-то как-то сказал мне, что такое решение в каких-то случаях выдает не верный результат или ошибки. Я напрочь забыл, кто это сказал :/
Вопрос : в чем плох такой подход и как правильно?
Скорее всего, компиляторы сами производят подобную оптимизацию, но всё же.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.12.2012, 14:30     Модульное деление на степень двойки
Посмотрите здесь:

C++ Найти степень двойки
C++ Степень двойки
Максимальная степень двойки C++
степень двойки C++
Степень двойки в степени десятки C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.12.2012, 15:29     Модульное деление на степень двойки #2
А чего ты хотел то? Что вообще значит твой исходник? Какую задачу ты решал?
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 15:48  [ТС]     Модульное деление на степень двойки #3
Цитата Сообщение от taras atavin Посмотреть сообщение
А чего ты хотел то? Что вообще значит твой исходник? Какую задачу ты решал?
Издеваетесь что ли?..
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.12.2012, 16:07     Модульное деление на степень двойки #4
Издеваешься здесь ты.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 16:13  [ТС]     Модульное деление на степень двойки #5
Цитата Сообщение от taras atavin Посмотреть сообщение
Издеваешься здесь ты.
Где же? Что не понятного то? Как подход к умножению на степень двойки при помощи битовых сдвигов, есть и обратный подход для деления и деления с остатком, то есть деления по модулю. Я привел листинг, как это делал я раньше. Некто сказал мне, что такой подход не верен в некоторых случаях. Я задал вопрос, когда этот листинг может быть не верен и почему, а так же попросил привести верный листинг.
А теперь новый вопрос : где здесь издевательство? Что здесь не понятно?.. Ей богу, только настроение испортили.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.12.2012, 16:15     Модульное деление на степень двойки #6
Цитата Сообщение от nexen Посмотреть сообщение
Как подход к умножению на степень двойки при помощи битовых сдвигов, есть и обратный подход для деления и деления с остатком, то есть деления по модулю.
И где у тебя сдвиги? Кроме того, что на что ты собирался делить, где у тебя результат и при чём здесь вообще типы из твоего поста не понятно.
WhiteP
605 / 203 / 23
Регистрация: 20.11.2012
Сообщений: 419
04.12.2012, 16:31     Модульное деление на степень двойки #7
Я так понимаю речь о взятии остатка от деления на степень двойки (деление по модулю).
Чем не устраивает modA = a % mod?
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 16:38  [ТС]     Модульное деление на степень двойки #8
WhiteP, % выполняет обычное деление по сути. Так как модуль в данном случае степень двойки, то можно написать более быстрое модульное деление. Поэтому и не устраивает обычный %. Но, как я написал, компиляторы, наверное, справляются с этим. Только как..
WhiteP
605 / 203 / 23
Регистрация: 20.11.2012
Сообщений: 419
04.12.2012, 16:48     Модульное деление на степень двойки #9
Написал тестовый пример.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
 
int mod1(int a, int mod)
{
    return a % mod;
}
 
int mod2(int a, int mod)
{
    return a & int(mod-1);
}
 
int main()
{
    int a=0, mod = 0;
    cout<<"Enter a: " ;cin>>a;
    cout<<"Enter mod: "; cin>>mod;
    cout<<"\n"<<mod1(a, mod)<<"\n";
    cout<<"\n"<<mod2(a, mod)<<"\n";
    return 0;
}
Откомпилировал студийным (VS 2012) компилятором с ключом оптимизации /O2 (Maximize speed).

Результат:

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
?mod1@@YAHHH@Z PROC                 ; mod1, COMDAT
; _a$ = ecx
; _mod$ = edx
 
; 5    : {
 
    push    esi
    mov esi, edx
 
; 6    :    return a % mod;
 
    mov eax, ecx
    cdq
    idiv    esi
    pop esi
    mov eax, edx
 
; 7    : }
 
    ret 0
Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
?mod2@@YAHHH@Z PROC                 ; mod2, COMDAT
; _a$ = ecx
; _mod$ = edx
 
; 11   :    return a & int(mod-1);
 
    lea eax, DWORD PTR [edx-1]
    and eax, ecx
 
; 12   : }
 
    ret 0
?mod2@@YAHHH@Z ENDP
Так что компилятор тут все "дословно" скомпилил. Ну это он не знает, что степень двойки, естессно.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.12.2012, 16:54     Модульное деление на степень двойки #10
Цитата Сообщение от nexen Посмотреть сообщение
WhiteP, % выполняет обычное деление по сути.
Бред. % вычисляет остаток.
WhiteP
605 / 203 / 23
Регистрация: 20.11.2012
Сообщений: 419
04.12.2012, 16:56     Модульное деление на степень двойки #11
taras atavin,
на уровне ассемблера производится деление (idiv) при котором в одном регистре - частное, а в другом остаток.
Когда нам нужно частное - выдается один регистр, а когда остаток - другой. Операция же одна и та же.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 16:57  [ТС]     Модульное деление на степень двойки #12
WhiteP, хм, сам не проверял, лишь слышал, что компиляторы давно уже научились a*16, b/32 и c%256 заменять на быстрые эквиваленты. То ли с модулем всё не так, то ли врали мне ;/
И всё же вопрос остался. В каких случаях листинг из первого сообщения выдает не правильный результат и как надо?
Sanyur
11 / 11 / 0
Регистрация: 19.03.2010
Сообщений: 101
04.12.2012, 16:57     Модульное деление на степень двойки #13
Ваш код тоже вычисляет остаток деления от степени двойки
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.12.2012, 16:58     Модульное деление на степень двойки #14
Да. Но % не возвращает результат из регистра с частным, он возвращает только остаток.
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 16:59  [ТС]     Модульное деление на степень двойки #15
Цитата Сообщение от taras atavin Посмотреть сообщение
Да. Но % не возвращает результат из регистра с частным, он возвращает только остаток.
И что? Деление выполняет обычное.
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.12.2012, 17:00     Модульное деление на степень двойки #16
Цитата Сообщение от nexen Посмотреть сообщение
В каких случаях листинг из первого сообщения выдает не правильный результат и как надо?
Сначала опиши задачу и объясни, где у тебя исходные данные, а где результат. И какое данное где.

Добавлено через 1 минуту
Цитата Сообщение от nexen Посмотреть сообщение
Деление выполняет обычное.
Деление он не выполняет, он возвращает остаток. Побочный низкоуровневый результат в виде частного при этом теряется.
Sanyur
11 / 11 / 0
Регистрация: 19.03.2010
Сообщений: 101
04.12.2012, 17:01     Модульное деление на степень двойки #17
C++
1
2
3
4
5
6
int mod = 8;//делим на 8
int a = 90412488;//что делим на 8
char b = 113;//тожесамое
int modA, modB;// остатки от деления на 8
modA = a & int(mod-1);
modB = b & char(mod-1);
Для наглядности:
a=20(10100)
делим на 16
mod=16(1000)
1000-1= 0111
получаем 10100
& 00111
_____
00100 = 4
nexen
187 / 180 / 3
Регистрация: 27.01.2012
Сообщений: 1,335
04.12.2012, 17:03  [ТС]     Модульное деление на степень двойки #18
Sanyur, я думал это и так понятно..
taras atavin
Ушёл с форума.
 Аватар для taras atavin
3569 / 1752 / 91
Регистрация: 24.11.2009
Сообщений: 27,619
04.12.2012, 17:04     Модульное деление на степень двойки #19
Будет глючить в том случае, если mod не равно целой степени двойки, если же делать проверку, то на ней потеряешь ещё больше. Вывод: применять только в тех случаях, когда априорно известно, что делитель равен целой степени двойки. И можно даже так:
C++
1
2
3
4
5
6
int mod = 8;//делим на 8
int a = 90412488;//что делим на 8
char b = 113;..тожесамое
int modA, modB;// остатки от деления на 8
modA = a & (mod-1);
modB = b & (mod-1);
. Если mod - константа, то лучше заранее вычислить mod-1, чтоб ещё больше съэкономить: целочисленное вычитание, как и целочисленное сложение хоть и быстрей деления, но всё таки не бесконечно быстрей.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
04.12.2012, 17:10     Модульное деление на степень двойки
Еще ссылки по теме:

Наибольшая целая степень двойки, не превосходящая заданного числа n C++
C++ Степень двойки для отражения размера памяти
C++ Возведение двойки в большую степень (длинное число)

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
WhiteP
605 / 203 / 23
Регистрация: 20.11.2012
Сообщений: 419
04.12.2012, 17:10     Модульное деление на степень двойки #20
Цитата Сообщение от taras atavin Посмотреть сообщение
Деление он не выполняет, он возвращает остаток. Побочный низкоуровневый результат в виде частного при этом теряется.
Просто операция деления одна из самых затратных по времени (на уровне тактов, конечно)

Добавлено через 4 минуты
Если константой заменить (a % 8), то вот так оптимизирует.

Assembler
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
?mod1@@YAHH@Z PROC                  ; mod1, COMDAT
; _a$ = ecx
 
; 6    :    return a % 8;
 
    and ecx, -2147483641            ; 80000007H
    jns SHORT $LN3@mod1
    dec ecx
    or  ecx, -8                 ; fffffff8H
    inc ecx
$LN3@mod1:
    mov eax, ecx
 
; 7    : }
 
    ret 0
?mod1@@YAHH@Z ENDP
Yandex
Объявления
04.12.2012, 17:10     Модульное деление на степень двойки
Ответ Создать тему
Опции темы

Текущее время: 12:22. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru