Точная оценка 1/1 + 1/2 + … 1/n строка

Для больших n лучше использовать асимптотические формулы, подобные приведенным на http://en.wikipedia.org/wiki/Harmonic_number ;

Другой способ заключается в использовании преобразования exp-log. Обычно:

H_n = 1 + 1/2 + 1/3 + ... + 1 / n = log (exp (1 + 1/2 + 1/3 + ... + 1 / n)) = log (exp (1) * exp (1/2) * exp (1/3) * ... * exp (1 / n)).

Экспоненты и логарифмы могут быть вычислены довольно быстро и точно с помощью вашей стандартной библиотеки. Используя умножение, вы должны получить гораздо более точные результаты.

Если это ваша домашняя работа и вам необходимо использовать простое сложение, вам лучше прибавить от наименьшего к наибольшему, как предлагали другие.

Причина отсутствия точности заключается в точности типов float, double и long double. Они хранят только определенное количество десятичных знаков. Таким образом, добавление очень маленького значения к большому значению не имеет никакого эффекта, меньший член «теряется» в большом.

Ряд, который вы суммируете, имеет «длинный хвост» в том смысле, что маленькие члены должны добавить к большому вкладу. Но если вы суммируете в порядке убывания, то через некоторое время каждый новый маленький член не будет иметь никакого эффекта (даже до этого большая часть его десятичных знаков будет отброшена). Как только вы доберетесь до этой точки, вы можете добавить еще миллиард членов, и если вы будете делать их по одному, это все равно не даст никакого эффекта.

Я думаю, что суммирование в порядке возрастания должно дать наилучшую точность для такого рода рядов, хотя Это' Возможно, есть некоторые нечетные угловые случаи, когда ошибки из-за округления до степени (1/2) могут просто так дать более точный ответ для одних порядков сложения, чем для других. Однако вы, вероятно, не можете этого предсказать.

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic Вы можете найти библиотеки с готовой к использованию реализацией для C / C ++.

Например http://www.apfloat.org/apfloat/

Если вы не используете какое-то точное представление в замкнутой форме, упорядоченное суммирование от малого к большому, вероятно, будет наиболее точным простым решением (мне не ясно, почему логарифмическое экспонирование может помочь - это изящный трюк, но, насколько я могу судить, здесь вы ничего не выиграете).

Вы можете еще больше повысить точность, если поймете, что через некоторое время сумма станет "квантованной": эффективно, когда у вас есть 2 цифры точности, добавление 1,3 к 41 дает 42, а не 42,3 - но вы достигаете почти удвоения точности, сохраняя термин «ошибка». Это называется суммированием Кахана . Вы должны вычислить член ошибки (42-41-1,3 == -0,3) и исправить его в следующем добавлении, добавив 0,3 к следующему члену, прежде чем добавлять его снова.

Суммирование Кахана в дополнение к упорядочиванию от малого к большому, должно быть настолько точным, насколько вам когда-либо понадобится. Я серьезно сомневаюсь, что вам когда-нибудь понадобится что-нибудь получше для гармонического ряда - в конце концов, даже после 2 ^ 45 итераций (безумно много) вы все равно будете иметь дело только с числами, которые по крайней мере 1/2 ^ 45 больших, и сумма порядка 45 (<2 ^ 6) для разницы на порядок величин в 51 степень двойки, т.е. даже может быть представлена ​​в переменной двойной точности, если вы добавляете в «неправильном» порядке.

Если вы переходите от малого к большому и используете суммирование Кахана, солнце, вероятно, погаснет до того, как сегодняшние процессоры достигнут процента погрешности - и вы '

Так как все ваши числа являются рациональными, самым простым (а также, возможно, самым быстрым, поскольку потребуется меньше операций с плавающей запятой) будет выполнение вычислений с рациональными числами (кортежами из двух целых чисел). p, q), а затем сделайте только одно деление с плавающей запятой в конце.

update для эффективного использования этой техники вам нужно будет использовать bigints для p & q, поскольку они растут довольно быстро ...

Быстрый прототип на Лиспе, в который встроены рациональные числа, показывает:

(defun sum_harmonic (n acc)
  (if (= n 0) acc (sum_harmonic (- n 1) (+ acc (/ 1 n)))))

(sum_harmonic 10 0)
7381/2520
[2.9289682]

(sum_harmonic 100 0)
14466636279520351160221518043104131447711/278881500918849908658135235741249214272
[5.1873775]

(sum_harmonic 1000 0)

53362913282294785045591045624042980409652472280384260097101349248456268889497101
75750609790198503569140908873155046809837844217211788500946430234432656602250210
02784256328520814055449412104425101426727702947747127089179639677796104532246924
26866468888281582071984897105110796873249319155529397017508931564519976085734473
01418328401172441228064907430770373668317005580029365923508858936023528585280816
0759574737836655413175508131522517/712886527466509305316638415571427292066835886
18858930404520019911543240875811114994764441519138715869117178170195752565129802
64067621009251465871004305131072686268143200196609974862745937188343705015434452
52373974529896314567498212823695623282379401106880926231770886197954079124775455
80493264757378299233527517967352480424636380511370343312147817468508784534856780
21888075373249921995672056932029099390891687487672697950931603520000
[7.485471]

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

Я не уверен, что порядок суммирования играет важную роль, я не слышал об этом раньше. Я предполагаю, что вы хотите сделать это в арифметике с плавающей запятой, поэтому сначала нужно подумать о более встроенном (1.0 / 1.0 + 1.0 / 2.0 + 1.0 / 3.0) - иначе компилятор будет выполнять целочисленное деление

, чтобы определить порядок оценки , может быть, цикл for или скобки?

например

float f = 0.0;
for (int i=n; i>0; --i) 
{
    f += 1.0/static_cast<float>(i);
}

о, забыл сказать, компиляторы обычно имеют переключатели для определения режима вычисления с плавающей запятой. возможно, это связано с тем, что вы говорите о порядке суммирования - в Visual C + они находятся в настройках компиляции генерации кода, в g ++ есть параметры -float, которые на самом деле обрабатывают это

, другой прав - сначала нужно произвести суммирование в порядке наименьшего компонента; так 1 / n + 1 / (n-1) .. 1/1

это потому, что точность числа с плавающей запятой связана с масштабом, если вы начнете с 1, у вас будет 23 бита точности относительно 1.0. если вы начнете с меньшего числа, точность будет относиться к меньшему числу, поэтому вы получите 23 бита точности относительно 1xe-200 или чего-то еще. тогда по мере увеличения числа будет возникать ошибка округления, но общая ошибка будет меньше, чем в другом направлении

Я даже не знаю, с чего начать.

Здесь: Что каждый компьютерный ученый должен знать об арифметике с плавающей запятой