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/ |