OberonCore
https://forum.oberoncore.ru/

Быстрое вычисление квадратного корня.
https://forum.oberoncore.ru/viewtopic.php?f=27&t=2440
Страница 1 из 1

Автор:  Валерий Лаптев [ Вторник, 16 Март, 2010 00:03 ]
Заголовок сообщения:  Быстрое вычисление квадратного корня.

Код:
float InvSqrt(float x){
   float xhalf = 0.5f * x;
   int i = *(int*)&x; // store floating-point bits in integer
   i = 0x5f3759d5 - (i >> 1); // initial guess for Newton's method
   x = *(float*)&i; // convert new bits into float
   x = x*(1.5f - xhalf*x*x); // One round of Newton's method
   return x;
}

Из Quake 2

Автор:  Сергей Губанов [ Вторник, 16 Март, 2010 11:21 ]
Заголовок сообщения:  Re: Быстрое вычисление квадратного корня.

В наборе команд SSE (начиная с то ли с Pentium-3 то ли с Pentium-4) есть инструкция которая вычисляет одновременно для четырёх SHORTREAL-чисел {x1, x2, x3, x4} четыре SHORTREAL-числа {1/sqrt(x1), 1/sqrt(x2), 1/sqrt(x3), 1/sqrt(x4)}.

Автор:  Роман М. [ Вторник, 16 Март, 2010 12:06 ]
Заголовок сообщения:  Re: Быстрое вычисление квадратного корня.

Только вычисление не квадратного корня, а обратного квадратного корня.
Wikipedia: Fast inverse square root

Автор:  bohdant [ Вторник, 16 Март, 2010 12:57 ]
Заголовок сообщения:  Re: Быстрое вычисление квадратного корня.

Валерий Лаптев писал(а):
Быстрое вычисление квадратного корня.

Спасибо за инфу! Люблю такие методы, иногда очень выручают

В применении к микроконтроллерам можно приблизительное значение квадратного кореня вычислить путем отнимания нечетных числел

Код:
1^2 =1      =-1
2^2 =4      =-1-3
3^2 =9      =-1-3-5
4^2=16     =-1-3-5-7
...

Автор:  Info21 [ Вторник, 16 Март, 2010 14:51 ]
Заголовок сообщения:  Re: Быстрое вычисление квадратного корня.

bohdant писал(а):
Валерий Лаптев писал(а):
Быстрое вычисление квадратного корня.

Спасибо за инфу! Люблю такие методы, иногда очень выручают

Ньютон вычислял вручную, ему все время себя надо было выручать.

Читайте Калиткина.

Автор:  Валерий Лаптев [ Вторник, 16 Март, 2010 16:08 ]
Заголовок сообщения:  Re: Быстрое вычисление квадратного корня.

Обязательно прочту. :) Попозжа.
По данной теме рекомендую книжку "Алгоритмические трюки для программистов".

Автор:  Евгений Темиргалеев [ Вторник, 16 Март, 2010 18:29 ]
Заголовок сообщения:  Re: Быстрое вычисление квадратного корня.

Валерий Лаптев писал(а):
По данной теме рекомендую книжку "Алгоритмические трюки для программистов".
и здесь трюки... это так численные методы называются?

Автор:  Валерий Лаптев [ Вторник, 16 Март, 2010 18:41 ]
Заголовок сообщения:  Re: Быстрое вычисление квадратного корня.

Евгений Темиргалеев писал(а):
Валерий Лаптев писал(а):
По данной теме рекомендую книжку "Алгоритмические трюки для программистов".
и здесь трюки... это так численные методы называются?

Нет. Там описываются серьезные вычисления, использующие на полную катушку особенности машинного представления чисел. Некоторые алгоритмы даже с доказательствами. Для встроенных микропроцессорных систем весьма может пригодиться.
Если подробнее - на РСДН есть моя рецензия на эту книгу. Там и оглавление приводится.

Автор:  bohdant [ Четверг, 18 Март, 2010 10:33 ]
Заголовок сообщения:  Re: Быстрое вычисление квадратного корня.

А вот и корень на основе той же методики:
Код:
    double fsqrt (double y) {
    double x, z, tempf;
    unsigned long *tfptr = ((unsigned long *)&tempf) + 1;

   tempf = y;
   *tfptr = (0xbfcdd90a - *tfptr)>>1; /* estimate of 1/sqrt(y) */
   x =  tempf;
   z =  y*0.5;                        /* hoist out the “/2”    */
   x = (1.5*x) - (x*x)*(x*z);         /* iteration formula     */
   x = (1.5*x) – (x*x)*(x*z);
   x = (1.5*x) – (x*x)*(x*z);
   x = (1.5*x) – (x*x)*(x*z);
   x = (1.5*x) – (x*x)*(x*z);
   return x*y;
    }


А вот кому нужно целочисленный:

Код:
 *      - SquareRoot(5) --> 2
 *      - SquareRoot(8) --> 2
 *      - SquareRoot(9) --> 3
 *
 * \param[in] a_nInput - unsigned integer for which to find the square root
 *
 * \return Integer square root of the input value.
 */
uint32_t SquareRoot(uint32_t a_nInput)
{
    uint32_t op  = a_nInput;
    uint32_t res = 0;
    uint32_t one = 1uL << 30; // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint32_t type


    // "one" starts at the highest power of four <= than the argument.
    while (one > op)
    {
        one >>= 2;
    }

    while (one != 0)
    {
        if (op >= res + one)
        {
            op = op - (res + one);
            res = res +  2 * one;
        }
        res >>= 1;
        one >>= 2;
    }
    return res;
}

Код:
/**
 * \brief    Fast Square root algorithm, with rounding
 *
 * This does arithmetic rounding of the result. That is, if the real answer
 * would have a fractional part of 0.5 or greater, the result is rounded up to
 * the next integer.
 *      - SquareRootRounded(2) --> 1
 *      - SquareRootRounded(3) --> 2
 *      - SquareRootRounded(4) --> 2
 *      - SquareRootRounded(6) --> 2
 *      - SquareRootRounded(7) --> 3
 *      - SquareRootRounded(8) --> 3
 *      - SquareRootRounded(9) --> 3
 *
 * \param[in] a_nInput - unsigned integer for which to find the square root
 *
 * \return Integer square root of the input value.
 */
uint32_t SquareRootRounded(uint32_t a_nInput)
{
    uint32_t op  = a_nInput;
    uint32_t res = 0;
    uint32_t one = 1uL << 30; // The second-to-top bit is set: use 1u << 14 for uint16_t type; use 1uL<<30 for uint32_t type


    // "one" starts at the highest power of four <= than the argument.
    while (one > op)
    {
        one >>= 2;
    }

    while (one != 0)
    {
        if (op >= res + one)
        {
            op = op - (res + one);
            res = res +  2 * one;
        }
        res >>= 1;
        one >>= 2;
    }

    /* Do arithmetic rounding to nearest integer */
    if (op > res)
    {
        res++;
    }

    return res;
}

Страница 1 из 1 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/