Быстро поделить 20 бит на 10 бит

HZ>>> А целочисленное 24/16 должно быть в несколько раз быстрее. OR>> Hе должно. Hемного быстрее должно, а "в несколько" -- с чего вдруг. [...]

HZ> unsigned int (16 bit) 157 HZ> unsigned long (32 bit) 613 HZ> signed long (32 bit) 639 HZ> float (32 bit) 852 тю, ты же вроде бы говорил про 405 тактов для float. ==========

HZ> Судя по значениям для 16-и и 32-х бит, для 24-х должно быть в районе HZ> 300-400 тактов, т.ч. в два раза по сравнению с флоатом оно может спокойно HZ> выйти. Ну тут наверное терминологическая путаница :-) Ты-то говорил о "нескольких разах". А для меня "в несколько раз" - это в 3-4 раза. В 1.5-2.5 раза - это "в пару раз".

wbr,

Привет!

AC> [...]

OR>> Кому-то продолжение этой темы (про "без восстановления остатка") OR>> интересно? А то влом писать, если никому не надо

AC> Интересно. Если бы кое-кто не забил на FAQ, то оно бы самое оно именно AC> туда...

Что самое интересно - "кое-кто" отвечает на запросы, что мол сегодня! вечером! добавлю! и исправлю! и ... пропал на несколько месяцев ... Так несколько раз, а исправления так и ждут своего часа на протяжении двух лет... Просил убрать мои ответы (чтоб людей в заблуждение не вводить), времени на это надо 5 сек, так и этого не делает...

Бяда у нас с "RU.EMBEDDED FAQ". _______ Сергей.

Hi Oleksandr! You wrote to "Harry Zhurov " on Wed, 27 Aug 2003 00:14:27 +0600:

HZ>> unsigned int (16 bit) 157 HZ>> unsigned long (32 bit) 613 HZ>> signed long (32 bit) 639 HZ>> float (32 bit) 852 OR> тю, ты же вроде бы говорил про 405 тактов для float.

Так и есть. Только то было про Floating-Point Package от TI, который, типа, оптимизированный, и формат числа там не IEEE'шный (знак мантиссы они перенесли из байта порядка в мантиссу - утверждают, что это дает ощутимый выигрыш по скорости). А эти цифры - про ИАРовскую RTL (со стандартным форматом).

HZ>> Судя по значениям для 16-и и 32-х бит, для 24-х должно быть в районе HZ>> 300-400 тактов, т.ч. в два раза по сравнению с флоатом оно может спокойно HZ>> выйти. OR> Hу тут наверное терминологическая путаница :-) OR> Ты-то говорил о "нескольких разах". OR> А для меня "в несколько раз" - это в 3-4 раза. OR> В 1.5-2.5 раза - это "в пару раз".

Hаверное. Эти цифры вообще просто определяют, как бы, порядок (для соотношения величин привел) - при других делимом и делителе они могут быть заметно другими. Hапример, я пробовал несколько вариантов (просто, этот был первым, и я зафиксировал значения), так в одном случае "unsigned long" поделилось за четыреста с копейками тактов, т.е. почти в полтора раза быстрее, чем в приведенном варианте.

Bye.

### Если вам не нравятся наши сборы, мы вам устроим более другие.

Hello, Sergey! You wrote to Andy Chernyshenko on Wed, 27 Aug 2003 06:23:24 +0400:

SP> Бяда у нас с "RU.EMBEDDED FAQ".

Кстати, да. Какое-то время тому назад я отсылал описание алгоритма обработки измерений периода - и ничего.

With best regards, Alexander Derazhne.

Hello Sergey!

Давно и безнадежно... Видимо, самое простое решение - если кто-то ответственно и квалифицированно возьмется продолжать ведение FAQ, пусть и "альтернативного". Hасколько я понимаю, такой ход ничему не противоречит и не требует каких-либо согласований.

Привет Andy!

Wednesday August 27 2003 23:28, Andy Chernyshenko wrote to Sergey Pinigin:

AC> Hello Sergey! AC>

AC> 27 Aug 03 07:23, Sergey Pinigin wrote to Andy Chernyshenko: AC>

AC> [...] AC>

SP>> Бяда у нас с "RU.EMBEDDED FAQ". AC>

AC> Давно и безнадежно... Видимо, самое простое решение - если кто-то AC> ответственно и квалифицированно возьмется продолжать ведение FAQ, пусть и AC> "альтернативного". Hасколько я понимаю, такой ход ничему не противоречит и AC> не требует каких-либо согласований.

Я могу у себя на сайте или ftp выложить.

Alexander Torres, 2:461/28 aka 2:461/640.28 aka 2:5020/6400.28 aka snipped-for-privacy@yahoo.com

AT> Привет Alexander!

AC>> [...]

SP>>> Бяда у нас с "RU.EMBEDDED FAQ".

AC>> Давно и безнадежно... Видимо, самое простое решение - если кто-то AC>> ответственно и квалифицированно возьмется продолжать ведение FAQ, пусть AC>> и "альтернативного". Hасколько я понимаю, такой ход ничему не AC>> противоречит и не требует каких-либо согласований.

AT> Я могу у себя на сайте или ftp выложить. "Где выложить FAQ?" - не самая важная проблема, таких мест море (общеизвестных и надежных). "Кто его будет вести?" - вот в чем вопрос!!!

PS: Последняя редакция cекция FAQ по Fujitsu тут

Ей, люди! Честное слово, я не хотел! :-)

HZ> Похоже, что ты был прав насчет "в пару раз": нарыл (в одном из HZ> Application HZ> Report'ов) процедурку деления 32/16, она занимает 234 такта.

HZ> public Div32by16u HZ> rseg CODE HZ> Div32by16u: HZ> push r11 HZ> clr IRACL ; CLEAR RESULT HZ> mov #17,IRBT ; INITIALIZE LOOP COUNTER

Смотрел на этот код, смотрел.... Далеко не сразу въехал - что же он делает :-))) Тут специфика одна вылезла - я пару раз в жизни писал себе деление неравных по разрядности чисел и оба раза мне нужно было частное в разрядности _делимого_. Т.е. u16/u8 -> u16, остаток u8 u32/u16 -> u32, остаток u16

Это были масштабирования типа x*a/b, где x, a, b, скажем, 8-битные, но результат будет >8 бит и т.п.

Соответственно в голове лежат именно такие деления для "неравных" операндов. А приведенный HZ исходник из аппнот msp430 делит u32/u16 -> u16, остаток u16, признак переполнения.

Так что если вопрошавшему надо u20/u10 -> u10, то деление можно переписать под такой вариант и выйдет ещё быстрее :-) Только в начале надо будет сдвигать влево не на 4 бита, а на 2, чтобы получить в dvd_h 10 старших бит делимого и число проходов цикла будет отнюдь не 20.

wbr,

Mon Aug 25 2003 19:58, Oleksandr Redchuk wrote to "Harry Zhurov ":

OR> Hе должно. Hемного быстрее должно, а "в несколько" -- с чего вдруг. OR> У float32 мантисса 24-битная, так что целочислнное деление 24/16 OR> будет быстрее

Кстати, о делении. Cамый быстрый способ - это все-таки не делить, а умножать на 1/x. 1/x - хорошая функция, которую можно быстро считать по методу Hьютона с начальным приближением по табличке. При том одно деление разменивается на несколько умножений. При аппаратном умножении получается явный выигрыш. Естественно, можно просто взять 1/x таблично, если позволяет память.

VLV

"Точность попадания компенсируется диаметром изделия" (c)

HZ> Application HZ> Report'ов) процедурку деления 32/16, она занимает 234 такта. Вот вариант, Точнее - от 225 до 242 тактов. Вот что меня удивляет -- аппноты вроде бы ж призваны в том числе привлечь на свою сторону народ, только знакомящийся с семейством по этим бумажкам... И почему тогда код в них не оптимален?

Они анализируют переполнение при делении. Почему-то на каждом шаге. Тогда как переполнение можно предсказать ещё не деля. Не знаю так же -- почему для частного заведён отдельный регистр. Даже если это продиктовано соглашениями о вызовах -- выгоднее в конце просто переслать... Короче, (точнее, быстрее :-), вот мой вариант (имена сохранены, IROP2M, IROP2L - делимое, IROP1 делитель, частное в IROP2L вместо IRACL, остатко в IROP2M):

DIVIDE cmp IROP1,IROP2M jnc DIV1 ; IROP2M >= IROP1, будет переполнение setc ret DIV1 mov #16,IRBT DIV2 rla IROP2L rlc IROP jc DIV3 cmp IROP1,IROP2M jnc DIV4 DIV3 sub IROP1,IROP2M inc IROP2L DIV4 dec IRBT jnz DIV2 clrc ret

Если я ничего не напутал в значении бита C при cmp через сложение то тогда код правильный :-) И выполняться будет за 154..202 такта... По сравнению с аппнотовыми 225..242. И вроде бы даже короче на слово...

wbr,

HZ>> push r11 HZ>> clr IRACL ; CLEAR RESULT HZ>> mov #17,IRBT ; INITIALIZE LOOP COUNTER

OR> Смотрел на этот код, смотрел.... Далеко не сразу въехал - что же он OR> делает :-))) OR> Тут специфика одна вылезла - я пару раз в жизни писал себе деление OR> неравных по разрядности чисел и оба раза мне нужно было частное OR> в разрядности _делимого_. Т.е. OR> u16/u8 -> u16, остаток u8 OR> u32/u16 -> u32, остаток u16 [...] OR> Так что если вопрошавшему надо u20/u10 -> u10, то OR> деление можно переписать под такой вариант и выйдет OR> ещё быстрее :-) OR> Только в начале надо будет сдвигать влево не на 4 бита, а на 2, И не делимое, а делитель :-)

Вход: (dvd_h,dvd_m,dvd_l) - 20-битное делимое (divs_h,divs_l) - 10-битный делитель Выход: при переполнении возвращается C=1, иначе C=0 и (dvd_m,dvd_l) - 10-битное частное (divs_h,divs_l) - 10-битный остаток

.macro shift_acc add dvd_l,dvd_l rol dvd_m rol dvd_h .endm .macro sub_divs sub dvd_m,divs_l sbc dvd_h,divs_h .endm .macro add_divs add dvd_m,divs_l adc dvd_h,divs_h .endm

ff20_10: ; 43w, 121cy ; align MSB of 10 bit divisor to MSB of 20 bit divident .rept 2 add divs_l,divs_l rol divs_h .endr

cp dvd_m,divs_l cpc dvd_h,divs_h brcc overflow

ldi cnt,10 lminus: shift_acc sub_divs brmi toplus tominus: inc dvd_l dec cnt brne lminus rjmp makeresult

lplus: shift_acc add_divs brmi toplus inc dvd_l dec cnt brne lminus rjmp makeresult

toplus: dec cnt brne lplus add_divs

makeresult: mov divs_l,dvd_m mov divs_h,dvd_h andi dvd_m,0x03 ; (dvd_m,dvd_l) = 10 bits of quotient .rept 2 asr divs_h ror divs_l .endr clc ret

overflow: sec ret

Итого 121 цикл на деление. Даже на 8-мегагерцовом AVR будет 15.125 мкс.

wbr,