Комментарии 25
Лучше уж сразу назвать серию постов «Алгоритмы древнего Вавилона»
while(fabs(a-b)<EPS) тут наверное обратное условие,
преобразуем, пока разница между сторонами больше ε?
преобразуем, пока разница между сторонами больше ε?
Ожидал увидеть очередную статью про 0x5f3759df.
Раз уж решили искать корень перебором, почему бы обычную дихотомию не использовать? Или бином Ньютона, на худой конец.
Раз уж решили искать корень перебором, почему бы обычную дихотомию не использовать? Или бином Ньютона, на худой конец.
По-моему это называется итерационный аналитический алгоритм извлечения квадратного корня на основе формулы Герона.
И за реализацией я бы обратился например к этой замечательной статье.
А можете объяснить почему стандартный sqrt,
sqrt13:
и sqrt14
работают разное время? Каждый следующий раза в два быстрее предыдущего (при этом точность одинаковая).
Очень уж не хочется верить в то, что в наши дни нужно писать код как в примере 14, который судя по всему ещё не будет работать на x64. Как-то я больше доверял оптимизациям компилятора.
sqrt13:
double sqrt13(double n)
{
__asm {
fld n
fsqrt
}
}
и sqrt14
double inline __declspec (naked) __fastcall sqrt14(double n)
{
_asm fld qword ptr [esp+4]
_asm fsqrt
_asm ret 8
}
работают разное время? Каждый следующий раза в два быстрее предыдущего (при этом точность одинаковая).
Очень уж не хочется верить в то, что в наши дни нужно писать код как в примере 14, который судя по всему ещё не будет работать на x64. Как-то я больше доверял оптимизациям компилятора.
может из-за __declspec (naked)?
Ну по идее обе функции должны бы заинлайниться. Да и пролог/эпилог хороший компилятор должен сам суметь решить когда выкинуть.
анализировать __asm{} блок компилятору запрещено. именно поэтому 13й вариант имеет все необходимые стандартные заголовки и не имеет права инлайниться — мало ли что ты там в asm{} блоке хочешь делать.
кстати, 14й тоже НЕ инлайнится, несмотря на __inline. иначе функция работала бы СОВСЕМ неправильно из-за ret 8 унутре
кстати, 14й тоже НЕ инлайнится, несмотря на __inline. иначе функция работала бы СОВСЕМ неправильно из-за ret 8 унутре
А я ожидал увидеть алгоритмы для компьютеров — быстрые, с маленькой погрешностью, эффективные.
Да? codepad.org/m6myk89P
Автор, ты сам запускал этот код перед тем как постить?
Автор, ты сам запускал этот код перед тем как постить?
У автора после while фигурных скобок не хватает :)
И ещё вдогонку, в приведённой функции после того как поставить скобки после условия в while, всё разно есть ещё одна ошибка,
Она связана с неучтённой погрешностью float.
Вход 1e18: codepad.org/qK4Bs558 — выполняется
Вход 1e20: codepad.org/7Rwyo0gh — бесконечный цикл
Вход 1e22: codepad.org/Ry9iRGbZ — выполняется
Она связана с неучтённой погрешностью float.
Вход 1e18: codepad.org/qK4Bs558 — выполняется
Вход 1e20: codepad.org/7Rwyo0gh — бесконечный цикл
Вход 1e22: codepad.org/Ry9iRGbZ — выполняется
У меня при компиляции на gcc все представленные входы нормально считаются. Там float какого размера используется?
Если вдруг интересно, то проект Эйлер еще жив.
Задача чуть повеселее: euler.jakumo.org/problems/view/80.html.
Задача чуть повеселее: euler.jakumo.org/problems/view/80.html.
Вот еще в копилку Формула Герона:
chipenable.ru/index.php/programming-avr/item/144-sqrt-root.html
chipenable.ru/index.php/programming-avr/item/144-sqrt-root.html
unsigned int root(unsigned int a)
{
unsigned int x;
x = (a/0x3f + 0x3f)>>1;
x = (a/x + x)>>1;
x = (a/x + x)>>1;
return(x);
а почему не метод Ньютона? тем более есть обобщение на случай n > 2.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
[Неочевидные алгоритмы очевидных вещей] Алгоритм 1. Корень квадратный