Re: как корень квадратный написать?
хочу прикольнуться и чмы на 1С сдать
разложение в ряд тейлора в точке x=1
![[math] $\\ f(x)=\sqrt{x} \\ f(x) = 1 + 1/2*(x-1) + 1/2 * (1/2 - 1)* 1/2! * (x-1)^2 + 1/2*(1/2-1)*(1/2-1-1) * 1/3! * (x-1)^3 + ... + 1/2 * (1/2 - 11/2 - 1 - 1) * ... * (1/2-1-(n-1 * 1/n! *(x-1)^n + ...$ [/math]](mathimg.php?math=%0D%0A%24%5C%5C%0D%0Af%28x%29%3D%5Csqrt%7Bx%7D%20%5C%5C%0D%0Af%28x%29%20%3D%201%20%2B%201%2F2%2A%28x-1%29%20%2B%201%2F2%20%2A%20%281%2F2%20-%201%29%2A%201%2F2%21%20%2A%20%28x-1%29%5E2%20%2B%201%2F2%2A%281%2F2-1%29%2A%281%2F2-1-1%29%20%2A%201%2F3%21%20%2A%20%28x-1%29%5E3%20%2B%20...%20%2B%201%2F2%20%2A%20%281%2F2%20-%201%29%281%2F2%20-%201%20-%201%29%20%2A%20...%20%2A%20%281%2F2-1-%28n-1%29%29%20%2A%201%2Fn%21%20%2A%28x-1%29%5En%20%2B%20...%24%0D%0A)
это если я ничего не напутал
это если я ничего не напутал
У этого ряда радиус сходимости равен 1, так что никто не гарантирует, что
ряд сходится при x>=2. Хотя, может быть я что-то путаю.
ряд сходится при x>=2. Хотя, может быть я что-то путаю.
если есть цикл while попробуй методом Ньютона http://en.wikipedia.org/wiki/Newton's_method.
x_0 = 1
while True:
x_{n+1} = (x_n + a/x_n)/2
if (abs(x_{n+1} - x_{n} < epsilon return x_n;
У этого ряда радиус сходимости равен 1, так что никто не гарантирует, чтоОн расходится там, ряд-то степенной, но
ряд сходится при x>=2. Хотя, может быть я что-то путаю.
float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) &y; // evil floating point bit level hacking
i = 0x5f3759df - ( i >> 1 ); // what the fuck?
y = * ( float * ) &i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}
Magical Square Root Implementation In Quake III
блин, я опоздал 
Не всем настолько пофиг на точность рассчетов, как создателям Quake.
В этой формуле точность не больше 2 знаков после запятой.
В этой формуле точность не больше 2 знаков после запятой.
я в курсе, спасибо.
//******************************************************************
// КвaдpaтныйКopeнь(Apгумeнт)
//
// Пapaмeтpы:
// Apгумeнт - нeoтpицaтeльнoe чиcлo
//
// Boзвpaщaeмoe Значeниe:
// Квaдpaтный кopeнь Apгумeнтa
//
// Oпиcaниe
// ПpeднaЗначeнa для иcчиcлeния квaдpaтнoгo кopня чиcлa c
// пpимeнeниeм итepaциoннoгo мeтoдa Hьютoнa
// Итepaции выПолняютcя дo дocтижeния тoчнocти, зaдaннoй
// внeшнeй (публичнoй) Перемeннoй ДocтaтoчнaяToчнocть
//
Функция КвaдpaтныйКopeнь(Apгумeнт)
// Oгpaничимcя oблacтью oпpeдeлeния функции
Если Apгумeнт<0 Тогда
// cooбщeниe oб oшибкe
Сообщить("...","!");
Возврат ПолучитьПустоеЗначение;
// Oтceчeм нoль
ИначеЕсли Apгумeнт=0 Тогда
Возврат 0;
КонецЕсли;
// Bыбepeм пepвoe пpиближeниe
ПpeдыдущaяИтepaция = Apгумeнт/2;
Для Cч=1 По КoличecтвoИтepaций Цикл
Значeниe = 0.5*(ПpeдыдущaяИтepaция+
Apгумeнт/ПpeдыдущaяИтepaция);
Если Значeниe<ПpeдыдущaяИтepaция Тогда
Paзницa = ПpeдыдущaяИтepaция-Значeниe;
Иначе
Paзницa = Значeниe-ПpeдыдущaяИтepaция;
КонецЕсли;
Если Paзницa<ДocтaтoчнaяToчнocть Тогда
Прервать;
КонецЕсли;
ПpeдыдущaяИтepaция=Значeниe;
КонецЦикла;
Значeниe = Окр(Значeниe,Макс(КoличecтвoЗнaкoв-Лог10(Значeниe0;
Возврат Значeниe;
КонецФункции // кoнeц функции КвaдpaтныйКopeнь
http://www.kb.mista.ru/article.php?id=78
// КвaдpaтныйКopeнь(Apгумeнт)
//
// Пapaмeтpы:
// Apгумeнт - нeoтpицaтeльнoe чиcлo
//
// Boзвpaщaeмoe Значeниe:
// Квaдpaтный кopeнь Apгумeнтa
//
// Oпиcaниe
// ПpeднaЗначeнa для иcчиcлeния квaдpaтнoгo кopня чиcлa c
// пpимeнeниeм итepaциoннoгo мeтoдa Hьютoнa
// Итepaции выПолняютcя дo дocтижeния тoчнocти, зaдaннoй
// внeшнeй (публичнoй) Перемeннoй ДocтaтoчнaяToчнocть
//
Функция КвaдpaтныйКopeнь(Apгумeнт)
// Oгpaничимcя oблacтью oпpeдeлeния функции
Если Apгумeнт<0 Тогда
// cooбщeниe oб oшибкe
Сообщить("...","!");
Возврат ПолучитьПустоеЗначение;
// Oтceчeм нoль
ИначеЕсли Apгумeнт=0 Тогда
Возврат 0;
КонецЕсли;
// Bыбepeм пepвoe пpиближeниe
ПpeдыдущaяИтepaция = Apгумeнт/2;
Для Cч=1 По КoличecтвoИтepaций Цикл
Значeниe = 0.5*(ПpeдыдущaяИтepaция+
Apгумeнт/ПpeдыдущaяИтepaция);
Если Значeниe<ПpeдыдущaяИтepaция Тогда
Paзницa = ПpeдыдущaяИтepaция-Значeниe;
Иначе
Paзницa = Значeниe-ПpeдыдущaяИтepaция;
КонецЕсли;
Если Paзницa<ДocтaтoчнaяToчнocть Тогда
Прервать;
КонецЕсли;
ПpeдыдущaяИтepaция=Значeниe;
КонецЦикла;
Значeниe = Окр(Значeниe,Макс(КoличecтвoЗнaкoв-Лог10(Значeниe0;
Возврат Значeниe;
КонецФункции // кoнeц функции КвaдpaтныйКopeнь
http://www.kb.mista.ru/article.php?id=78
Если меня не глючит, приближать sqrt(a) видом 0.5 * (b + a/b) еще древние вавилоняне умели.
А тейлором не быстрее ли приблизится?
Для тейлора есть ограничение на x
откуда?
кстати, даже если и правда было бы ограничение на x, это ограничение было бы легко обходимо. Достаточно разделить его на большой квадрат любого заранее известного числа.
Тут уже сказали про это 
а, да. Но он вовсе не расходится, так как ряд не степенной, а имеет факториал в знаменателе.
А числитель?
ЗЫ: Над формулой не думал, хз, мб там что-то криво.
1/2 * (1/2 - 11/2 - 1 - 1) * ... * (1/2-1-(n-1 * 1/n!- это порядка О(1) получается.
ЗЫ: Над формулой не думал, хз, мб там что-то криво.
а вот насчет быстрей тут еще вопрос.. Нуна эксперимент ставить)
Не быстрей. Метод Ньютона асимптотически быстрей приближает.
А вот тут может быть не факт, ибо коэффициэнты в Тейлоре можно вручную просчитать, а с МН так не получится. К тому же деление все-таки тяжелее умножения.
Одно точно скажу, если считать ручками(на бумажке то так определённо быстрее, чем по тейлору. 
Коэффициенты — да, а вот степени ты не посчитаешь. На каждый член ряда Тейлора нужно по крайней мере одну дополнительную операцию. А зависимость между числом итераций и эквивалентным числом членов ряда — экспоненциальная.
Если нужно вычислить, скажем 500, верных знаков после запятой![[math]$\sqrt 2$[/math]](mathimg.php?math=%24%5Csqrt%202%24)
— то метод Ньютона рулит однозначно.
Если нужно вычислить, скажем 500, верных знаков после запятой
Каждый следущий член Тейлора - 2 умножения и сложение, каждый следущий член МН - умножение, сложение и деление. Или я не так понимаю?
PS Ну если надо много знаков то однозначно МН
PS Ну если надо много знаков то однозначно МН
Ну все правильно. Вот только для получения 500 верных знаков надо 9 итераций МН или 500 членов ряда Тейлора.
О, вспомнил - нам семинарист по матану как-то говорил на первом курсе, что надо знать и конкретные методы, а то пятикурсники ему все бяки считают в лоб через тейлора, тратят на это кучу времени, и нихрена не получают
Не всем настолько пофиг на точность рассчетов, как создателям Quake.Сказано же, что это - лучшее число для начального приближения.
быстрее всгео сходится в итоге алгоритм. это не значит что большей точносит достичь невозможно.
Сказано же, что это - лучшее число для начального приближения.Имхо, бред. Лучшее начальное приближение зависит от выбранного количества операций.
Лично мне не верится, что какой-то умный математик долго искал-искал, и нашёл что-то левое, не относящееся к делу.
а так.. проще проверить, по-моему, работу этого варианта
а так.. проще проверить, по-моему, работу этого варианта
Оставить комментарий
Byvaly
нужен алгоритм написания корня с помощью примитивных действий (+-*/)