La evaluación precisa de 1/1 + 1/2 + ... 1 / n fila

Question

necesito para evaluar la suma de la fila: 1/1 + 1/2 + 1/3 + ... + 1 / n. Teniendo en cuenta que en las evaluaciones de C ++ no están completos precisa, el orden de la suma juega un papel importante. 1 / n + 1 / (n-1) + ... + 1/2 + 1/1 expresión da el resultado más preciso. Así que necesito para averiguar el orden de la suma, que proporciona la máxima precisión. Ni siquiera sé por dónde empezar. Idioma preferido de realización es C ++. Lo siento por mi Inglés, si hay algún error.

Answer 1

En realidad, si usted está haciendo la suma de N grande, añadiendo en orden de menor a mayor no es la mejor manera - todavía se puede llegar a una situación donde los números que estás agregando son demasiado pequeñas en relación con el suma para producir un resultado preciso.

Mira el problema de esta manera: Usted tiene N sumas, sin importar el orden y desea tener el menor error total. Por lo tanto, usted debe ser capaz de obtener el error total de menos minimizando el error de cada suma - y minimizar el error en la suma añadiendo valores como casi cerca entre sí como sea posible. Creo que después de que la cadena de la lógica le da un árbol binario de sumas parciales:

Sum[0,i] = value[i]

Sum[1,i/2] = Sum[0,i] + Sum[0,i+1]

Sum[j+1,i/2] = Sum[j,i] + Sum[j,i+1]

y así sucesivamente hasta llegar a una única respuesta.

Por supuesto, cuando N no es una potencia de dos, que va a terminar con las sobras en cada etapa, lo que usted necesita para llevar encima en las sumatorias en la próxima etapa.

(Los márgenes de Stackoverflow son, por supuesto, demasiado pequeña para incluir una prueba de que esto es óptimo. En parte porque no he tomado el tiempo para probarlo. Pero funciona para cualquier N, por muy grande, ya que todos las adiciones están agregando valores de magnitud casi idénticos. Bueno, todos menos log (N) de ellos en el peor de los casos no-potencia de 2, y que es extremadamente pequeña en comparación con N.)

Answer 2

Para n grande es mejor utilizar fórmulas asintóticas, como las de http: // en. wikipedia.org/wiki/Harmonic_number ;

Otra forma es utilizar la transformación exp-registro. Básicamente:

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)).

Los exponentes y logaritmos se pueden calcular con bastante rapidez y, fielmente por su biblioteca estándar. El uso de la multiplicación debe obtener resultados mucho más precisos.

Si esta es su tarea y que están obligados a utilizar una simple suma, se le agrega un mejor desde la más pequeña a la más grande, como otros sugirieron.

Answer 3

La razón de la falta de precisión es la precisión del flotador, dobles, dobles y tipos largos. Ellos sólo almacenan tantos lugares decimales "". Por lo que añadir un valor muy pequeño en un valor grande no tiene ningún efecto, el término pequeño se "pierde" en el más grande.

La serie está sumando tiene una "cola larga", en el sentido de que las pequeñas términos deben sumar a una gran contribución. Pero si usted resumir en orden descendente, a continuación, después de un tiempo cada nuevo término pequeño no tendrá ningún efecto (incluso antes de eso, la mayoría de sus cifras decimales serán descartados). Una vez que llegue a ese punto se puede añadir más de mil millones de términos, y si los hace uno a la vez que todavía no tiene ningún efecto.

Creo que sumando en orden ascendente debe dar una mayor precisión para este tipo de serie, aunque es posible que hay algunos casos de esquina impares donde los errores debido al redondeo de las facultades de (1/2) por lo que sólo podría suceder para dar un cerrador responder por adición de algunas órdenes que otros. Es probable que no se puede predecir esto, sin embargo.

Answer 4

  

No sé ni por dónde empezar.

A continuación: Lo que todo informático debe saber sobre la aritmética de punto flotante

Answer 5

http://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic Puede encontrar bibliotecas con listo para su implementación uso para C / C ++.

Por ejemplo http://www.apfloat.org/apfloat/

Answer 6

A menos que utilice una representación precisa de forma cerrada, un pequeño a gran suma ordenada es probable que sea simple solución más precisa (no me queda claro por qué un log-exp ayudaría - que es un buen truco, pero no estamos ganando nada con ella aquí, por lo que yo puedo decir).

Puede obtener una mayor precisión al darse cuenta de que después de un tiempo, la suma se convertirá en "cuantificado": Efectivamente, cuando se tiene 2 dígitos de precisión, la adición de 1,3 a 41 resultados en el 42, no 42.3 - pero conseguir casi una precisión duplicar mediante el mantenimiento de un término de "error". Esto se llama Kahan Suma . Se podría calcular el término de error (42-41-1.3 == -0,3) y correcta que en la próxima Además mediante la adición de 0,3 al próximo mandato antes de añadir de nuevo.

Kahan Suma además de un pedido de pequeño a grande es susceptible de ser lo más preciso que usted necesitará siempre de conseguir. Tengo serias dudas de que alguna vez necesitas algo mejor para la serie armónica - después de todo, incluso después de 2 ^ 45 iteraciones (loco muchos) que le sigue sólo se esté tratando con un número que son al menos 1/2 ^ 45 grandes, y una suma que es del orden de 45 (<2 ^ 6), por un orden de magnitud de diferencia de 51 potencias de dos hijos -. es decir, incluso aún representable en una variable de doble precisión si se añade a la orden "equivocado"

Si usted va de pequeño a grande, y utiliza Kahan Suma, del sol probablemente va a extinguir antes de los procesadores de hoy en día alcanzan un porcentaje de error - y se encontrará con otros problemas de precisión complicado simplemente debido al error individual plazo sobre que escala primero de todos modos (siendo que un número del orden de 2 ^ 53 o mayor no se puede representar con precisión como una doble en absoluto de todos modos.)

Answer 7

No estoy seguro acerca de la orden de la suma de jugar un papel importante, no he oído eso antes. Supongo que quieres hacer esto en aritmética de punto flotante así que lo primero es pensar más en línea de (1.0 / 1.0 + 1.0 / 2.0 + 1.0 / 3.0) - de lo contrario el compilador hará la división entera

para determinar el orden de evaluación, tal vez un bucle for o soportes?

por ejemplo.

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

oh olvidó decir, los compiladores normalmente tienen interruptores para determinar el modo de evaluación de coma flotante. esto es tal vez relacionado con lo que se dice en el orden de la suma - en visual C + Estos se encuentran en la generación de código compilar la configuración, en g ++ hay opciones estés -float que manejar esto

En realidad, el otro tipo es correcto - que debe hacer la suma con el fin de componente más pequeño primero; entonces 1 / n + 1 / (n-1) .. 1/1

Esto es porque la precisión de un número de coma flotante se une a la escala, si se inicia en 1 tendrá 23 bits de precisión relativa a 1,0. si se inicia en un número más pequeño de la precisión es relativo al número más pequeño, de manera que obtendrá 23 bits de precisión en relación con 1XE-200 o lo que sea. a continuación, ya que el número se pone ocurrirá más grande error de redondeo, pero el error total será menor que la otra dirección

Answer 8

Como todos los números son números racionales, los más fáciles (y tal vez también el más rápido, ya que tendrá que hacer operaciones de coma menos flotante) sería hacer los cálculos con números racionales (tuplas de 2 enteros p, q), y luego no sólo un punto de división flotante al final.

actualización para utilizar esta técnica eficacia con la que tendrá que utilizar para bigints p & q, a medida que crecen bastante rápido ...

Un prototipo rápido en Lisp, que se ha acumulado en los racionales muestra:

(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]

Por lo tanto, la siguiente mejor opción podría ser la de MANTENER la lista de puntos flotantes y para reducirlo sumando los dos números más pequeños en cada paso ...