Целочисленное деление на константу

[orinoko]

Подскажите пожалуйста реализацию целочисленного деления 3-байтного беззнакового числа на константу (а конкретно - на 200). АТмега128, ассемблер, 16 МГц. Ограничение по времени выполнения - не более 80 мкс. Хочу оптимизировать часть программы - но вот что-то у меня такая задача в тупик поставила.

[ibiza11]

здесь посмотрите http://www.atmel.com/Images/doc0936.pdf
и здесь http://www.mikrocontroller.net/articles/AVR_Arithmetik

[orinoko]

Спасибо. Надо будет внимательно поизучать.

[a_skr]

откомпилировал в WinAVR простую строчку b = a / 200; для 32-разрядных беззнаковых переменных. в симуляторе выполняется за 600 с небольшим тактов (пробовал с разными значениями вплоть до 0xFFFFFF). итого, для 16 МГц - не более 40 мкс.
вот ассемблерный листинг (убрал немного лишнего, можно еще сократить), может, поможет:

Спойлер

Код: Выделить всё

; вход:
; r22 - r25 - делимое
; r18 - r21 - делитель (=200)
	...
	call udivmodsi4
	...
; выход:
; r22 - r25 - частное

udivmodsi4:
	ldi	r26, 0x21	; 33
	mov	r1, r26
	sub	r26, r26
	sub	r27, r27
	movw	r30, r26
	rjmp udivmodsi4_ep
udivmodsi4_loop:
	adc	r26, r26
	adc	r27, r27
	adc	r30, r30
	adc	r31, r31
	cp	r26, r18
	cpc	r27, r19
	cpc	r30, r20
	cpc	r31, r21
	brcs udivmodsi4_ep
	sub	r26, r18
	sbc	r27, r19
	sbc	r30, r20
	sbc	r31, r21
udivmodsi4_ep:
	adc	r22, r22
	adc	r23, r23
	adc	r24, r24
	adc	r25, r25
	dec	r1
	brne udivmodsi4_loop
	com	r22
	com	r23
	com	r24
	com	r25
	ret

[orinoko]

спасибо за то, что отклюкнулись, сохраню на всякий случай, но я только что закончил делать для 24-разрядных. получилось, и даже делит правильно , по времени 28 мкс.

[ChipKiller]

получилось, и даже делит правильно , по времени 28 мкс.

... можно вспомнить, что X/((0x10000/200)/0x10000)=(X*~328)>>16 ... возможно получится быстрее

[Gudd-Head]

Поделить пополам сдвигом вправо, перевести в BCD и отбросить 2 младшие цифры

[ibiza11]

а потом обратно в Bin перевести надо.

[ChipKiller]

Поделить пополам сдвигом вправо, перевести в BCD

.. так уж точно будет не быстрее . ТС не написал какая точность нужна и есть ли аппаратное умножение ...
PS. если нужно точнее можно так X/200=(X*83886)>>24 ... 24 сдвига конечно делать не надо

[Gudd-Head]

обратно в Bin перевести надо.

Об этом ТС не говорил

[orinoko]

Умножения с дикими числами - это перебор, как по моему, делить "примерно" тоже не подходит. У меня идёт расчёт среднеквадратического значения.

есть ли аппаратное умножение

Я написал тип МК, там есть умножитель 8*8=16. А в общем то вопрос решён

[Gudd-Head]

Умножения с дикими числами - это перебор

Да ладно... несколько 2-х тактных операций умножения и сложения.

[orinoko]

Можно попробовать ради интереса. И сравнить.

[Kavka]

PS. если нужно точнее можно так X/200=(X*83886)>>24 ... 24 сдвига конечно делать не надо

При делении 16 битного числа 32х разрядов не хватает, однако. Надо разрядность промежуточного результата увеличивать до 40бит (ну или перенос учитывать, реально 33 бита надо).
И занижает на единицу местами. Вот так точно ((X+1)*83886)>>24
Если с аппаратным умножением делать, то по моим прикидкам 16bit * 24bit = 40bit выльется в 6 умножений 8*8=16 и 22 сложения (8 битных). Если всё на регистрах, то это 34 такта, плюс накладные расходы.

по времени 28 мкс.

Если не ошибаюсь, то это около 450 тактов получается на 16 мегагерцах.

[КРАМ]

У меня идёт расчёт среднеквадратического значения.

И что из этого следует?

[orinoko]

Если с аппаратным умножением делать, то по моим прикидкам 16bit * 24bit = 40bit выльется в 6 умножений 8*8=16 и 22 сложения (8 битных). Если всё на регистрах, то это 34 такта, плюс накладные расходы.

Если всё делать в регистрах, то может, причём это очень оптимистично. Но количество регистров, допускаемых для этой операции, не резиновое, поэтому, если будут добавляться операции с памятью...

У меня идёт расчёт среднеквадратического значения.

И что из этого следует?

Это было к тому, что предлагалось умножить на ~328

[El-Eng]

Поделить на 200 (точнее на 200.0001907) можно и так:

( X SHR 8 )+( X SHR 10 )+( X SHR 13 )-( X SHR 18 )-( X SHR 20 )-( X SHR 23 )

Понятно, что при реализации все число X сдвигать не надо.

[ChipKiller]

Если всё делать в регистрах, то может, причём это очень оптимистично. Но количество регистров, допускаемых для этой операции, не резиновое, поэтому, если будут добавляться операции с памятью...

... согласен - быстродействие и размер в большей степени "съедят" не умножения а пересылки, но в любом случае будет побыстрее 28 мкс.

Это было к тому, что предлагалось умножить на ~328

.. ошибка при округлении присутствует все равно. Точность (X*~328)>>16 можно повысить т.е. (X*327,68)=X*(328 - 0.32)=X*328-X*(32*2,56/256)=X*328-X*(81,92/256) и наконец в итоге ((X*328)-(X*82)>>8)>>16.
Т.к. (X*328)=(X*0x148)=X<<8+X*0x48 - имеем в итоге 4 умножения и кучу пересылок

[ChipKiller]

Код: Выделить всё

...

Понятно, что при реализации все число X сдвигать не надо

если сдвиг не кратен 8, то двигать придется много

И занижает на единицу местами. Вот так точно ((X+1)*83886)>>24

...возможно что то упустил, но откуда вместо X, (X+1) не понял....

[El-Eng]

если сдвиг не кратен 8, то двигать придется много

Не так и много: пять сдвигов двухбайтных чисел, два однобайтного, один SWAP и взять старший бит исходного числа.