OberonCore

Библиотека  Wiki  Форум  BlackBox  Компоненты  Проекты
Текущее время: Пятница, 29 Март, 2024 00:06

Часовой пояс: UTC + 3 часа




Начать новую тему Ответить на тему  [ Сообщений: 9 ] 
Автор Сообщение
СообщениеДобавлено: Вторник, 16 Март, 2010 00:03 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Код:
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 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 18:55
Сообщения: 2272
Откуда: Россия, Нижний Новгород
В наборе команд 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 

Зарегистрирован: Пятница, 25 Сентябрь, 2009 13:10
Сообщения: 1177
Откуда: Мариуполь
Только вычисление не квадратного корня, а обратного квадратного корня.
Wikipedia: Fast inverse square root


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 16 Март, 2010 12:57 
Аватара пользователя

Зарегистрирован: Суббота, 15 Март, 2008 20:00
Сообщения: 297
Откуда: Київ, Україна
Валерий Лаптев писал(а):
Быстрое вычисление квадратного корня.

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 16 Март, 2010 14:51 
Аватара пользователя

Зарегистрирован: Пятница, 25 Ноябрь, 2005 12:02
Сообщения: 8500
Откуда: Троицк, Москва
bohdant писал(а):
Валерий Лаптев писал(а):
Быстрое вычисление квадратного корня.

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

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

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 16 Март, 2010 16:08 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Обязательно прочту. :) Попозжа.
По данной теме рекомендую книжку "Алгоритмические трюки для программистов".


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 16 Март, 2010 18:29 
Модератор
Аватара пользователя

Зарегистрирован: Среда, 16 Ноябрь, 2005 00:53
Сообщения: 4625
Откуда: Россия, Орёл
Валерий Лаптев писал(а):
По данной теме рекомендую книжку "Алгоритмические трюки для программистов".
и здесь трюки... это так численные методы называются?


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Вторник, 16 Март, 2010 18:41 

Зарегистрирован: Суббота, 07 Март, 2009 15:39
Сообщения: 3261
Откуда: Астрахань
Евгений Темиргалеев писал(а):
Валерий Лаптев писал(а):
По данной теме рекомендую книжку "Алгоритмические трюки для программистов".
и здесь трюки... это так численные методы называются?

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


Вернуться к началу
 Профиль  
 
СообщениеДобавлено: Четверг, 18 Март, 2010 10:33 
Аватара пользователя

Зарегистрирован: Суббота, 15 Март, 2008 20:00
Сообщения: 297
Откуда: Київ, Україна
А вот и корень на основе той же методики:
Код:
    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;
}


Вернуться к началу
 Профиль  
 
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 9 ] 

Часовой пояс: UTC + 3 часа


Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей и гости: 8


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

Найти:
cron
Вся информация, размещаемая участниками на конференции (тексты сообщений, вложения и пр.) © 2005-2024, участники конференции «OberonCore», если специально не оговорено иное.
Администрация не несет ответственности за мнения, стиль и достоверность высказываний участников, равно как и за безопасность материалов, предоставляемых участниками во вложениях.
Без разрешения участников и ссылки на конференцию «OberonCore» любое воспроизведение и/или копирование высказываний полностью и/или по частям запрещено.
Powered by phpBB® Forum Software © phpBB Group
Русская поддержка phpBB