Помощь - Поиск - Пользователи - Календарь
Полная версия этой страницы: Корень квадратный
Форум разработчиков электроники ELECTRONIX.ru > Цифровая обработка сигналов - ЦОС (DSP) > Алгоритмы ЦОС (DSP)
lamerok
У меня такая проблема. Кварц 32768. Проц должен за 300 мс найти корень из целого числа (X) в диапазоне от 625 до 10000. Нужно получить корень но с точностью два занака, т.е например, корень(1000)= 31.62 = (3162)
Беру следующим образом (итеррациями):
Если (X<=2500) то итерации такие (y1 =) y + (X - y^2)
Если (X>2500), то такие (y1 =) y + (X - y^2)/2.
Вроде считает правильно, но самое максимальное получается 13 итераций. в итоге занимает примерно 850 мс. Очень долго.
Посмотрел, оказалось, что больше всего занимает место перемножение двух 16 рарядных целых чисел(квадрат y^2). примерно 450 циклов в каждой итеррации.
Не подскажите как можно квадрат сделать в циклов 100. или как корень побыстрее сделать.
Использую PIC16.
Пробывал по другому
Код
do
//  {
//      a = b;    
//      b = (a + c/a)/2;
//  } while (a > b);

Получается секунды 2. Из-за того, что все числа long int;

Заранее спасибо
Код
               typedef unsigned char  tU8;  /* 8 bits, unsigned */
    typedef signed char  tS8;  /* 8 bits, unsigned */
    typedef unsigned int  tU16;    /* Two-byte unsigned int */
    typedef long int  tS32;
    typedef signed int  tS16;    /* Two-byte signed int */
    typedef unsigned long  tU32;    /* Four-byte unsigned */
    typedef union {tU8 Byte[4]; tS16 I[2]; tU32 L;} tAll;

tS16 Sqrt(tS16 value)
{
    
    tAll  a;
    tS16 b;    
    tU8  c;
    tAll temp;

    {
//  c = 10000;
//  c = c*Result;
//  b = c;
//  do
//  {
//      a = b;    
//      b = (a + c/a)/2;
//  } while (a > B);
//    }
//    Result = a;
//    return  Result;

 c = value>>8;                   /*Выделяем старший байт*/
 a.L = value * 429496;        /* домнажаем на 65556*6.5536 для точности */
 b = 1;
 temp.I[0] = a.I[1];
 temp.I[1] = a.I[1];
 while(b>0)
 {
     a.L = (tU32)temp.I[0]*(tU16)temp.I[0];   /*  y^2 */
     b = (temp.I[1] - a.I[1]);                         /* X - y^2 */
     if (c > 9)                                              /* Если больше чем 0x900 */
     {
                    b =b>>2;                                       /* (X - y^2)/2 */
     }      
     temp.I[0]+=b;                                    /* y = y+(X-y^2) или y = y+(X-y^2)/2*/
 };
    }
    a.L = (tU32)temp.I[0] * 10000;           /* Множим на 65536/6.5536 = 10000*/
    return a.I[1]; /* В старшем байте искомый результат */
    
}
yornik
Есть метод извлечения корня "в столбик". Если Вам нужно 16 бит результата, то будет 16 итераций с вычитаниями/сравнениями (почти как деление). Должно быть быстрее, по идее. Мы аппаратуру свою такую делали (а потом корки такие появились smile.gif )
lamerok
Практически так и сделал... взял пример c форума микрочипа...
Получилось быстрее почти в 8 раз, теперь занимает всего 900 циклов
корень от значения в диапазоне от 0 до 10000.
Вот чего получилось...
Код
tS16 Sqrt(tS16 value)          
{
       tS16 Result;
       tU32 ulinput;       // вход 27 бит
       tU16 uitemp;    // результат, и врем.
       tU8  ucc;        // счетчики

    
/* uniput = (value*10000) Для точности 2 знака */
       ulinput =  value<<1;                    
       ulinput += (tU32)value<<3;

       ulinput =  ulinput<<1;
       ulinput += ulinput<<2;
    
       ulinput  = ulinput<<1;
       ulinput += ulinput<<2;

       ulinput = ulinput<<1;
       ulinput +=ulinput<<2;
/*********************Конец умножения на 10000 *********************/
    
        Result  = 0;
        uitemp = 0;

        ucc = 14;

        do
       {
               uitemp <<= 1;
               if (ulinput & 0x08000000)
                     uitemp |= 1;
             
               ulinput <<= 1;    
               Result <<= 1;
   
              uitemp <<= 1;
              if (ulinput & 0x08000000)
                     uitemp |= 1;
                 
              ulinput <<= 1;    
              Result <<= 1;
   

              Result &= ~2;   // set '01' at the end
              Result |= 1;

              if (uitemp >= Result)
              {
                      uitemp -= Result;    
                      Result |= 2;
               }
               Result >>= 1;
       } while (--ucc != 0);    // конец циклов

        return Result;
}
olefil
Врядли быстрее сделаешь математика вещь жесткая (хотя хрен знает)
yornik
2 lamerok: а почему именно на 10000 умножаете? Не проще ли просто сразу входное число дополнять шестнадцатью бинарными нулями (т.е. умножать на 65536) ? Масштабирование результата в 256 раз учесть, имхо, не сложнее, чем в варианте с масштабированием в 100 раз.

Кусок из "Алгоритмические трюки для программистов" (!не пробовал сам!), для 32-битного исходного числа, "в среднем ему требуется 149 базовых RISC-команд":

int isqrt (unsigned x)
{
unsigned m, y, b;
m = 0x40000000;
y = 0;
while (m != 0) { //16 раз
b = y | m;
y = y >> 1;
if (x >= b) {
x = x - b;
y = y | m;
}
m = m >> 2;
}
return y;
}
YuryL
Интересная статья по вычислению корня квадратного с
ракурсом в историю аж до арифмометров.

Integer Square Roots by Jack W. Crenshaw

http://www.embedded.com/98/9802fe2.htm
Joseph
Господа, а не проще ли табличными методами? Память сейчас дешевая... smile.gif
Для просмотра полной версии этой страницы, пожалуйста, пройдите по ссылке.
Invision Power Board © 2001-2025 Invision Power Services, Inc.