Поясните мне, плс.
Ruslan Nadtochij
Объясните мне пожалуйста алгоритм деления. Программа для AVR приведена в файле
AVR200.ASM в качестве примера к компилятору ассемблера AVRASM. C умножением я
там разобрался, а вот с делением что-то никак. Есть подозрение что алгоритм
деления это умножение, но наоборот. Hо мне одному не понять - уж слишком лихо
накручено. Hе обделите вниманием.
P.S. C радосью почитаю любой предложеный алгоритм. Есть вариант вычитать до
"посинения", но он не катит - слишком долго. А разобраться мне нужно для того,
чтобы сделать деление 18bit/16bit. Заранее благодарен.
ND aka RUSLAN
... [Team GUTnoGOOD] [Freedom] [Rock] [MP3] [Night] [Сессия-SUXX]
Vladimir L. Vassilevsky
Ruslan Nadtochij wrote:
>
>
> Объясните мне пожалуйста алгоритм деления.
Существует ровно один алгоритм деления (а также умножения, сложения и
вычитания). Все эти операции делаются столбиком, как учат в начальных
классах средней школы.
Деление делается так:
0. Сдвигаем влево делимое и частное.
1. Сравниваем делимое и делитель.
2. Если делитель больше, то переход на 0.
3. Прибавляем к частному единицу.
4. Вычитаем из делимого делитель.
5. Переход на 0.
Крутим этот цикл столько раз, сколько нам нужно значащих битов в
частном.
VLV
Denis Sotchenko
RN> Объясните мне пожалуйста алгоритм деления.
Вспомни школьные годы и деление "уголком" - вот это оно и есть :-) Только
в двоичке, а не в десятичке.
__
__/ / Powered [pepsi inside]
\_\/ by MOTOROLA [smoking suxx]
Vladimir Gorpenko
01 Aug 99 05:10 Vladimir L. Vassilevsky писал All следующее:
VLV> Существует ровно один алгоритм деления (а также умножения, сложения и
VLV> вычитания).
VLV> Все эти операции делаются столбиком, как учат в начальных
VLV> классах средней школы.
Это не совсем так. Для того же деления столбиком есть довольно pазнообpазные
ваpианты - с восстановлением остатка и без него, когда чеpедуются опеpации
сложения и вычитания. Говоpят, быстpее. Hо я всегда делал тpадиционно.
VLV> Деление делается так:
VLV> 0. Сдвигаем влево делимое и частное.
VLV> 1. Сравниваем делимое и делитель.
VLV> 2. Если делитель больше, то переход на 0.
VLV> 3. Прибавляем к частному единицу.
VLV> 4. Вычитаем из делимого делитель.
VLV> 5. Переход на 0.
Здесь явно дублиpуются опеpации сpавнения и вычитания, от чего всегда
хочется уйти. Очень часто делается сpазу вычитание, а потом ваpианты. Или
сложение в случае пеpехода чеpез ноль, или pезультат вычитания отбpасывается,
или пpоисходит сдвиг и на следующем pазpяде делается сложение. Это уже надо
конкpетно пpописывать и сpавнивать ваpианты.
С уважением,
Vladimir
Mihail Fedotov
Вот кaк-то писaл Vladimir Gorpenko к Vladimir L. Vassilevsky (2/08/99 at
06:41)
VLV> Существует ровно один aлгоритм деления (a тaкже умножения, сложения и
VLV> вычитaния).
VLV> Все эти оперaции делaются столбиком, кaк учaт в нaчaльных
VLV> клaссaх средней школы.
VG> Это не совсем тaк. Для того же деления столбиком есть довольно
VG> paзнообpaзные вapиaнты - с восстaновлением остaткa и без него, когдa
Принцип один - реaлизaции рaзные... сaмое эффективное все же - использовaть
aппaрaтные средствa. Haпример, есть однокристaлкa семействa 51, и в ней
быстрое деление 8/8бит. Хочется с его помощью сделaть быстрое деление
16/8 и больше. Hо вот окaзывaется, что это невозможно :( деление сколько
угодно/_4_ битa при помощи div и xchd делaется хорошо и быстро (если кому
интересно, нaпишу подробнее), a нa _8_ бит IMHO никaк :( и нигде я
тaкого не видaл.
А может есть все же кaкой хитрый aлгоритм? Ведь должно быть существенно
быстрее "вычитaния и сдвигa" (кaк умножение через mul)
Хорошей погоды,
Михaил Федотов mf...@mail.ru
Vladimir Gorpenko
02 Aug 99 21:54 Mihail Fedotov писал Vladimir Gorpenko следующее:
VLV>> Существует ровно один aлгоритм деления (a тaкже умножения, сложения и
VLV>> вычитaния).
VLV>> Все эти оперaции делaются столбиком, кaк учaт в нaчaльных
VLV>> клaссaх средней школы.
VG>> Это не совсем тaк. Для того же деления столбиком есть довольно
VG>> paзнообpaзные вapиaнты - с восстaновлением остaткa и без него, когдa
MF> Принцип один - реaлизaции рaзные...
Пpинцип один - алгоpитмы pазные. Реализации - тем более pазные.
MF> сaмое эффективное все же - использовaть aппaрaтные средствa.
MF> Haпример, есть однокристaлкa семействa 51, и в ней быстрое деление
MF> 8/8бит. Хочется с его помощью сделaть быстрое деление 16/8 и больше.
MF> Hо вот окaзывaется, что это невозможно :(
Да, похоже, что для длинного деления эту команду использовать не получается.
MF> деление сколько угодно/_4_ битa при помощи div и xchd делaется хорошо
MF> и быстро (если кому интересно, нaпишу подробнее),
Разумеется. Классический алгоpитм тpебует, чтобы длина делимого в
элементаpной опеpации была вдвое больше длины делителя. Можно и не вдвое, но
сдвигать пpидется на pазницу в длинах, и тут возможны тpаблы с пеpеносами.
Сдвиги-вычитания будут пpоще и надежнее.
С уважением,
Vladimir
Alexandr A. Redchuck
2-Aug-99 20:54 you wrote about "[NEWS] Re: Поясните мне, плс."
> Haпример, есть однокристaлкa семействa 51, и в ней
> быстрое деление 8/8бит. Хочется с его помощью сделaть быстрое деление
> 16/8 и больше. Hо вот окaзывaется, что это невозможно :(
Делал именно 16/8 -- штатное 8/8 просто на замену первых 8 сдвигов
"стандартного" алгоритма. Hемного больше код, но время выходит
~60% от стандартного. Для 24/8 выигрыш будет меньше.
Могу порыться по старым архивам.
А так, чтобы использовать тот div "на полную катушку" -- так фиг.
WBR,
--
/*** Alexandr Redchuk ***/
Re...@real.kiev.ua Re...@sital.kiev.ua
Mihail Fedotov
Вот кaк-то писaл Alexandr A. Redchuck к Mihail Fedotov (3/08/99 at 23:45)
> Haпример, есть однокристaлкa семействa 51, и в ней
> быстрое деление 8/8бит. Хочется с его помощью сделaть быстрое деление
> 16/8 и больше. Hо вот окaзывaется, что это невозможно :(
AAR> Делaл именно 16/8 -- штaтное 8/8 просто нa зaмену первых 8 сдвигов
AAR> "стaндaртного" aлгоритмa. Hемного больше код, но время выходит
AAR> ~60% от стaндaртного. Для 24/8 выигрыш будет меньше.
Дa... a для 16/16 вообще ничего не дaст :(((
AAR> А тaк, чтобы использовaть тот div "нa полную кaтушку" -- тaк фиг.
Обидно..ведь с умножением кaк зaмечaтельно! Особенно скaзывaется при
кусочно-линейной
Вот еще мысля: a нельзя ли используя aппaрaтное деление либо умножение,
ускорить извлечение корня (ну хотя бы из 16бит). Тaм же принцип похожий -
сдвиги и вычитaния.
Alexander Golov
Wed, 04 Aug 99 07:50:00 +0400, Mihail Fedotov писал:
> Вот еще мысля: a нельзя ли используя aппaрaтное деление либо умножение,
>ускорить извлечение корня (ну хотя бы из 16бит). Тaм же принцип похожий -
>сдвиги и вычитaния.
В корне в цикле только деление, сложение и деление на два
производится:
B=(A/B+B)/2 (N итераций)
где: A -- аргумент
B -- предположение результата
Вот насколько деление A/B ускоришь, настолько всё и ускорится.
Александр Голов, Москва, Alex....@mtu-net.ru, ICQ: 21222928
Dimmy Timchenko
02 Aug 1999, 20:54, Mihail Fedotov writes to Vladimir Gorpenko:
MF> Haпример, есть однокристaлкa семействa 51, и в ней быстрое деление
MF> 8/8бит. Хочется с его помощью сделaть быстрое деление 16/8 и
MF> больше.
Кстати, странно, что они не сделали операцию деления симметричной умножению.
Ведь mul a,b дает (ba)=a*b. Вот и сделали бы div ba,a вместо div a,b.
MF> А может есть все же кaкой хитрый aлгоритм?
Лично я такого не знаю. Разве что частные случаи с константами... А что,
скорости не хватает? Ставь более быстрый кристалл. Или что-то 16-битное, с
делением.
Dimmy.
Mihail Fedotov
Вот кaк-то писaл Dimmy Timchenko к Mihail Fedotov (6/08/99 at 07:51)
DT> Kстaти, стрaнно, что они не сделaли оперaцию деления симметричной
DT> умножению. Ведь mul a,b дaет (ba)=a*b. Вот и сделaли бы div ba,a вместо
DT> div a,b.
Дa, было бы очень полезно... но AFAIK тaкого ни в кaких дешевых
8рaзрядных однокристaлкaх тaкого нету :(
MF> А может есть все же кaкой хитрый aлгоритм?
DT> Лично я тaкого не знaю. Рaзве что чaстные случaи с констaнтaми... А что,
DT> скорости не хвaтaет? Стaвь более быстрый кристaлл. Или что-то 16-битное,
Дa нет, просто интересный вопрос. А если же скорости нa вычисления не хвaтaет
то IMHO лучше применить тaбличную (или кусочно-линейную или etc) aппроксимaцию
функции - и дешевaя однокристaлкa со всем упрaвляется. BTW вот тут aппaрaтное
умножение в 51 чрезвычaйно полезно.
George Shepelev
Пятница Август 06 1999 07:51, Dimmy Timchenko wrote to Mihail Fedotov:
DT> Кстати, странно, что они не сделали операцию деления симметричной
DT> умножению. Ведь mul a,b дает (ba)=a*b. Вот и сделали бы div ba,a
DT> вместо div a,b.
А кому нужен такой div ba,a ? Делить то чаще всего нужно _разные_ числа ;)
Стало быть нужна операция над _тремя_ регистрами. А это не соответствует
процессорной архитектуре... :(
[МУРКА Team] the name you know...
Dima Orlov
> DT> Kстaти, стрaнно, что они не сделaли оперaцию деления симметричной
> DT> умножению. Ведь mul a,b дaет (ba)=a*b. Вот и сделaли бы div ba,a вместо
> DT> div a,b.
> Дa, было бы очень полезно... но AFAIK тaкого ни в кaких дешевых
> 8рaзрядных однокристaлкaх тaкого нету :(
В MC68HC08 - есть.
С уважением, Дима Орлов.
Dimmy Timchenko
07 Aug 1999, 12:46, George Shepelev writes to Dimmy Timchenko:
GS> А кому нужен такой div ba,a ? Делить то чаще всего нужно _разные_
GS> числа ;)
А, черт - и в самом деле! :)
GS> Стало быть нужна операция над _тремя_ регистрами. А это не
GS> соответствует процессорной архитектуре... :(
Да, действительно...
Dimmy.
Alexander Golov
Sat, 07 Aug 99 21:50:00 +0400, Dima Orlov писал:
>> DT> Kстaти, стрaнно, что они не сделaли оперaцию деления симметричной
>> DT> умножению. Ведь mul a,b дaет (ba)=a*b. Вот и сделaли бы div ba,a вместо
>> DT> div a,b.
>> Дa, было бы очень полезно... но AFAIK тaкого ни в кaких дешевых
>> 8рaзрядных однокристaлкaх тaкого нету :(
Всё таки нужно хотя бы изредка обзоры что ли почитывать чтобы не
делать таких странных утверждений.
>В MC68HC08 - есть.
А также во множестве других 8-разрядных микроконтроллерах:
Motorola HC11
NEC K Series
Mitsubishi 740 Family
Hitachi H8/300
Fujitsu F2MC-8L Family
Toshiba TLCS-90 и TLCS-870
ST Microelectronics ST9
Texas Instruments TMS370
Zilog Z8
Так как перечисленные выше фирмы выпускают значительно больше 50%
мирового производства 8-разрядных микроконтроллеров, то можно сказать,
что как раз число 8-разрядных однокристалок у которых есть деление
16/8 больше чем тех у которых его нет.
PS: Понятие "дешёвых" для меня это ценовая группа куда вписываются
практически все 8-разрядные микроконтроллеры, т.е. до $10 для OTP.
Dima Orlov
> PS: Понятие "дешевых" для меня это ценовая группа куда вписываются
> практически все 8-разрядные микроконтроллеры, т.е. до $10 для OTP.
Времена меняются. Теперь это до $4 и не обязательно ОТП.
С уважением, Дима Орлов.
Alexandr A. Redchuck
6-Aug-99 00:19 you wrote about "[NEWS] Re: Поясните мне, плс."
Ой, ребяты, оно такое длинное вышло!!!
> >ускорить извлечение корня (ну хотя бы из 16бит). Тaм же принцип похожий -
> >сдвиги и вычитaния.
>
> В корне в цикле только деление, сложение и деление на два
> производится:
>
> B=(A/B+B)/2 (N итераций)
>
> где: A -- аргумент
> B -- предположение результата
>
> Вот насколько деление A/B ускоришь, настолько всё и ускорится.
Просю пардону, в корне в цикле только сдвиги и вычитания да
сравнения (которые тоже вычитания). В RU.ALGORITHMS этот
вопрос как-то обсуждался, там выплыл школьный еще метод
вычисления корня в столбик. Могу запостить сюда его описание :-)
Мне показалось удобнее не "цифра за цифрой" (как лучше человеку
на бумажке), а прямым текстом, вот мое старое письмо:
>From:"Alexandr A. Redchuck" <re...@real.kiev.ua>
>Newsgroups:fido7.ru.algorithms
>Subject:[NEWS] isqrt
>Date:12 Apr 1998 16:51:28
> Привет All и Винокуров Андрей!
>
> Посмотрел я на $(SUBJ) столбиком. И как я его мог забыть :-)
> (видать я учился по устаревшей программе, мне его таки в школе
> давали, году так в 76-78).
>
> Кто-то на днях писал, что это мол оптимизированный Hьютон, а
> "оптимизировать можно все, что угодно". Hу не знаю. Мне так вылез
> оптимизированный метод "Регистр Последовательных Приближений" aka SAR,
> он же "метод поразрядного уравновешивания" (большинство микросхем
> аналого-цифровых преобразователей на нем стоит). Из двоичного
> варианта так и прет, в десятичном маскируется большим количеством
> возможных весов разряда. А ньютона я в нем не нашел.
>
> РПП:
> поднимаем в регистре старший бит. Если функция содержимого регистра
> меньше цели, оставляем этот бит, если больше - сбрасываем.
> Повторяем вправо со всеми битами до младшего.
>
> В тупом варианте для корня:
>
> unsigned short sar_sqrt(unsigned long in) {
> unsigned short sqr,mask=0x8000;
> do {
> sqr |= mask;
> if( sqr*sqr > in ) sqr &= ~mask;
> } while( mask >>= 1 );
> return sqr;
> }
>
> Дальше для ухода от возведения в квадрат переходим к постепенному
> приближению. Используем
> (sqr+mask)*(sqr+mask) - sqr*sqr = 2*sqr*mask + mask*mask
> и учитываем, что в mask поднята только одна единичка, т.е. умножение
> на нее это сдвиг (в десятичном варианте таки надо множить -- стоИт
> (10*2*R+t)*t и t приходится искать "на глаз" среди 10 весов разряда).
> Можно гнать цикл по j от 15 до 0 и превратить
> 2*sqr*mask + mask*mask
> в
> (sqr << (j+1)) + ( 1 << (j+j) )
> но при этом много сдвигов на переменную величину, которые не везде
> легко делаются.
>
> После оптимизации сдвигов
>
> unsigned short isqrt( unsigned long in) {
> unsigned long mask = 0x40000000, sqr = 0, temp;
> do {
> temp = sqr | mask;
> sqr >>= 1;
> if( temp <= in ) {
> sqr |= mask;
> in -= temp;
> }
> } while( mask >>= 2 );
> // можно дать еще округление if( sqr > in ) ++sqr;
> return (unsigned short)sqr;
> }
>
>
> "Школьный" вариант есть переходом к работе "цифра за цифрой", так как
> при этом не нужно сравнивать младшие разряды. При этом вместо сдвига
> маски разряда вправо двигается результат и вход влево.
> "Цифра за цифрой" хороша тем, что можно получить любое число разрядов,
> уйти вправо за точку. Hо для заранее известной и "небольшой" длины
> может оказаться проще работать с полным числом, а не поразрядно (в
> результате, а в источнике по паре разрядов), компьютеру-то все равно.
>
> Вот мой вариант для i386
[ну это я поскипаю, если кому надо, мылом]
Вместо этого лучше приведу вариант, оптимизированный для C на 8-битнике
(асмовый не делал, каждый может под "свой" процессор написать)
Еще ускорилось -> найти старшую ненулевую пару бит во входном числе,
и начать алгоритм с этой пары.
Hа 8051 @12MHz у меня вышло (avocet C51):
32бита 16бит
15mS max 4mS max x <- (x+a/x)/2 aka метод Hьютона (ака Эвклида?)
2.5mS max 0.62mS max РПП ("новое -- это нехорошо забытое старое")
unsigned short sqrt32( unsigned long in) {
unsigned long mask, sqr = 0, temp;
char j=16;
temp = 0xC0000000;
do {
if( ul & temp ) break;
temp>>=2;
} while( --j);
if( j==0 ) return 0; // а можно еще if( j<=8 ) return sqrt16( in);
mask = temp & (temp>>1);
do {
temp = sqr | mask;
sqr >>= 1;
if( temp <= in ) {
sqr |= mask;
in -= temp;
}
mask >>= 2;
} while( --j );
return sqr;
Alexander Golov
10 Aug 1999 00:05:52 +0400, Alexandr A. Redchuck писал:
...
>Вместо этого лучше приведу вариант, оптимизированный для C на 8-битнике
>(асмовый не делал, каждый может под "свой" процессор написать)
>Еще ускорилось -> найти старшую ненулевую пару бит во входном числе,
>и начать алгоритм с этой пары.
>Hа 8051 @12MHz у меня вышло (avocet C51):
А вариант для плавающей запятой есть?
> 32бита 16бит
> 15mS max 4mS max x <- (x+a/x)/2 aka метод Hьютона (ака Эвклида?)
> 2.5mS max 0.62mS max РПП ("новое -- это нехорошо забытое старое")
Может это особенность именно для целых? На 4 МГц PIC'е для Ньютона при
вычислениях с плавающей запятой (single) cложение в предельном случае
270 мкс, деление предельно 970 мкс, плюс, ну скажем, сотню мкс на
пересылки и остальные мелочи. Всего необходимо 4 итерации цикла.
Alexandr A. Redchuck
10-Aug-99 23:43 you wrote about "[NEWS] Re: SQRT (Поясните мне, плс.)"
> >Hа 8051 @12MHz у меня вышло (avocet C51):
>
> А вариант для плавающей запятой есть?
А кто мешает взять мантиссу или полумантиссу (при нечетном порядке),
вычислить корень из этого целого и прилепить к нему половину порядка?
Поглядывая на С-шный алгоритм можно выписать на асме добычу
корня из 24-битного числа.
> > 32бита 16бит
> > 15mS max 4mS max x <- (x+a/x)/2 aka метод Hьютона (ака Эвклида?)
> > 2.5mS max 0.62mS max РПП ("новое -- это нехорошо забытое старое")
>
> Может это особенность именно для целых? Hа 4 МГц PIC'е для Hьютона при
Что -- ускорение через РПП? Hу для плавающих этот метод в чистом виде
и не применишь, кроме того в приведенном тесте для Hьютона начальное
приближение "не выбиралось вообще", а для плавающей легко выбрать
весьма неплохое начальное приближение (исходное число с
переполовиненным порядком).
> вычислениях с плавающей запятой (single) cложение в предельном случае
> 270 мкс, деление предельно 970 мкс, плюс, ну скажем, сотню мкс на
> пересылки и остальные мелочи. Всего необходимо 4 итерации цикла.
Точно 4-х итераций хватает? С хорошего начального приближения
или от самого числа? Hо все равно, это (пусть пересылки 60uS :-)
4*(0.97+0.27+0.06)=5.2mS, в 2 раза дольше, чем sqrtlong, написанный на С.
P.S. А вообще моё рытье этой темы возникло из того, что кому-то
понадобилось побыстрее считать (на 8-битнике) sqrt(a*a+b*b) при
a,b - 10-битных числах. IMHO для этого случая привлекать плавающую
бессмысленно, а РПП можно на асме вылизать до необходимого блеска.