Comments 25
Мой опыт говорит, что любые хитропопые методы заходят куда лучше, после того, как сам решил задачу ужасающим методом. Вот тогда их хитропопость начинает выглядеть как cleverness. А если начинать с них, то (без понимания масштаба задачи), оно выглядит как "ЗАЧЕМ ЭТО ВСЁ КАКОЙ УЖАС".
любые хитропопые методы заходят куда лучше, после того, как сам решил задачу ужасающим методомЭто все абсолютно верно. Но после «сам решил» даже вы не подразумеваете, что на этом нужно останавливаться. А здесь то какой вообще был резон для написания статьи? Ну, решил ты «ужасающим методом», допустим. Проведи тогда хотя бы анализ решения, изучи его сходимость, проверь случая расхождения, поиграйся с оптимизацией, сравни с другими решениями — это все необходимо, чтобы твой опыт действительно стал полезным для других. Но здесь ничего этого и близко нет. Увы, пусть это и мои трудности, но лично я вижу только «не знаю и горжусь этим».
Это называется негативный перфекционизм, и с ним лучше бороться.
Негативным перфеционизмом является как раз обратное — это когда человеку, который первый раз в жизни что-то сделал приходит кто-то и говорит "ну куда ты со своим рылом в калашный ряд лезешь-то? Вот если бы ты поднапрягся, саморазвился, да показал бы что-то, достойное Старых Мастеров (гигантов, на чьих плечах покоится И. Ньютон), вот тогда да, а так-то ты, куда лезешь-то?".
Негативный перфекнционизм — одна из характерных черт русской культуры, требующей либо восхитить, либо устыдиться.
ну куда ты со своим рылом в калашный ряд лезешь-то
Меня удивляет, что вы смогли увидеть такой подтекст в моих словах о том, что: «Решил сам — молодец, правильный подход, если только это является лишь первым шагом, а не последним.»
По факту вы сейчас пытаетесь найти в моей фразе контекст, которого в ней нет, но который беспокоит вас лично.
Асимптотика? А то я ж могу и бинпоиском это сделать
И категорически вредно всегда пользоваться всем готовым, не имея никакого представления о внутреннем устройстве.Меня несколько смущает следующий вопрос — неужели вы никогда не слышали про итерационную формулу Герона? Было бы весьма похвально додуматься до нее самостоятельно какому-нибудь школьнику или первокурснику, но для профильного выпускника, который прослушал курс лекций по численным методам и вычислительной математике (и, по идее, заведомо перепробовал все эти алгоритмы задолго до окончания обучения), не знать подобных базовых вещей по меньшей мере странно. К сожалению, здесь это выглядит как бравирование собственным незнанием: «Не знаю и знать не хочу».
Логарифмическая сложность алгоритма? Или другая? :)Алгоритм имеет квадратичную сходимость, как и метод Ньютона, из которого он вытекает.
Кстати, какие возможности ускорения этого алгоритма можно реализовать на ваш взгляд?Основные правила по поиску возможностей таковы:
1. Подумать самостоятельно (для затравки)
2. Изучить имеющуюся базу/существующие решения
3. Подумать еще раз (о том, как сделать лучше)
4. Верифицировать идею
5. Если результаты неоптимальны, вернуться в пункт 1 и повторить цикл.
У вас здесь, к сожалению, в наличии только шаг 1, шаги 2-5 пропущены, иначе бы вы обнаружили, что одним из известных методов для улучшения выбранного вами метода является прескейлинг. Но лучше все же было бы заведомо исходить из того, что постоянное самообразование является строгой необходимостью для специалиста — меня удивляет, почему нынешняя молодежь не то что книги и учебники не читает, но даже затрудняется прогуляться до гугла и английской википедии, где описано весьма впечатляющее для затравочных размышлений количество методов вычисления корня.
Как ни странно, почти хорошо.
Радикальное улучшение будет, если root = 0.5 * ( rn + root); заменить на root = rn / n + root * (1.0 - 1.0 / n); — тогда будет чистый метод Ньютона. Отсюда видно, почему 0.5 для квадратного корня.
По мелочи — 1/rootn можно вычислить за логарифмическое число операций.
И "пять знаков после запятой" чаще интерпретируется как |root/rn — 1| < 10-5, а не как |rootn — rn| < 10-5, иначе для чисел порядка 10-6 будет получаться полная чушь.
пусть f(x) = x^^n=Y
Err= f(x0)-Y
dErr/dx = n*x^^(n-1)
dx = ( Y-f(x0) )/( n*x^^(n-1) )
x1= x0 + (Y — x0^^n )/(n*x0^^(n-1)) ==>
x1 = x0*(1-1/n) + (1/n)*Y / x0^^(n-1);
собственно, Ваш алгоритм для корня третьей степени отличается от приведенного мной тем, что он «Ваш» (первое) (а мой- Ньютона :-)),
константа 0,5 //root = 0.5 * ( rn + root);// не самая оптимальная в плане сходимости (второе), и вместо деления в цикле лучше использовать умножение, оно считается быстрее, а для корней большой степени его еще и можно ускорить (x^^7 = x*x^^2*(x^^2)^^2, вместо шести умножений- 2 умножения и два(!) возведения в квадрат, для x^^32 ускорение еще приятнее :-)) ( это третье)
double r_n1;
while(mabs(root — rn) >= eps){
r_n1 = 1.0;
for(int i = 1; i < rootDegree; i++){
r_n1 = r_n1 *root;
}
rn = root;
root = rn*(1.0 — 1/rootDegree) + (1.0/rootDegree) *num / r_n1;
countiter++;
}
П.С. а для квадратного корня Вы изобрели формулу Герона. ну как изобрели- Вам ее в школе рассказали, потом Вы ее забыли, а потом- изобрели. «честно нашел».
Почему бы не рассмотреть более общую задачу: нахождение x^p для произвольной вещественной степени p?
Алгоритм вычисления корня n-ой степени из произвольного положительного числа