c++ - sirve - que significa e en matematicas

Una forma eficiente de calcular la constante matemática e

Question

La representación estándar de la constante e como la suma de las series infinitas es muy ineficiente para el cálculo, debido a muchas operaciones de división. Entonces, ¿hay alguna forma alternativa de calcular la constante de manera eficiente?

¡Gracias!

EDITAR

Después de seguir algunos de sus enlaces, creo que la eficiencia proviene de una técnica llamada división binaria (mientras que la representación todavía se menciona en una serie), con la que no estaba familiarizado. Si alguien está familiarizado con él, siéntase libre de contribuir.

Answer 1

Como no es posible calcular cada dígito de ''e'', ​​tendrá que elegir un punto de parada.

Doble precisión: 16 decimales

Para aplicaciones prácticas, "el valor de punto flotante de precisión doble de 64 bits que es lo más cercano posible al valor verdadero de ''e'' - aproximadamente 16 dígitos decimales" es más que adecuado.

Como dijo KennyTM, ese valor ya se calculó previamente en la biblioteca matemática. Si desea calcularlo usted mismo, como señaló Hans Passant, el factorial ya crece muy rápido. Los primeros 22 términos de la serie ya son excesivos para calcular con esa precisión: agregar más términos de la serie no cambiará el resultado si se almacena en una variable de punto flotante de doble precisión de 64 bits. Creo que tardarás más en parpadear que en que tu computadora haga 22 divisiones. Así que no veo ninguna razón para optimizar esto aún más.

miles, millones o billones de dígitos decimales

Como señaló Matthieu M., este valor ya se ha calculado y puede descargarlo del sitio web de Yee.

Si desea calcularlo usted mismo, muchos dígitos no cabrán en un número de punto flotante de precisión doble estándar. Necesitas una biblioteca "bignum". Como siempre, puede usar una de las muchas bibliotecas bignum gratuitas ya disponibles, o reinventar la rueda creando su propia biblioteca bignum con sus propias peculiaridades especiales.

El resultado, un largo archivo de dígitos, no es muy útil, pero los programas para calcularlo a veces se usan como puntos de referencia para probar el rendimiento y la precisión del software de la biblioteca "bignum", y como pruebas de esfuerzo para verificar la estabilidad y la capacidad de enfriamiento. de nuevo hardware de la máquina.

Una página describe brevemente los algoritmos que Yee usa para calcular constantes matemáticas .

El artículo de Wikipedia "división binaria" entra en mucho más detalle. Creo que lo que está buscando es la representación numérica: en lugar de almacenar internamente todos los números como una larga serie de dígitos antes y después del punto decimal (o un punto binario), Yee almacena cada término y cada suma parcial como un número racional. - como dos enteros, cada uno de los cuales es una larga serie de dígitos. Por ejemplo, digamos que a una de las CPU trabajadoras se le asignó la suma parcial,

... 1/4! + 1/5! + 1/6! + ... .

En lugar de hacer la división primero para cada término, y luego agregar, y luego devolver un resultado de punto fijo de un millón de dígitos a la CPU del administrador:

// extended to a million digits
1/24 + 1/120 + 1/720 => 0.0416666 + 0.0083333 + 0.00138888

esa CPU puede sumar todos los términos de la serie juntos con aritmética racional y devolver el resultado racional a la CPU del administrador: dos enteros de unos pocos cientos de dígitos cada uno:

// faster
1/24 + 1/120 + 1/720 => 1/24 + 840/86400 => 106560/2073600

Una vez que se han agregado miles de términos de esta manera, la CPU del administrador hace la única división al final para obtener los dígitos decimales después del punto decimal.

Recuerde evitar la PrematureOptimization , y siempre ProfileBeforeOptimizing .

Answer 2

De wikipedia reemplazar x con 1

Answer 3

Desde mi punto de vista, la forma más eficiente de calcular e hasta la precisión deseada es usar la siguiente representación:

e := lim (n -> inf): (1 + (1/n))^n

Especialmente si eliges n = 2^x , puedes calcular la potencia con solo x multiplicaciones, ya que:

a^n = (a^2)^(n/2), if n % 2 = 0

Answer 4

Di esta respuesta en CodeReviews sobre la pregunta sobre computación e por su definición a través de la serie de Taylor (por lo tanto, otros métodos no eran una opción). El post-post aquí fue sugerido en los comentarios. He eliminado mis comentarios relevantes a ese otro tema; Aquellos interesados ​​en explicaciones adicionales pueden querer revisar la publicación original.

La solución en C (debería ser lo suficientemente fácil de adaptar para adaptarse a C ++):

#include <stdio.h>
#include <math.h>
int main ()
{
long double n = 0, f = 1;
int i;
for (i = 28; i >= 1; i--) {
f *= i; // f = 28*27*...*i = 28! / (i-1)!
n += f; // n = 28 + 28*27 + ... + 28! / (i-1)!
} // n = 28! * (1/0! + 1/1! + ... + 1/28!), f = 28!
n /= f;
printf("%.64llf/n", n);
printf("%.64llf/n", expl(1));
printf("%llg/n", n - expl(1));
printf("%d/n", n == expl(1));
}

Salida:

2.7182818284590452354281681079939403389289509505033493041992187500
2.7182818284590452354281681079939403389289509505033493041992187500
0
1

Hay dos puntos importantes:

1. Este código no calcula 1, 1 * 2, 1 * 2 * 3, ... que es O (n ^ 2), sino que calcula 1 * 2 * 3 * ... en una pasada (que es O (n )).

2. Comienza a partir de números más pequeños. Si tratamos de calcular

   1/1 + 1/2 + 1/6 + ... + 1/20!

   y traté de agregarlo 1/21 !, estaríamos agregando

   1/21! = 1/51090942171709440000 = 2E-20,

   a 2. algo, que no tiene efecto en el resultado (el double contiene aproximadamente 16 dígitos significativos). Este efecto se llama desbordamiento .

   Sin embargo, cuando empezamos con estos números, es decir, si calculamos 1/32! +1/31! + ... todos tienen algún impacto.

Esta solución parece estar de acuerdo con lo que C calcula con su función de expl , en mi máquina de 64 bits, compilada con gcc 4.7.2 20120921.

Answer 5

El método de división binaria se presta muy bien a un metaprograma de plantilla que produce un tipo que representa un racional correspondiente a una aproximación de e. 13 iteraciones parecen ser las máximas: cualquier valor superior producirá un error de "desbordamiento constante integral".

#include <iostream>
#include <iomanip>
template<int NUMER = 0, int DENOM = 1>
struct Rational
{
enum {NUMERATOR = NUMER};
enum {DENOMINATOR = DENOM};
static double value;
};
template<int NUMER, int DENOM>
double Rational<NUMER, DENOM>::value = static_cast<double> (NUMER) / DENOM;
template<int ITERS, class APPROX = Rational<2, 1>, int I = 2>
struct CalcE
{
typedef Rational<APPROX::NUMERATOR * I + 1, APPROX::DENOMINATOR * I> NewApprox;
typedef typename CalcE<ITERS, NewApprox, I + 1>::Result Result;
};
template<int ITERS, class APPROX>
struct CalcE<ITERS, APPROX, ITERS>
{
typedef APPROX Result;
};
int test (int argc, char* argv[])
{
std::cout << std::setprecision (9);
// ExpType is the type containing our approximation to e.
typedef CalcE<13>::Result ExpType;
// Call result() to produce the double value.
std::cout << "e ~ " << ExpType::value << std::endl;
return 0;
}

Otra variación de la plantilla (no metaprograma), en tiempo de compilación, calculará una doble aproximada e. Este no tiene el límite en el número de iteraciones.

#include <iostream>
#include <iomanip>
template<int ITERS, long long NUMERATOR = 2, long long DENOMINATOR = 1, int I = 2>
struct CalcE
{
static double result ()
{
return CalcE<ITERS, NUMERATOR * I + 1, DENOMINATOR * I, I + 1>::result ();
}
};
template<int ITERS, long long NUMERATOR, long long DENOMINATOR>
struct CalcE<ITERS, NUMERATOR, DENOMINATOR, ITERS>
{
static double result ()
{
return (double)NUMERATOR / DENOMINATOR;
}
};
int main (int argc, char* argv[])
{
std::cout << std::setprecision (16);
std::cout << "e ~ " << CalcE<16>::result () << std::endl;
return 0;
}

En una construcción optimizada, la expresión CalcE<16>::result () se reemplazará por el valor doble real.

Se puede decir que ambos son bastante eficientes ya que calculan e en tiempo de compilación :-)

Answer 6

Hay varios algoritmos de "spigot" que calculan los dígitos secuencialmente de una manera ilimitada. Esto es útil porque simplemente puede calcular el "siguiente" dígito a través de un número constante de operaciones aritméticas básicas, sin definir de antemano cuántos dígitos desea producir.

Estos aplican una serie de transformaciones sucesivas de modo que el siguiente dígito llegue al lugar de 1, para que no se vean afectados por los errores de redondeo de flotación. La eficiencia es alta porque estas transformaciones se pueden formular como multiplicaciones de matrices, que se reducen a la suma y multiplicación de enteros.

En definitiva, la expansión de la serie taylor.

e = 1/0! + 1/1! + 1/2! + 1/3! ... + 1/n!

Se puede reescribir factorizando partes fraccionarias de los factoriales (tenga en cuenta que para hacer que la serie sea regular, hemos movido 1 al lado izquierdo):

(e - 1) = 1 + (1/2)*(1 + (1/3)*(1 + (1/4)...))

Podemos definir una serie de funciones f1 (x) ... fn (x) así:

f1(x) = 1 + (1/2)x
f2(x) = 1 + (1/3)x
f3(x) = 1 + (1/4)x
...

El valor de e se encuentra en la composición de todas estas funciones:

(e-1) = f1(f2(f3(...fn(x))))

Podemos observar que el valor de x en cada función está determinado por la siguiente función, y que cada uno de estos valores está limitado en el rango [1,2], es decir, para cualquiera de estas funciones, el valor de x será 1 <= x <= 2

Dado que este es el caso, podemos establecer un límite inferior y superior para e utilizando los valores 1 y 2 para x respectivamente:

lower(e-1) = f1(1) = 1 + (1/2)*1 = 3/2 = 1.5
upper(e-1) = f1(2) = 1 + (1/2)*2 = 2

Podemos aumentar la precisión al componer las funciones definidas anteriormente, y cuando un dígito coincide en el límite superior e inferior, sabemos que nuestro valor calculado de e es preciso para ese dígito:

lower(e-1) = f1(f2(f3(1))) = 1 + (1/2)*(1 + (1/3)*(1 + (1/4)*1)) = 41/24 = 1.708333
upper(e-1) = f1(f2(f3(2))) = 1 + (1/2)*(1 + (1/3)*(1 + (1/4)*2)) = 7/4 = 1.75

Dado que los dígitos 1s y 10th coinciden, podemos decir que una aproximación de (e-1) con una precisión de 10ths es 1.7. Cuando el primer dígito coincide entre los límites superior e inferior, lo restamos y luego lo multiplicamos por 10; de esta manera, el dígito en cuestión siempre está en el lugar del 1 donde la precisión de punto flotante es alta.

La optimización real proviene de la técnica en álgebra lineal de describir una función lineal como una matriz de transformación. La composición de mapas de funciones para la multiplicación de matrices, por lo que todas esas funciones anidadas se pueden reducir a la simple multiplicación y suma de enteros. El procedimiento de restar el dígito y la multiplicación por 10 también constituye una transformación lineal y, por lo tanto, también se puede lograr mediante la multiplicación de matrices.

Otra explicación del método: http://www.hulver.com/scoop/story/2004/7/22/153549/352

El documento que describe el algoritmo: http://www.cs.ox.ac.uk/people/jeremy.gibbons/publications/spigot.pdf

Una introducción rápida para realizar transformaciones lineales mediante aritmética matricial: https://people.math.gatech.edu/~cain/notes/cal6.pdf

NB: este algoritmo utiliza transformaciones de Mobius, que son un tipo de transformación lineal que se describe brevemente en el artículo de Gibbons.

Answer 7

No tengo conocimiento de ningún cálculo "más rápido" que la expansión de Taylor de la serie, es decir:

e = 1/0! + 1/1! + 1/2! + ...

o

1 / e = 1/0! - 1/1! + 1/2! - ¡1/3! + ...

Considerando que estos fueron utilizados por A. Yee, quien calculó los primeros 500 mil millones de dígitos de e , supongo que no hay mucha optimización para hacerlo (o mejor, podría optimizarse, pero nadie encontró la forma, AFAIK)

EDITAR

Una implementación muy aproximada.

#include <iostream>
#include <iomanip>
using namespace std;
double gete(int nsteps)
{
// Let''s skip the first two terms
double res = 2.0;
double fact = 1;
for (int i=2; i<nsteps; i++)
{
fact *= i;
res += 1/fact;
}
return res;
}
int main()
{
cout << setprecision(50) << gete(10) << endl;
cout << setprecision(50) << gete(50) << endl;
}

Salidas

2.71828152557319224769116772222332656383514404296875
2.71828182845904553488480814849026501178741455078125

Answer 8

Puede ser capaz de ganar algo de eficiencia. Dado que cada término implica el siguiente factorial, se puede obtener cierta eficiencia al recordar el último valor del factorial.

e = 1 + 1/1! + 1/2! + 1/3! ...

Ampliando la ecuación:

e = 1 + 1/(1 * 1) + 1/(1 * 1 * 2) + 1/(1 * 2 * 3) ...

En lugar de calcular cada factorial, el denominador se multiplica por el siguiente incremento. Por lo tanto, mantener el denominador como variable y multiplicarlo producirá cierta optimización.

Answer 9

Si está utilizando double o float , ya hay una constante math.h en math.h

#define M_E 2.71828182845904523536028747135266250 /* e */

Hay otras representaciones de e en http://en.wikipedia.org/wiki/Representations_of_e#As_an_infinite_series ; Todos los implicarán división.

Answer 10

Si estás de acuerdo con una aproximación de hasta siete dígitos, usa

3-sqrt(5/63)
2.7182819

Si quieres el valor exacto:

e = (-1)^(1/(j*pi))

donde j es la unidad imaginaria y pi la constante matemática conocida (Identidad de Euler)

Answer 11

Esta página tiene un buen resumen de diferentes métodos de cálculo.

Este es un pequeño programa en C de Xavier Gourdon para calcular 9000 dígitos decimales de e en tu computadora. Existe un programa del mismo tipo para π y para algunas otras constantes definidas por medio de series hipergeométricas.

[Versión desglosada de https://codereview.stackexchange.com/a/33019 ]

#include <stdio.h>
int main() {
int N = 9009, a[9009], x;
for (int n = N - 1; n > 0; --n) {
a[n] = 1;
}
a[1] = 2;
while (N > 9) {
int n = N--;
while (--n) {
a[n] = x % n;
x = 10 * a[n-1] + x/n;
}
printf("%d", x);
}
return 0;
}

Este programa [cuando se usa el código de golf] tiene 117 caracteres. Se puede cambiar para calcular más dígitos (cambiar el valor 9009 a más) y para ser más rápido (cambiar la constante 10 a otra potencia de 10 y el comando printf). Una pregunta no tan obvia es encontrar el algoritmo utilizado.