проблема: у процессора нет команды целочисленного деления (FPU тоже нет)
как реализовать деление на 24, чтобы оно работало быстро (так чтобы, можно было
пользоваться им внутри длинных циклов).
умножение на 24 реализуется просто: a * 24 = a*(8 + 16), т.е. два сдвига:

b = a << 3; // a*8
res = b + (b << 1); // res = a*8 + a*16

хотелось бы что нибудь подобное для операции деления на эту константу.

Здравствуйте, Тимошенко Антон Валентинович, Вы писали:

ТАВ>проблема: у процессора нет команды целочисленного деления (FPU тоже нет)
ТАВ>как реализовать деление на 24, чтобы оно работало быстро (так чтобы, можно было
ТАВ>пользоваться им внутри длинных циклов).
ТАВ>умножение на 24 реализуется просто: a * 24 = a*(8 + 16), т.е. два сдвига:


ТАВ>b = a << 3; // a*8
ТАВ>res = b + (b << 1); // res = a*8 + a*16

ТАВ>хотелось бы что нибудь подобное для операции деления на эту константу.
а в итоге деления что ты хочешь получить?

25/24 что будет?

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

Здравствуйте, IceLoveR, Вы писали:

ILR>Здравствуйте, Тимошенко Антон Валентинович, Вы писали:

ТАВ>>проблема: у процессора нет команды целочисленного деления (FPU тоже нет)
ТАВ>>как реализовать деление на 24, чтобы оно работало быстро (так чтобы, можно было
ТАВ>>пользоваться им внутри длинных циклов).
ТАВ>>умножение на 24 реализуется просто: a * 24 = a*(8 + 16), т.е. два сдвига:


ТАВ>>b = a << 3; // a*8
ТАВ>>res = b + (b << 1); // res = a*8 + a*16

ТАВ>>хотелось бы что нибудь подобное для операции деления на эту константу.
ILR>а в итоге деления что ты хочешь получить?

ILR>25/24 что будет?

я хочу целочисленное деление с остатком.
25/24 = 1, остаток 1
смысл — вычисление индекса в массиве (матрице), который представляет
равномерное разбиение пространства на блоки размером 24. Остаток от деления = координата точки внутри блока.
Так что нужны оба эти числа. Раньше я работал с блоком размером 16, так тут все решалось простым сдвигом (целая часть)
и маскированием младших 4 битов (остаток). Теперь нужен блок размером 24...

Здравствуйте, Тимошенко Антон Валентинович, Вы писали:

ТАВ>проблема: у процессора нет команды целочисленного деления (FPU тоже нет)
Те пишешь под какуюто странную железку?
Незнаю поможет или нет но вот что VC++8 нагенерил из этого кода

__declspec(noinline)
unsigned int get()
{
    return GetTickCount() % 123;
}
__declspec(noinline)
void print(unsigned int i, unsigned int j, unsigned int k)
{
    std::cout << i << " " << j << " " << k;
}
int main()
{
    unsigned int i = get();
    unsigned int j = i / 24;
    unsigned int k = i % 24;
    print(i, j, k);
    return 0;
}

?get@@YAIXZ PROC                    ; get

; 5    :     return GetTickCount() % 123;

    call    DWORD PTR __imp__GetTickCount@0
    xor    edx, edx
    mov    ecx, 123                ; 0000007bH
    div    ecx
    mov    eax, edx

; 6    : }

    ret    0
?get@@YAIXZ ENDP                    ; get

?print@@YAXIII@Z PROC                    ; print
; _j$ = ecx
; _k$ = eax

; 9    : {

    push    ebp
    mov    ebp, esp
    and    esp, -8                    ; fffffff8H

; 10   :     std::cout << i << " " << j << " " << k;

    mov    edx, DWORD PTR _i$[ebp]
    push    eax
    push    ecx
    push    ecx
    push    ecx
    push    edx
    push    OFFSET ?cout@std@@3V?$basic_ostream@DU?$char_traits@D@std@@@1@A ; std::cout
    call    ??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QAEAAV01@I@Z ; std::basic_ostream<char,std::char_traits<char> >::operator<<
    push    eax
    call    ??$?6U?$char_traits@D@std@@@std@@YAAAV?$basic_ostream@DU?$char_traits@D@std@@@0@AAV10@PBD@Z ; std::operator<<<std::char_traits<char> >
    add    esp, 8
    push    eax
    call    ??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QAEAAV01@I@Z ; std::basic_ostream<char,std::char_traits<char> >::operator<<
    push    eax
    call    ??$?6U?$char_traits@D@std@@@std@@YAAAV?$basic_ostream@DU?$char_traits@D@std@@@0@AAV10@PBD@Z ; std::operator<<<std::char_traits<char> >
    add    esp, 8
    push    eax
    call    ??6?$basic_ostream@DU?$char_traits@D@std@@@std@@QAEAAV01@I@Z ; std::basic_ostream<char,std::char_traits<char> >::operator<<

; 11   : }

    mov    esp, ebp
    pop    ebp
    ret    0
?print@@YAXIII@Z ENDP                    ; print

_main    PROC

; 13   : {

    push    esi

; 14   :     unsigned int i = get();

    call    ?get@@YAIXZ                ; get
    mov    esi, eax

; 15   :     unsigned int j = i / 24;
; 16   :     unsigned int k = i % 24;

    mov    eax, -1431655765            ; aaaaaaabH
    mul    esi
    mov    ecx, edx
    shr    ecx, 4
    lea    eax, DWORD PTR [ecx+ecx*2]
    add    eax, eax
    add    eax, eax
    add    eax, eax
    mov    edx, eax
    mov    eax, esi
    sub    eax, edx

; 17   :     print(i, j, k);

    push    esi
    call    ?print@@YAXIII@Z            ; print
    add    esp, 4

; 18   :     return 0;

    xor    eax, eax
    pop    esi

; 19   : }

    ret    0
_main    ENDP

Что тут происходит не разбирался. Но может поможет.

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

если скажем, что разрядность 32 бит, а делимо не превышает 16 бит, то:

result = (param*0x5555)>>19;

что то же самое:

result = (param*0xAAAA)>>20;

Здравствуйте, WolfHound, Вы писали:

;тут в esi исходное число
    mov    eax, -1431655765            ; aaaaaaabH
    mul    esi
    mov    ecx, edx
    shr    ecx, 4
;тут в ecx получается частное
    lea    eax, DWORD PTR [ecx+ecx*2]
    add    eax, eax
    add    eax, eax
    add    eax, eax
;тут в eax получается частное*24
;единственное чего я не понял это почему в место одного
;shl eax, 3
;использованы 3
;add    eax, eax
;??? Ктонибудь это может объяснить? Можут тут какоето хитрое спаривание комманд?
;или это по томучто VC++8.0 beta 1 и просто не всех тараканов из оптимизатора выловили?
    mov    edx, eax
    mov    eax, esi
    sub    eax, edx
;тут в eax получается остаток

WolfHound wrote:
>
> ;единственное чего я не понял это почему в место одного
> ;shl eax, 3
> ;использованы 3
> ;add eax, eax
> ;??? Ктонибудь это может объяснить? Можут тут какоето хитрое спаривание комманд?
> ;или это по томучто VC++8.0 beta 1 и просто не всех тараканов из оптимизатора выловили?

Хмм.. вопрос интересный. Есть подозрение что "shl eax, 3" скорее всего
равно "eax * 8" в то время как "3 add eax, eax" == "shl eax, 1.5" (точно
не помню, проверьте пожалуйста).

Ну и add для П4 это дешево, он их может делать несколько штук за такт.
Кроме того есть подозрение что команда кодирует аргументы "в себе" и
процесору будет быстрее ее парсить, размер опкода тоже должен быть
поменьше других команд подхлдящих для этой цели. Вообщем лутше пока ниче
нет для умножения на 3.

Здравствуйте, Тимошенко Антон Валентинович, Вы писали:

ТАВ>проблема: у процессора нет команды целочисленного деления (FPU тоже нет)
ТАВ>как реализовать деление на 24, чтобы оно работало быстро (так чтобы, можно было

В общем, вот что получилось. Использована идея с умножением на 0x5555. Умножение реализовано через сдвиги. Правда (любимый) компилятор от МС заменил все наши старания на imul (гад!). А IC оставил как есть, и дернул МС почти на 1 сек.

#include <iostream>
#include <cstdlib>
#include <ctime>
#define NOMINMAX
#include <windows.h>

int Add[48], Mod[48];

void Fill()
{
   int i;
   for( i = 0; i<24; ++i )
   {
      Add[i] = 0;
      Mod[i] = i;
   }
   for( i = 0; i<24; ++i )
   {
      Add[i+24] = 1;
      Mod[i+24] = i;
   }
}

inline void Magic( int n, int &a, int &b )
{
   a = n;
   a = (a<<2)+a;
   a = (a<<4)+a;
   a = (a<<8)+a;
   a >>= 19;
   b = a<<3;
   b += (b<<1);
   b = n-b;
   a += Add[b];
   b = Mod[b];
}

int main()
{
   Fill();
   srand( time( NULL ) );
   int n, a, b, res = 0, time = ::GetTickCount();
   for( n = 100000000; n>=0; --n )
   {
      Magic( rand()*2+rand(), a, b );
      res += (a+b);
   }
   std::cout << res << std::endl;
   std::cout << (::GetTickCount()-time)/1000.0 << std::endl;
   return 0;
}