Популярно о науке

Previous Entry Share Next Entry
Пояснение\указание
ahiin
к менее типичной задаче.

Очевидно, я недостаточно внятно сформулировал задачу, в результате ряд уважаемых читателей решили, что основная проблема — это оценка остатка и увлеченно принялись эту оценку искать. Сам по себе, поиск такой оценки  — дело интересное, но в рамках исходной задачи не самое важное.

Суть в том, что ряд, который я вам предложил, "в лоб" с требуемой точностью не суммируется. (Уважаемый son_0f_morning меня убедительно опроверг, сумев уложиться в лимит времени суммируя исходный ряд. Снимаю шляпу, посыпаю голову пеплом.) Изучив его код, я понял, что с пеплом поторопился. Идея воплощена годная, но это очень сильно не "в лоб".
А чтобы вы свою жизнь не тратили на эти обреченные попытки, установлен жесткий лимит времени (напомню, если ваша программа считает дольше 10 секунд, значит задача не решена \надо было ставить 100 мс\). И вот найти выход, извернуться и просуммировать, таки, ряд, вот в этом суть.

Для облегчения жизни присутствующих, под катом выложены результаты моих расчетов. Абсолютная погрешность заведомо не более 1e-14, так что сравнивайте со своими расчетами смело, не заморачиваясь оценками хвостов. Суть не в хвостах.


1.6449340668482264
1.5346072449045607
1.4408788415467229
1.360082586782444
1.2895778007910417
1.2274112777602189
1.1721051961250153
1.1225193425357527
1.0777588727442429
1.0371109178506583
0.99999999999999989


Время счета моей (изрядно продвинутой) современной версии составило в один поток около 3 миллисекунд (на самом деле около 8 микросекунд, если не включать время работы потока вывода). Но даже то, что я в 2002 году написал на Турбо Паскале, в лимит времени укладывалось. Дерзайте.

И еще. Имейте в виду. Использование всевозможных констант при расчете вполне кошерно. А вот если вы используете формулы, в которых выражение, содержащее аргумент Х, попадает под действие трансцендентной функции (особенно такой нетривиальной, как дигамма), то значит вы жульничаете, перекладывая задачу суммирования ряда на плечи автора математической библиотеки.

  • 1
Интересно, что решение "в лоб":

11 раз складываем:
- 100 000 членов последовательности
- 100 000 членов ряда эйлера
- берём остаточный член от ряда эйлена

Даёт скорость 30 миллисекунд.

Вариант увеличить скорость в 10 раз (без привлечения SIMD их в плавучке у нас вроде нету?) или аналитики) реальный:
- вдвое за счёт 1-кратного подсчёта ряда эйлера
- ещё в 1.5 раза за счёт того, что все 11 рядов считаем одновременно -- получим более плотное использование FPU в коде.
- ещё в 3 раза -- за счёт сокращения кол-ва суммируемых членов ряда и работы с "ожидаемой" погрешностью


Но тут мы получим точность "впритык" к 10^-10.
А как получить (при той же скорости) на 4 порядка больше -- не представляю.
Надо аналитически исследовать ряд, интересно что вы сделали.





Edited at 2018-03-28 10:51 am (UTC)

Да, это полное время.
Чтоб вам окончательно отринуть решение "в лоб". Персонально для себя считайте погрешность 1e-12 (-13, -14). Суть не меняется совершенно, запаса по времени хватает с избытком.

Для замеров точности

Решил измерить как хорошо себя ведёт решение на Си -- т.е.его примерная точность (от числа элементов). Для этого посчитал задачку поточнее, если кому надо выкладываю более точные результаты тут:

Точность 23 знака:
long double answer[] = {
1.644934066848226308227702251860034101764,
1.534607244904560654382959377390414933720,
1.440878841546722825296521304828894296399,
1.360082586782444016584503720145821215388,
1.289577800791041787189592186753823607729,
1.227411277760218762331072180833930389026,
1.172105196125015187520858679904696591036,
1.122519342535752596123538201084308469275,
1.077758872744243001519018737823589429800,
1.037110917850658422034710860012204247854,
1.000000000000000000000000666666626666798
};



ПС
Старое (вчерашнее) точность 18 знаков
long double answer[] = {
1.644934066848226308227702251860034101764,
1.534607244904560654466291906557226101304,
1.440878841546722825379853821495737464062,
1.360082586782444016667836224312699715910,
1.289577800791041787272924678420740771285,
1.227411277760218762414404660000889560806,
1.172105196125015187604191146571701093001,
1.122519342535752596206870655251361632025,
1.077758872744243001602351179490694597154,
1.037110917850658422118043289179364746803,
1.000000000000000000083333083333845832436
};

Edited at 2018-03-29 09:15 am (UTC)

  • 1
?

Log in

No account? Create an account