[Неочевидные алгоритмы очевидных вещей] Алгоритм 1. Корень квадратный

[grich]

Лучше уж сразу назвать серию постов «Алгоритмы древнего Вавилона»

[Imp5]

Хорошо. Ничего критичного для жизни людей не программирует.

[WorksIsGone]

while(fabs(a-b)<EPS) тут наверное обратное условие,
преобразуем, пока разница между сторонами больше ε?

[skobeltsyn]

Точно! Очень извиняюсь! Спасибо! Исправил

[eyeless_watcher]

Ожидал увидеть очередную статью про 0x5f3759df.
Раз уж решили искать корень перебором, почему бы обычную дихотомию не использовать? Или бином Ньютона, на худой конец.

[Weageoo]

По-моему это называется итерационный аналитический алгоритм извлечения квадратного корня на основе формулы Герона.

[Weageoo]

И за реализацией я бы обратился например к этой замечательной статье.

[burdakovd]

А можете объяснить почему стандартный sqrt,

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. Как-то я больше доверял оптимизациям компилятора.

[datacompboy]

может из-за __declspec (naked)?

[burdakovd]

Ну по идее обе функции должны бы заинлайниться. Да и пролог/эпилог хороший компилятор должен сам суметь решить когда выкинуть.

[datacompboy]

анализировать __asm{} блок компилятору запрещено. именно поэтому 13й вариант имеет все необходимые стандартные заголовки и не имеет права инлайниться — мало ли что ты там в asm{} блоке хочешь делать.

кстати, 14й тоже НЕ инлайнится, несмотря на __inline. иначе функция работала бы СОВСЕМ неправильно из-за ret 8 унутре

[evocatus]

А я ожидал увидеть алгоритмы для компьютеров — быстрые, с маленькой погрешностью, эффективные.

[Imp5]

Да? codepad.org/m6myk89P
Автор, ты сам запускал этот код перед тем как постить?

[Lonsdaleite]

У автора после while фигурных скобок не хватает :)

[skobeltsyn]

Прошу прощения=) Исправил=)

[Imp5]

И ещё вдогонку, в приведённой функции после того как поставить скобки после условия в while, всё разно есть ещё одна ошибка,
Она связана с неучтённой погрешностью float.

Вход 1e18: codepad.org/qK4Bs558 — выполняется
Вход 1e20: codepad.org/7Rwyo0gh — бесконечный цикл
Вход 1e22: codepad.org/Ry9iRGbZ — выполняется

[skobeltsyn]

У меня при компиляции на gcc все представленные входы нормально считаются. Там float какого размера используется?

[Imp5]

4 байта.
Проявление этой ошибки зависит от инструкций и их порядка. И будет скорее всего разное при разных настройках компилятора.
Можешь попробовать повычислять с числами такого же порядка, в цикле.

[skobeltsyn]

Ок

[Forked]

Если вдруг интересно, то проект Эйлер еще жив.

Задача чуть повеселее: euler.jakumo.org/problems/view/80.html.

[Nexis]

Вот еще в копилку Формула Герона:
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);

[vvsh]

а почему не метод Ньютона? тем более есть обобщение на случай n > 2.

[vvsh]

вернее этот метод является его частным случаем.

[Pastafarianist]

en.wikipedia.org/wiki/Methods_of_computing_square_roots