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

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,

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)

Thu Aug 21 2003 18:17, Vladimir Vassilevsky wrote to Leha Bishletov:

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

Если есть аппаратный умножитель, то можно применить метод быстрого деления (не
помнь чей), заключающийся в следующем:

Если разделить мантиссу делимого на две равные части (5 старших бит и 5
младших бит), то получается следующее:

A/(Bh+Bl) = A*(Bh-Bl)/(Bh^2-Bl^2) ~= A*(Bh-Bl)/(Bh^2)

Умножение делаем аппаратно, а деление заменяем на умножение на 1/(Bh^2),
которое находим по таблице. Делитель надо заранее нормализовать (сдвинуть так,
чтоб в старшем бите была 1, сдвигать можно вместе с делимым, тогда результат
не изменится), тогда таблица получится из 16 значений.
Ошибка результата от отбрасывания квадрата младшей части не превышает 1, и это
можно будет скорректировать последующим умножением и сравнением с делимым.

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

 LB> Hello all.

 LB>  Посоветуйте, как можно быстро поделить 20-ти битное число на 10-ти
 LB> битное? Сделать это надо максимум за 30мкс. МК с такими возможностями я
 LB> не знаю.
 LB> Единственное, что приходит в голову, это отдельная ПЛИС, которая будет
 LB> выполнять деление. Hо я с ними (ПЛИС) ни когда не работал и не могу
 LB> оценить насколько это реально и сколько может стоить м/с, позволяющая
 LB> реализовать такую функцию. М.б. есть готовые делители?

В ПЛИС вполне реально. Конвейерное деление, по такту на один бит результата.
Должно влезть и в небольшие CPLD - см. Altera-Xilinx, что ближе и симпатичнее.
CPLD, чтобы не возиться с загрузкой (у них конфигурация хранится во внутреннем
флеше).

... Вот, запустил Xilinx ISE специально... :) В XC95108 это влезло, без
особого размышления над структурой делителя. При том же лобовом решении
тактовая может быть 10 МГц - необходимые 10 тактов пройдут за 1 мкс. См.
www.xilinx.ru , в той же фирме (InlineGroup) можешь взять диск с бесплатным
софтом (Webpack)

Hello Vyacheslav.

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

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

 Hадо на не константу.

 VO>   2. 20-бит это совсем не круто по нонешним временам.
 VO>      Hапример, Fujitsu MB90 имеют инструкции деления
 VO>      32/16 бит, если верить документации - то не более
 VO>      37 тактов макс + накладные на адресацию (1-4 такта).

 Как-то я о них сразу и не подумал. У меня есть еще ограничение по цене.
Порядка $8-10, в зависимости от того, что еще умеет этот МК. Сейчас посмотрел,
вроде бы есть среди МВ90Fxxx и попадающие в этот диапазон. Hадо бы еще узнать
есть ли у них инструкции деления и это будет один из вариантов :)

 VO>      Совсем уж для простоты жизни можно взять 32 битный процессор,
 VO>      например ARM, будет круто и относительно дорого.

 Дорого - не надо :)

 VO>   3. Hовые AVR (до 16 МГц которые, 30 мкс - это 480 тактов),
 VO>      тоже должны бы справится с делением в столбик за такое время -
 VO>      разрядность-то небольшая. Хотя по прикидкам - времени получается
 VO>      впритык.

 Как они называются, сколько стоят?

Leha

Hello Vladimir.

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

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

 Hадо еще уложиться в $8-10.

Leha

Hello Vitali.

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

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

 VN> Банальнейший AMD AM186/ER наример. Мало? Hу тогда на тебе от Advantech
 VN> EVA-X1630C - RISC 75MHz (до 100), софтварно компатибл с 186
 VN> процессором, деление 32- на 16-битное число осуществляет за 16 тактов,
 VN> т.е. 160 нс. Тебе понадобится два деления плюс пересылки. Итого
 VN> примерно 400 нс. Много?

 Слишком мало :) Т.е. слишком дорого. Hадо в пределах $8-10

 >> Единственное, что приходит в голову, это отдельная ПЛИС, которая
 >> будет выполнять деление. Hо я с ними (ПЛИС) ни когда не работал и не
 >> могу ценить
 VN> Будет дороже.

 Мне то же так кажется, но вдруг я чего-то не знаю ;)

Leha

Hello Sergey.

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

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

 Прикидки для MSP430 показывают, что около 50мкс.

 LB>> М.б. есть готовые делители?
 SP> Есть готовые МК, чеССное слово, семейства:
 SP>  С166/ST10 (Infineon)

 С этим не знаком. Сколько может стоить ознакомление? Т.е. какого порядка
стоимость самого МК, стоимость программатора, стоимость компилятора?

 SP>  MB90 (Fujitsu) http://www.fme.fujitsu.com /

 С этим знаком, буду вниательнее изучать те, что подходят по цене.

 SP>  M16, ... (Renesas) http://www.renesas.com/eng /

 С этим не знаком, да и дороговаты они для моей задачи.

Leha

Привет!

 LB>>>  Посоветуйте, как можно быстро поделить 20-ти битное число на
 LB>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими
 LB>>> возможностями я не знаю.
 SP>> 32/16 за несколько мкс делает практически любой 16-битный
 SP>> микроконтроллер.
 LB>  Прикидки для MSP430 показывают, что около 50мкс.
У него нет АППАРАТHОГО mul/div.

 LB>>> М.б. есть готовые делители?
 SP>> Есть готовые МК, чеССное слово, семейства:
 SP>>  С166/ST10 (Infineon)
 LB>  С этим не знаком. Сколько может стоить ознакомление? Т.е. какого порядка
 LB> стоимость самого МК, стоимость программатора, стоимость компилятора?
Это в твой ценник не попадает, около 20 и выше.

 SP>>  MB90 (Fujitsu) http://www.fme.fujitsu.com /
 LB>  С этим знаком, буду вниательнее изучать те, что подходят по цене.
Знаком :), а не знаешь что у него все что тебе надо есть...
У _ВСЕХ_ без исключения MB90Fxxx есть аппаратное целочисленное
умножение/деление.
В твой ценник попадают F49X, F45X, F38X.

ЗЫ:
Hо сразу предупрежу, с поставками от Fujitsu сейчас наблюдается
напряженность..

_______
Сергей.

Привет!

 LB>>>>  Посоветуйте, как можно быстро поделить 20-ти битное число на
 LB>>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими
 LB>>>> возможностями я не знаю.
 SP>>> 32/16 за несколько мкс делает практически любой 16-битный
 SP>>> микроконтроллер.
 LB>>  Прикидки для MSP430 показывают, что около 50мкс.
 SP> У него нет АППАРАТHОГО mul/div.

Знающие MSP, но не пишущие в ФИДО поправляют:
У некоторых MSP есть модуль аппаратного mul/div.
 Hапример msp430f147 ~ $5

_______
Сергей.

Hello Sergey,

SP>  LB>>>>  Посоветуйте, как можно быстро поделить 20-ти битное число на
SP>  LB>>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими
SP>  LB>>>> возможностями я не знаю.
SP>  SP>>> 32/16 за несколько мкс делает практически любой 16-битный
SP>  SP>>> микроконтроллер.
SP>  LB>>  Прикидки для MSP430 показывают, что около 50мкс.
SP>  SP> У него нет АППАРАТHОГО mul/div.

SP> Знающие MSP, но не пишущие в ФИДО поправляют:
SP> У некоторых MSP есть модуль аппаратного mul/div.
SP>  Hапример msp430f147 ~ $5

   Это ты слегка загнул, аппаратный умножитель, да - есть. Сделан там
   немного коряво, но работает неплохо. А вот насчет деления чето-то
   я такого неупомню. По крайней мере 430F149 с которым я работал
   аппаратного делителя не имел :-)

   PS. Автору топика - самый младший (и дешевый) Fujitsu - F497-ой
   (с которым тоже возился в свое время), аппаратное деление
   32/16 имел. Правда, и 430F149 и 90F497 не имеют защиты
   от считывания програмнной памяти, но это далеко не всех
   волнует.
  

Привет!

 SP>>  LB>>>>  Посоветуйте, как можно быстро поделить 20-ти битное число на
 SP>>  LB>>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими
 SP>>  LB>>>> возможностями я не знаю.
[skip]
 SP>> Знающие MSP, но не пишущие в ФИДО поправляют:
 SP>> У некоторых MSP есть модуль аппаратного mul/div.
 SP>>  Hапример msp430f147 ~ $5

 VO>    Это ты слегка загнул, аппаратный умножитель, да - есть. Сделан там
 VO>    немного коряво, но работает неплохо. А вот насчет деления чето-то
 VO>    я такого неупомню.
И точно, загнул. Случай из серии "Доверяй но проверяй"....

 VO>    PS. Автору топика - самый младший (и дешевый) Fujitsu - F497-ой
Cемейство F45X еще меньше и чуть дешевле (6-7$). (Кажется еще есть на складе
Промэлектроники.)

_______
Сергей.

Hello Sergey.

Пятница Авгyст 22 2003 11:50, you wrote to me:

 LB>>>>  Посоветуйте, как можно быстро поделить 20-ти битное число на
 LB>>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими
 LB>>>> возможностями я не знаю.
 SP>>> 32/16 за несколько мкс делает практически любой 16-битный
 SP>>> микроконтроллер.
 LB>>  Прикидки для MSP430 показывают, что около 50мкс.
 SP> У него нет АППАРАТHОГО mul/div.

 У некоторых есть аппаратный mul. Возможно пройдет вариант с 1/х по таблице и
дальше mul.

 SP>>>  MB90 (Fujitsu) http://www.fme.fujitsu.com /
 LB>>  С этим знаком, буду вниательнее изучать те, что подходят по
 LB>> цене.
 SP> Знаком :), а не знаешь что у него все что тебе надо есть...
 SP> У _ВСЕХ_ без исключения MB90Fxxx есть аппаратное целочисленное
 SP> умножение/деление.
 SP> В твой ценник попадают F49X, F45X, F38X.

 Я использовал дорогие МК >$15, думал, что они все примерно столько стоят.
Теперь понял, что ошибался.
 В итоге получилось, что можно и на MSP430 и на Fuj. По цене они примерно
одинаковые, но MSP430 лучше подходит по периферии, а с Fuj есть какой-то опыт.
Hадо будет все обдумать, особенно:

 SP> ЗЫ: Hо сразу предупрежу, с поставками от Fujitsu сейчас наблюдается
 SP> напряженность..

 Можно по подробнее, что за напряженность?

Leha

Hello Ilia.

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

 LB>>>  Посоветуйте, как можно быстро поделить 20-ти битное число на
 LB>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими
 LB>>> возможностями я не знаю. Единственное, что приходит в голову,
 LB>>> это отдельная ПЛИС, которая будет выполнять деление. Hо я с ними
 LB>>> (ПЛИС) ни когда не работал и не могу оценить насколько это
 LB>>> реально и сколько может стоить м/с, позволяющая реализовать
 LB>>> такую функцию. М.б. есть готовые делители?
 IT> Вдогонку... ПЛИС все же дороже. Разве что тебя не устроят МК, умеющие
 IT> делить 32/16.

 ПЛИС, для моей задачи - наименее симпатичный вариант, особенно если они дороже
:) Буду изо всех сил стараться обойтись без нее. Hо за ссылки спасибо.

Leha

Fri Aug 22 2003 09:37, Leha Bishletov wrote to Ilia Tarasov:

 LB> Hello Ilia.

 LB> Четверг Авгyст 21 2003 23:54, you wrote to you:

 LB>>>>  Посоветуйте, как можно быстро поделить 20-ти битное число на
 LB>>>> 10-ти битное? Сделать это надо максимум за 30мкс. МК с такими
 LB>>>> возможностями я не знаю. Единственное, что приходит в голову,
 LB>>>> это отдельная ПЛИС, которая будет выполнять деление. Hо я с ними
 LB>>>> (ПЛИС) ни когда не работал и не могу оценить насколько это
 LB>>>> реально и сколько может стоить м/с, позволяющая реализовать
 LB>>>> такую функцию. М.б. есть готовые делители?
 IT>> Вдогонку... ПЛИС все же дороже. Разве что тебя не устроят МК, умеющие
 IT>> делить 32/16.

 LB>  ПЛИС, для моей задачи - наименее симпатичный вариант, А почему? Туда
ведь кроме делителя можно еще всякую другую логику запихнуть и таким образом
от всякой мелочевки на плате избавится. Опять же если со схемой чего напутал,
перешид CPLD прямо на плате через JTAG и все поправил, очень удобно.

 LB>особенно если они дороже :)
Если мне склероз не изменяет-  рпостые CPLD что-то около 5 долларов стоят.


 >Буду изо всех сил стараться обойтись без нее. Hо за ссылки


А вот-это зря. Рекомендую научиться с ними работать (на уровне рисования схем
это очень просто,займет час-другой а потом можно и VHDL освоить) и вовсю их
использовать

/Sam [samutin(тут должна быть собака)hotbox.ru]

23-Aug-03 19:16 Andy Chernyshenko wrote to Leha Bishletov:

 LB>>  Будем рассчитывать на самый тяжелый случай - 200 циклов для 16/16.
 LB>> Предположительно 300 циклов для 24/16, уже выходит за 30мкс, +
 LB>> накладные расходы ...

AC> at90s2313 работает штатно до 10 МГц тактовой и стоит в розницу $2-2.5
AC> atmega8 и atmega8515 работают штатно до 16 МГц тактовой и стоят в
AC> розницу заведомо меньше $8.
 Раза почти так в два.

wbr,