16 bit fixed point SQRT for PIC16
Dmitry Orlov
А не завалялось ли у кого асмовской реализации (желательно или вообще без
использования стека или с минимальным) subj? Я пока что использую где-то
откопанный такой код:
word src;
word tmp_src;
word tmp_dst;
word mask;
byte count;
/* Square root calculation */
dst = 0;
tmp_src = 0;
tmp_dst = 0;
mask = 0xFFFF;
src = SVoutRMS;
for(count = 0; count < 8; count++)
{
src &= (mask >> count*2);
tmp_src <<= 2;
tmp_src |= src >> (7 - count)*2;
tmp_dst = dst;
dst <<= 1;
if((tmp_src != 0 )||(dst!=0))
{
tmp_dst <<= 2;
tmp_dst += 1;
if(tmp_dst <= tmp_src)
{
dst += 1;
tmp_src -= tmp_dst;
}
}
}
tmp_src <<= 2;
tmp_dst = dst;
tmp_dst <<= 2;
tmp_dst += 1;
if (tmp_dst <= tmp_src) dst += 1;
В принципе он меня устраивает, но может быть есть что-то существенно более
эффективное по скорости, или размеру?
С уважением, Дима Орлов.
Alexandr A. Redchuck
DO> А не завалялось ли у кого асмовской реализации (желательно или вообще
DO> без
DO> использования стека или с минимальным) subj? Я пока что использую
DO> где-то откопанный такой код:
[^Y]
DO> for(count = 0; count < 8; count++) {
DO> src &= (mask >> count*2);
DO> tmp_src <<= 2;
DO> tmp_src |= src >> (7 - count)*2;
DO> tmp_dst = dst;
DO> dst <<= 1;
DO> if((tmp_src != 0 )||(dst!=0)) {
DO> tmp_dst <<= 2;
DO> tmp_dst += 1;
DO> if(tmp_dst <= tmp_src) {
DO> dst += 1;
DO> tmp_src -= tmp_dst;
DO> }
DO> }
DO> }
DO> tmp_src <<= 2;
DO> tmp_dst = dst;
DO> tmp_dst <<= 2;
DO> tmp_dst += 1;
DO> if (tmp_dst <= tmp_src) dst += 1;
DO> В принципе он меня устраивает, но может быть есть что-то существенно
DO> более эффективное по скорости, или размеру?
Думаю, что и по скорости, и по размеру. Здесь совсем не оптимизированы
сдвиги, разве можно делать столько многобайтных сдвигов на переменную
величину. Мог бы хоть их почистить...
В ru.algorithms когда-то этот вопрос поднимался, Винокуров Андрей приводил
объяснение "школьного" метода "цифра за цифрой" ("корень в столбик") для
десятичной системы и его асм386 реализацию в двоичном виде.
Ниже выдержка из моего письма туда же с несколько другим методом (регистр
последовательных приближений).
В асмовой реализации для 386 он дал сравнимое быстродействие.
Тут я приведу только С-шный кусок письма.
From: "Alexandr A. Redchuck" <re...@real.kiev.ua>
Newsgroups: fido7.ru.algorithms
Subject: [NEWS] isqrt
Date: 12 Apr 1998 16:51:28 +0400
> РПП:
> поднимаем в регистре старший бит. Если функция содержимого регистра
> меньше цели, оставляем этот бит, если больше - сбрасываем.
> Повторяем вправо со всеми битами до младшего.
>
> В тупом варианте для корня:
>
> unsigned short sar_sqrt(unsigned long from) {
> unsigned short sqr,mask=0x8000;
> do {
> sqr |= mask;
> if( sqr*sqr > from ) 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 from) {
> unsigned long mask = 0x40000000, sqr = 0, temp;
> do {
> temp = sqr | mask;
> sqr >>= 1;
> if( temp <= from ) {
> sqr |= mask;
> from -= temp;
> }
> } while( mask >>= 2 );
> // можно дать еще округление if( sqr < from ) ++sqr;
> return (unsigned short)sqr;
> }
Тут для корня из длинного, для корня из 16-битного надо соответственно
уменьшить разрядность переменных и начать с маски 0x4000.
wbr,
--
/* Alexandr Redchuck, Kyiv, Ukraine */
/* real на real тчк kiev тчк ua */
Dmitry Orlov
> DO> В принципе он меня устраивает, но может быть есть что-то существенно
> DO> более эффективное по скорости, или размеру?
> Думаю, что и по скорости, и по размеру. Здесь совсем не оптимизированы
> сдвиги, разве можно делать столько многобайтных сдвигов на
> переменную величину. Мог бы хоть их почистить...
Я просто пробовал как есть. Скорость на самом деле мне не особо критична, за
20ms успевает, и ладно (реально тот кусок где-то 500us при моей тактовой
выполнялся)
> В ru.algorithms когда-то этот вопрос поднимался, Винокуров Андрей
> приводил объяснение "школьного" метода "цифра за цифрой" ("корень в
> столбик") для десятичной системы и его асм386 реализацию в двоичном виде.
> Hиже выдержка из моего письма туда же с несколько другим методом
> (регистр последовательных приближений).
> В асмовой реализации для 386 он дал сравнимое быстродействие.
> Тут я приведу только С-шный кусок письма.
>> unsigned short isqrt( unsigned long from) {
>> unsigned long mask = 0x40000000, sqr = 0, temp;
>> do {
>> temp = sqr | mask;
>> sqr >>= 1;
>> if( temp <= from ) {
>> sqr |= mask;
>> from -= temp;
>> }
>> } while( mask >>= 2 );
>> // можно дать еще округление if( sqr < from ) ++sqr;
>> return (unsigned short)sqr;
>> }
> Тут для корня из длинного, для корня из 16-битного надо соответственно
> уменьшить разрядность переменных и начать с маски 0x4000.
О, а вот это работает почти в 5 раз быстрей и занимает примерно на 100 слов
меньше места (всего 46 слов!). Большое спасибо, ты здорово помог.
С уважением, Дима Орлов.
Vladimir Poletaev
Dmitry Orlov wrote in a message to All:
DO> В принципе он меня устраивает, но может быть есть что-то
DO> существенно более эффективное по скорости, или размеру?
Если важен размер (но не скорость!), то можно суммировать нечетные числа:
1 = 1 = 1^2
1 + 3 = 4 = 2^2
1 + 3 + 5 = 9 = 3^2 и т.д.
Так что суммируем и сравниваем с исходным числом. Hомер итерации - искомый
корень. Для 16 бит - не более 256 итераций, так что счетчик может быть
байтовым.
With best regards...
Vladimir.