Алгоритм целочисленного деления или хотя бы деления на 10

← →
Defunct © (2005-05-17 06:37) [0]

Может есть что-нибудь быстрее дедовского метода (вычитание + сдвиг)?

PS: Проц умеет: складывать, вычитать и умножать (аппаратно!!) (ну и сдвигать, и стандартная логика and/or)

← →
Иван Шихалев © (2005-05-17 07:10) [1]

Это что за проц такой, что делить не умеет?

← →
Defunct © (2005-05-17 07:20) [2]

> Иван Шихалев

Atmel AVR

← →
Kerk © (2005-05-17 07:34) [3]

Кнут. 2й том.

← →
Antonn © (2005-05-17 07:58) [4]

> PS: Проц умеет: складывать, вычитать и умножать
> (аппаратно!!) (ну и сдвигать, и стандартная логика
> and/or)

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

← →
Defunct © (2005-05-17 09:01) [5]

Kerk © (17.05.05 07:34) [3]

Нашел даже главу где написано про быстрое деление:
2 том. Глава 4.3.1. Алгоритм D (деление неотрицательных целых чисел)
но как назло нет у меня второго тома.. эх.

Antonn © (17.05.05 07:58) [4]
это к чему относится?

← →
Иван Шихалев © (2005-05-17 09:07) [6]

http://www.atmel.ru/Articles/Atmel21.htm

← →
Praco © (2005-05-17 09:33) [7]

Проц умеет только складывать

← →
Jeer © (2005-05-17 09:44) [8]

Деление 8-и разрядных целых беззнаковых чисел (AVR)
;*** Использование регистров

.def drem8u=r15 ;остаток
.def dres8u=r16 ;результат
.def dd8u=r16 ;делимое
.def dv8u=r17 ;делитель
.def dcnt8u=r18 ;счетчик цикла
;*****
div8u_c sub drem8u,drem8u ;очистить остаток и перенос
ldi dcnt8u,9 ;инициализировать счетчик цикла
d8u_1: rol dd8u ;делимое/результат сдвинуть влево
dec dcnt8u ;уменьшить на единицу счетчик цикла
brne d8u_2 ;переход, если не ноль
ret ;выход из подпрограммы
d8u_2: rol drem8u ;остаток сдвинуть влево
sub drem8u,dv8u ;остаток= остаток - делитель
brcc d8u_3 ;если результат < 0
add drem8u,dv8u ;восстановить остаток
clc ;сбросить перенос для формирования результата
rjmp d8u_1 ;иначе
d8u_3: sec ;установить перенос для формирования результата
rjmp d8u_1 ;вернуться назад

← →
Defunct © (2005-05-17 09:55) [9]

> Иван Шихалев

Спасибо большое, за то что прониклись моей проблемой, однако тот пример на сайте атмела работает в почти в два раза медленнее чем процедурка написанная мной (125 тактов против 77). И это при том, что у них не обрабатывается деление на 0 и плюс еще две ошибки в коде ;>

Я бы хотел как-то применить команду умножения для деления. мне бы именно алгоритм, а не код.

Большое спасибо всем кто откликнулся.
Kerk, тебе отдельное, 2-й том обязательно найду к вечеру ;>

← →
Defunct © (2005-05-17 09:57) [10]

Praco © (17.05.05 09:33) [7]

В datasheet"е четко написано - hardware multiplier.

← →
Praco © (2005-05-17 10:06) [11]

Defunct © (17.05.05 09:57) [10]
datasheet - что это?

В институте учили так:
Умножение - это многократное сложение, деление - многократное вычитание, вычитание - сложение с операндом, переведенным в дополнительный или обратный код, перевод в доп. код - примерно то же сложение.
Хотя может мои знания устарели?

← →
Defunct © (2005-05-17 10:16) [12]

> datasheet - что это?
Достоверный документ от фирмы производителя на конкретное устройство.

> Хотя может мои знания устарели?
помните табличку умножения тетрадках сзади рисовали?
вот и в процессор можно встроить ПЗУшку-таблицу умножения и выполнять табличное умножение за 1 такт.

← →
Anatoly Podgoretsky © (2005-05-17 10:41) [13]

Defunct © (17.05.05 10:16) [12]
Если будет желание потерять 128 кб, а так как стандартная ячейка памяти вроде 6 транзисторов, то можешь посчитать стоит ли овчинка выделки.

← →
Alx2 © (2005-05-17 10:43) [14]

Приближение x/10 ~ 26*x/256=x/16+x/32+x/128 не поможет?
Относительная ошибка = 1/64 т.е. целая часть начинает "врать" для x>=640

← →
TUser © (2005-05-17 10:46) [15]

Могу выслать эти разделы Кнута. Деление чисел с плавающей точкой - 6.5 М, целочисленное деление с применением длинной арифметики (алгоритм D) - 6.3 М.

← →
Alx2 © (2005-05-17 10:50) [16]

Вдогонку Alx2 © (17.05.05 10:43)
Вот, нашел источник де жа вю :)
http://www.telesys.ru/wwwboards/mcontrol/51/messages/393.shtml

← →
Jeer © (2005-05-17 11:20) [17]

Известен алгоритм деления на константу на основе умножения.
Для каждой константы свои MN и N
Приведено для asm i86
По аналогии можно перевести на asm AVR

mov eax,X
mov edx, MN
inc eax
mul edx
SHR edx, N

z = x/y
y = 123
MN = 2234779731
N = 6

← →
Sha © (2005-05-17 11:54) [18]

> Defunct © (17.05.05 06:37)
> PS: Проц умеет: ... умножать (аппаратно!!) (ну и сдвигать, и стандартная логика and/or)

Доп. вопросы:
1) какое деление интересует 8,16,32-бит ?
2) сколько бит имеет результат умножения 8х8,16х16,32х32 ?

← →
Jeer © (2005-05-17 12:18) [19]

AVR имеют аппаратный умножитель 8x8 (знаковое, безнаковое, целочисленный, дробный форматы) -> 16-битный результат за 2 такта.

← →
Sha © (2005-05-17 12:42) [20]

Для реализации беззнакового деления на 10
надо реализовать следующие алгоритмы:

08 бит: j:=(i*$CD) shr 11;
16 бит: j:=(i*$CCCD) shr 19;
32 бит: j:=(i*$CCCCCCCD) shr 35;

← →
Jeer © (2005-05-17 13:21) [21]

Добавление:
если требуется делить с округлением то

y:=(x*$CCCD) shr 18;
t := y and 1;
y := y shr 1;
if (t=1) then inc(y);

← →
Antonn © (2005-05-17 13:28) [22]

Defunct © (17.05.05 9:01) [5]
это к чему относится?
к первому посту. Все операции (при рассмотрении на "аппаратном уровне") выполняются только тремя операциями [4].
Praco © (17.05.05 9:33) [7]
не только.

> Jeer © (17.05.05 13:21) [21]
> если требуется делить с округлением то ...

можно короче, например для 08 бит:

k:=i*$CD;
j:=k shr 11;
if k and ($0400)<>0 then inc(j);

Где мне спорить со знаменитым Шароховым :)

Anatoly Podgoretsky © (17.05.05 10:41) [13]
Память ограничена.. 4kb еще можно было бы выделить, а 128k просто нет..

Alx2 © (17.05.05 10:43) [14]
хм.. попробую

TUser © (17.05.05 10:46) [15]
Буду очень благодарен!

Sha © (17.05.05 12:42) [20]
Спасибо, алгоритм - супер! Летает ;>

Antonn © (17.05.05 13:28) [22]
> Все операции (при рассмотрении на "аппаратном уровне") выполняются только тремя операциями [4].

Если уйти глубоко в аппаратную реализацию, то абсолютно все операции можно выполнить на любом функционально полном наборе логики, например - И-НЕ.

А если все же применительно к процессорам, производитель может применять на аппаратном уровне какие-то свои схемные решения, которые выходят за предел перечисленных вами операций [4] (хотя бы вы забыли про незаменимую операцию сдвига, без нее ни туда и ни сюда). В данном случае AVR выполняет 130 команд аппаратно и имеет производительность (MIPS) приблизительно равную равную тактовой частоте.

Кстати, сравнивать умеют далеко не все процессоры, например:
- C51 не имеет команд сравнения двух чисел (аналога cmp), вместо нее есть команда вычитания, что фактически одно и то же;
- В PIC нет команд условного перехода.

А разве cmp не вычетает, а результат её влияет на флаги?

cmp вычитает и не сохраняет рез-тат

Defunct © (17.05.05 23:33) [26]
я, вообще то, просто поправил PS в первом посту, сдвиг можно выполнить копированием, вычитание и умножение выполняется посредством сложения. сравнение и есть and/or.

> Defunct © (17.05.05 20:49) [25]
> Летает ;>

Чтобы летало быстрее:

Часто кроме операции div 10
бывает необходима операция mod 10.
Например, для своей реализации IntToStr.

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

Пример на BASM для IA32 ниже.

function DivMod10_Sha(var Value: cardinal): cardinal; overload; asm push eax mov eax, [eax] mov edx, $CCCCCCCD mov ecx, eax mul edx xor ecx, edx mov eax, edx and ecx, 1 and eax, 7 jnz @nzero test ecx, ecx jz @zero @nzero: sub eax, ecx add eax, 2 @zero: pop ecx shr edx, 3 mov [ecx], edx end;

Примеры использования ниже.

function IntToStr_Sha(Value: integer): string; var Buffer: array [0..11] of char; Negative, Blank: integer; begin; Negative:=0; if Value<0 then begin; Negative:=-1; Value:=-Value; end; Blank:=High(Buffer); repeat; Buffer[Blank]:=char(ord("0")+DivMod10_Sha(cardinal(Value))); dec(Blank); until Value=0; Buffer[Blank]:="-"; Blank:=Blank+Negative; SetString(Result,pchar(@Buffer[Blank+1]),High(Buffer)-Blank); end; function IntToStr_Sha2(Value: integer): string; var Pos: integer; Res: pchar; begin; Pos:=0; if Value<0 then begin; Value:=-Value; Pos:=Pos+1; end; case Value of 0..9: Pos:=Pos+1; 10..99: Pos:=Pos+2; 100..999: Pos:=Pos+3; 1000..9999: Pos:=Pos+4; 10000..99999: Pos:=Pos+5; 100000..999999: Pos:=Pos+6; 1000000..9999999: Pos:=Pos+7; 10000000..99999999: Pos:=Pos+8; 100000000..999999999: Pos:=Pos+9; else Pos:=Pos+10; end; SetLength(Result,Pos); Res:=pointer(Result); Res[0]:="-"; repeat; Res[Pos-1]:=char(ord("0")+DivMod10_Sha(cardinal(Value))); dec(Pos); until Value=0; end;

Думаю, их можно адаптировать под твой суперпроцессор.
Можно это дело еще ускорить раза в 2, если на нем сложение
раз в 10-20 быстрее умножения или есть нечто похожее на LEA.

Sha © (18.05.05 09:03) [31]
> Например, для своей реализации IntToStr.

Именно для нее и нужно было деление на 10. :)

> их при помощи единственного умножения.
Спасибо, но это уже оптимизация под x86, в AVR нахождение частного и остатка за 2 умножения (даже за 3) работает быстрее.
Еще раз большое спасибо за предложенный алгоритм!!

;----------------------------------------------------- ; Функция 8-ми разрядного целочисленного деления на 10 ;---> BL - 8-ми разрязное делимое ;<--- BL - ОСТАТОК, BH - ЧАСТНОЕ div10_8: ldi AL, $CD ; ldi - аналог mov для загрузки констант mul BL, AL ; Результат умножения в DH:DL mov BH, DH ldi AL, 0b00010000; Для сдвига на 3 fmul BH, AL ; Дробное умножение на 0.001 (shr BH, 3) mov BH, DH ; <--- BH - Частное ldi AL, 10 ; mul BH, AL sub BL, DL ; <--- BL - Остаток ret ;ps: названия регистров могут отличаться от реально используемых

> Mожно это дело еще ускорить раза в 2, если на нем сложение
> раз в 10-20 быстрее умножения или есть нечто похожее на LEA.
Сложение и умножение выполняются почти одинаково (1 и 2 такта соответственно).

Алгоритм целочисленного деления или хотя бы деления на 10 Найти похожие ветки