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

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From Russian to

Threaded View
Thu Aug 21 2003 09:31, Leha Bishletov wrote to All:


 LB>  Посоветуйте, как можно быстро поделить 20-ти битное число на 10-ти
 LB> битное? Сделать это надо максимум за 30мкс. МК с такими возможностями я
 LB> не знаю.

 Да хотя бы 68HC11 или любой другой микроконтроллер с делением 16/16.

 VLV

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


Re: Быстро поделить 20 бит на 10 бит
Thu Aug 21 2003 09:31, Leha Bishletov wrote to All:

 
 LB> Посоветуйте, как можно быстро поделить 20-ти битное число на 10-ти
 LB> битное? Сделать это надо максимум за 30мкс. МК с такими возможностями я
 LB> не знаю.

 1. Это легко сделать на любом DSP.

 2. Можно успеть на быстром AVR. Просто деление в столбик на асме.

 3. Можно сделать еще быстрее как умножение на 1/x. 1/x от 10-битного
 числа взять по табличке.

 VLV

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


Re: Быстро поделить 20 бит на 10 бит
Hello Vladimir.

Четверг Авгyст 21 2003 17:17, you wrote to me:

 LB>> Посоветуйте, как можно быстро поделить 20-ти битное число на
 LB>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими
 LB>> возможностями я не знаю.
 VV>  1. Это легко сделать на любом DSP.

 Прикидывал для MSP430 (это DSP?), получается, что для деления в столбик надо
около 400 тактов (~5 команд на бит). При его 125нс получается 50мкс - много.

 VV>  2. Можно успеть на быстром AVR. Просто деление в столбик на асме.

 Про них ни чего не знаю. Какие это?

 VV>  3. Можно сделать еще быстрее как умножение на 1/x. 1/x от 10-битного
 VV>  числа взять по табличке.

 Интересная идея, спасибо :) Hадо будет обдумать. 2кбайта на табличку не так уж
и много, а аппаратные умножители встречаются часто :)

Leha


Быстро поделить 20 бит на 10 бит
Hi Leha!
You wrote to Vladimir Vassilevsky on Fri, 22 Aug 2003 08:15:10 +0600:

[...]

LB>  Прикидывал для MSP430 (это DSP?), получается, что для деления в столбик
LB> надо около 400 тактов (~5 команд на бит). При его 125нс получается 50мкс -
LB> много.

    Что-то не так как-то ты прикидывал: на MSP430 деление float/float
выполняется за 405 тактов (см slaa024.pdf, стр. 5-99, там таблица приведена для
арифметических операций для float и double (правда, дабл там "ненастоящий", а
48-битный, но флоат - "честный", 32-битный)). Единственное, float там не
IEEE'шный, у него знак мантиссы перенесен из старшего бита всего числа в
старший бит мантиссы, и за счет этого достигается бОльшая скорость.

    А целочисленное 24/16 должно быть в несколько раз быстрее.

Bye.

### Что вы прямо как не русский, здесь же английским по белому написано.



Re: Быстро поделить 20 бит на 10 бит
Hello Oleksandr!

27 Aug 03 01:14, Oleksandr Redchuk wrote to All:

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

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



73 & Cheerio!   Andy.

Быстро поделить 20 бит на 10 бит ( ->FAQ)
Привет!

 AC> [...]

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

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

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

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


Re: Быстро поделить 20 бит на 10 бит ( ->FAQ)
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.



Быстро поделить 20 бит на 10 бит ( ->FAQ)
Hello Sergey!

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

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

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



73 & Cheerio!   Andy.

Быстро поделить 20 бит на 10 бит ( ->FAQ)
Привет 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
    http://www.altor.tk , http://altor.sytes.net ftp://altor.sytes.net




Быстро поделить 20 бит на 10 бит ( ->FAQ)

 AT> Привет Alexander!

 AC>> [...]

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

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

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

PS:
Последняя редакция cекция FAQ по Fujitsu тут
http://f2mc.nm.ru/f2mc_faq.html

_______
Сергей.

 


Без восстановления остатка [1/2] (Быстро поделить 20 бит на 10)
27-Aug-03 01:02 Andy Chernyshenko wrote to Oleksandr Redchuk:

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

AC> Интересно. Если бы кое-кто не забил на FAQ, то оно бы самое оно именно
AC> туда...
Ok. Длинновато получилось, на всяк случай двумя письмами.
Для FAQ, конечно, неплохо бы с картинками блок-схем, а тут простой
текст.

======= Алгоритм деления без восстановления остатка.

 Сначала немного бо "обычном" алгоритме, который на самом деле
"с восстановлением остатка". В нём делитель вычитается из
остатка, если заметили, что вычли много -- восстанавливается остаток.
 Разные вариации реализации этого алгоритма
* инкремент младшей части делимого, если вычитание было
правильным или же вдвигание единички/нолика из переноса при сдвиге
* вычитание и потом, если надо, восстановление или же сравнение и
вычитание
- это просто процессоро-зависимая оптимизация. Например, если
процессор не имеет отдельных команд для простого сравнивания
многобайтных слов, как AVR при помощи cp/cpc, то выгоднее вычесть
при помощи sub/sbc и глянуть на перенос. А если ещё и перенос
"как бы кривой" (при вычитании устанавливается при _отсутствии_
заёма, а при наличии - сбрасывается, угадайте с трёх раз о ком я :-),
то после вычитания перенос сразу вдвигается в результат без
инвертирования, а потом восстановление остатка делается по
проверке младшего бита результата и спецкоманды многобайтного
сравнения в этом месте даром не нужны. Ну ладно, это я отвлёкся
на тему "всё в этом мире не просто так".

 Суть алгоритма от этого не меняется
"если перевычли -- ой, исправляемся, добавляем вычтенное назад,
попробуем вычесть в 2 раза меньше".

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

Итак:
 Вычитаем делитель из остатка.
 Если результат положителен, то всё "как обычно", интереса
не представляет -- пишем единичку в младший бит результата и идём
дальше.

 А вот если результат отрицателен, то мы пишем нуль в младший
бит результата и идём по другому пути. НЕ ДОБАВЛЯЕМ делитель
к остатку. Берём и _добавляем_ _половину_ вычтенного.
Т.е. сдвигаем группу (остаток,делимое) и прибавляем делитель
к остатку. Вместо

2*((rem-divs) + divs) - divs ; восст.остатка, сдвиг, вычитание

проводим операцию

2*(rem-divs)+divs            ; сдвиг, сложение

Т.е. _делаем_вид_, что мы ничего не вычитали на предыдущем шаге,
а сейчас вычли, а не добавили. Опять смотрим на знак остатка.
Если остаток до сих пор отрицателен, то и на этом шаге вычитать
не пришлось бы, пишем 0 в младший бит результата и продолжаем
сдвигать/прибавлять. А вот если остаток стал неотрицательным,
то тогда в "обычном" алгоритме в этом месте вычитание было бы нужным,
пишем 1 в младший бит результата и опять идём на ветвь вычитания.

 Таким образом имеем как бы два цикла -- вычитания и прибавления
делителя -- с перекрёстными связями между ними. Суммарное число
проходов равно разрядности делителя, но в каждом теле есть только
одна операция -- сложения либо вычитания, и, соответственно,
одна экономится (если она выполнялась бы в "обычном" алгоритме).
Статистический выигрыш -
0.5 * число_проходов * цена_сложения_остатка_с_делимым.

Но, как я уже говорил, есть недостаток -- всегда надо знать
знак регистра остатка.
Можно расширить его разрядность то добавляются операции по сдвигу
и добавлению/вычитанию дополнительного байта, весь выигрыш пропадает.
Для расширения достаточно бы 1 бита, но... чтобы он обрабатывался
в одном цикле с остальными битами остатка, что легко реализовать
в аппаратуре, но невозможно программно в готовом процессоре.
Поэтому алгоритм подходит для деления на числа, на 1 бит меньшие,
чем имеющиеся регистры для остатка. Например, u16/u15, u32/u15,
u32/u31. Можно попытаться сохранять информацию о знаке в структуре
программы, но дополнительные проверки/переходы, опять таки, скушают
весь или большую часть выиграша.

Вот как выглядит этот алгоритм для AVR в варианте u16/u15

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

u16_15:
; 26w  3 + (10..12)*16 + (3..5) = 166..200
        ldi     cnt,16
        clr     rem_h
        clr     rem_l
lminus:
        shift_acc
        sub_divs
        brmi toplus
tominus: inc    dvd_l
        dec     cnt
        brne lminus
        ret
lplus:
        shift_acc
        add_divs
        brpl tominus
toplus: dec     cnt
        brne lplus
; если мы до самого конца в ситуации "ещё тогда вычли много",
; то для получения правильного остатка надо ещё раз прибавить
; если остаток не нужен (хотя бы для округления результата),
; то add_divs тоже не нужен.
        add_divs
        ret

Вот так это же выглядит при разворачивании цикла.
u16_15:
u16_15:
; 9+32*7+20 = 253w
; 9+(16..18)*7+(13..15) = 134..150cy
        clr     rem_h
        clr     rem_l

        shift_acc      ; 4
        sub_divs       ; 2
        brmi 2f ; nextplus

    .rept 7
        ;--------------
1:
        inc     dvd_l  ;
        shift_acc      ;
        sub_divs       ; =7
        brpl 3f ; nextminus
        rjmp 4f ; nextplus
2:
        shift_acc      ;
        add_divs       ; =6
        brmi 4f ; nextplus
        ;--------------
3:
        inc     dvd_l  ;
        shift_acc      ;
        sub_divs       ; =7
        brpl 1f ; nextminus
        rjmp 2f ; nextplus
4:
        shift_acc      ;
        add_divs       ; =6
        brmi 2f ; nextplus
    .endr
1:
        inc     dvd_l  ;
        shift_acc      ;
        sub_divs       ; =7
        brmi 4f ; nextplus
3:      inc     dvd_l
        ret
2:
        shift_acc      ;
        add_divs       ; =6
        brpl 3b ; nextminus
4:      add_divs
        ret

Маленькое объяснение - as (ассемблер из пакета gcc) поддерживает
локальные метки в виде одной цифры, в командах перехода указывается -
переход идёт вперёд (f-orward - br 1f) или назад (b-ackward - br 1b)
до ближайшей.
Поэтому тут получается так, что rjmp 2f осуществляет переход на
следующую "реализацию" тела в команде .rept либо за пределы
блока повторения.

Как я уже говорил, алгоритм без восстановления остатка даёт
выигрыш тем больше, чем больше разница в разрядности процессора
и делителя/остатка. Деление u32/u31 (в макросы добавить работу с
бОльшим числом регистров и число проходов цикла увеличить до 32)
выполняется 520..586 циклов (552..554 при выравнивании ветвей,
показано ниже для u20/u10), тогда как "обычный" алгоритм u32/u32 -
584..680 циклов.

========= продолжение следует.

Wbr,
--
/* Oleksandr Redchuk, Brovary, Ukraine */
/* real '\x40' real '\x2E' kiev '\x2E' ua     */


Re: Без восстановления остатка [1/2] (Быстро поделить 20 бит на 10)
Hello Oleksandr!

28 Aug 03 19:48, Oleksandr Redchuk wrote to Andy Chernyshenko:

[...]

TNX! Думаю, что полезно будет не только мне. И в FAQ таки войдет.



73 & Cheerio!   Andy.

Re: Быстро поделить 20 бит на 10 бит
24-Aug-03 23:43 Harry Zhurov wrote to Leha Bishletov:

HZ> выполняется за 405 тактов (см slaa024.pdf, стр. 5-99, там таблица
HZ> приведена для
HZ> арифметических операций для float и double (правда, дабл там "ненастоящий",
HZ> а
HZ> 48-битный, но флоат - "честный", 32-битный)). Единственное, float там не
HZ> IEEE'шный, у него знак мантиссы перенесен из старшего бита всего числа в
HZ> старший бит мантиссы, и за счет этого достигается бОльшая скорость.

HZ>     А целочисленное 24/16 должно быть в несколько раз быстрее.
 Не должно. Немного быстрее должно, а "в несколько" -- с чего вдруг.
У float32 мантисса 24-битная, так что целочислнное деление 24/16
будет быстрее на
- вычитание порядков
- подход-отход, связанный со знаковостью деления (я так понял,
  что 20/10 нужно беззнаковое)
- нормализация результата.
Возможно я ошибаюсь, но мне кажется, что тут и в 2 раза не набежит, не
говоря уже про большее.

wbr,



--
/* Oleksandr Redchuk, Brovary, Ukraine */
/* real '\x40' real '\x2E' kiev '\x2E' ua     */


Быстро поделить 20 бит на 10 бит
Hi Oleksandr!
You wrote to "Harry Zhurov " on Mon, 25 Aug 2003 18:58:39 +0600:

[...]

HZ>>     А целочисленное 24/16 должно быть в несколько раз быстрее.
OR>  Hе должно. Hемного быстрее должно, а "в несколько" -- с чего вдруг.
OR> У float32 мантисса 24-битная, так что целочислнное деление 24/16
OR> будет быстрее на
OR> - вычитание порядков
OR> - подход-отход, связанный со знаковостью деления (я так понял,
OR>   что 20/10 нужно беззнаковое)
OR> - нормализация результата.
OR> Возможно я ошибаюсь, но мне кажется, что тут и в 2 раза не набежит, не
OR> говоря уже про большее.

    Конкретно 24-биную арифметику не использовал (за ненадобностью, всегда
стандартного хватало). Вот результат ИАРовской библиотеки (деление чисел) из
состава последнего пакета (EW430 v2.20A):

    Тип                   Кол-во тактов

unsigned int  (16 bit)       157
signed   int  (16 bit)       183
unsigned long (32 bit)       613
signed   long (32 bit)       639
float         (32 bit)       852


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


Bye.

### Гусь тоже думал, что купается, пока вода не закипела...



Re: Быстро поделить 20 бит на 10 бит
25-Aug-03 23:12 Harry Zhurov wrote to Oleksandr Redchuk:


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.
==========
24-Aug-03 23:43 Harry Zhurov wrote to Leha Bishletov:
HZ>     Что-то не так как-то ты прикидывал: на MSP430 деление float/float
HZ> выполняется за 405 тактов (см slaa024.pdf, стр. 5-99, там таблица
HZ> приведена для
HZ> арифметических операций для float и double (правда, дабл там "ненастоящий",
HZ> а
HZ> 48-битный, но флоат - "честный", 32-битный)). Единственное, float там не
HZ> IEEE'шный, у него знак мантиссы перенесен из старшего бита всего числа в
HZ> старший бит мантиссы, и за счет этого достигается бОльшая скорость.
HZ>     А целочисленное 24/16 должно быть в несколько раз быстрее.
==========

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

wbr,
--
/* Oleksandr Redchuk, Brovary, Ukraine */
/* real '\x40' real '\x2E' kiev '\x2E' ua     */


Быстро поделить 20 бит на 10 бит
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.

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



Re: Быстро поделить 20 бит на 10 бит
29-Aug-03 07:40 Harry Zhurov wrote to Oleksandr Redchuk:

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

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,

--
/* Oleksandr Redchuk, Brovary, Ukraine */
/* real '\x40' real '\x2E' kiev '\x2E' ua     */


Re: Быстро поделить 20 бит на 10 бит
29-Aug-03 07:40 Harry Zhurov wrote to Oleksandr Redchuk:

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,
--
/* Oleksandr Redchuk, Brovary, Ukraine */
/* real '\x40' real '\x2E' kiev '\x2E' ua     */


Быстро поделить 20 бит на 10 - результат 10:10
29-Aug-03 19:03 Oleksandr Redchuk wrote to "Harry Zhurov "

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,

--
/* Oleksandr Redchuk, Brovary, Ukraine */
/* real '\x40' real '\x2E' kiev '\x2E' ua     */


Re: Быстро поделить 20 бит на 10 бит
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)


Site Timeline