[lamerok 0]

У меня такая проблема. Кварц 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 0]

Есть метод извлечения корня "в столбик". Если Вам нужно 16 бит результата, то будет 16 итераций с вычитаниями/сравнениями (почти как деление). Должно быть быстрее, по идее. Мы аппаратуру свою такую делали (а потом корки такие появились :) )

[lamerok 0]

Практически так и сделал... взял пример 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 0]

Врядли быстрее сделаешь математика вещь жесткая (хотя хрен знает)

[yornik 0]

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 0]

Интересная статья по вычислению корня квадратного с

ракурсом в историю аж до арифмометров.

 

Integer Square Roots by Jack W. Crenshaw

 

http://www.embedded.com/98/9802fe2.htm

[Joseph 0]

Господа, а не проще ли табличными методами? Память сейчас дешевая... :)