Un moyen efficace de calculer la constante mathématique e

Question

La représentation standard de la constante e comme la somme des séries infinies est très inefficace pour le calcul, car de nombreuses opérations division. Donc, il y a un autre manières de calculer la constante de manière efficace?

Merci!

MODIFIER

Après avoir suivi certains de vos liens, je crois que l'efficacité vient d'une technique appelée le découpage binaire (bien que la représentation est encore mentionné de la série), dont je n'étais pas familier avec. Si quelqu'un est familier avec elle, n'hésitez pas à contribuer.

Answer 1

Puisqu'il n'est pas possible de calculer tous les chiffres de "e", vous allez devoir choisir un point d'arrêt.

double précision: de 16 chiffres décimaux

Pour les applications pratiques, "le 64 bits en virgule flottante double précision de la valeur qui est aussi proche que possible de la vraie valeur de" e "-- environ 16 chiffres décimaux" est plus que suffisant.

Comme KennyTM dit, cette valeur a déjà été pré-calculé pour vous dans la bibliothèque de mathématiques. Si vous voulez calculer vous-même, comme Hans Passant souligné, factorielle déjà pousse très vite. Les 22 premiers termes de la série est déjà trop pour le calcul de la précision -- l'ajout d'autres termes de la série ne change pas le résultat si il est stocké dans un 64 bits à virgule flottante en double précision variable. Je pense que ça va prendre plus de temps à clignoter que pour votre ordinateur pour faire de la 22 divise. Donc je ne vois pas de raison pour optimiser davantage.

des milliers, des millions, voire des milliards de chiffres après la virgule

Comme Matthieu M. souligné, cette valeur a déjà été calculée, et vous pouvez le télécharger à partir Yee site web.

Si vous voulez calculer vous-même, que de nombreux chiffres ne correspondent pas au standard d'un double-nombre à virgule flottante. Vous avez besoin d'un "bignum" de la bibliothèque. Comme toujours, vous pouvez soit utiliser l'un des nombreux gratuit bignum bibliothèques déjà disponibles, ou de ré-inventer la roue, par la construction de votre propre encore une autre bignum bibliothèque avec ses propres caprices.

Le résultat, une longue file de chiffres n'est pas très utile, mais les programmes de calcul sont parfois utilisés comme points de référence pour tester les performances et la précision de "bignum" logiciel de bibliothèque, et que le stress tests pour vérifier la stabilité et la capacité de refroidissement de nouveau matériel de la machine.

Une page très brièvement décrit les algorithmes Yee utilise pour calculer les constantes mathématiques.

Wikipédia, "le découpage binaire" de l'article va dans beaucoup plus de détails. Je pense que la pièce que vous cherchez est le nombre de représentation: au lieu d'en interne, le stockage de tous les nombres comme une longue série de chiffres avant et après la virgule (ou un binaire point), Yee magasins de chaque terme et chaque somme partielle comme un nombre rationnel -- comme deux entiers, dont chacun est une longue série de chiffres. Par exemple, dire que l'un des travailleurs de Processeurs a été affecté de la somme partielle,

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

Au lieu de faire la division de première, pour chaque terme, puis en ajoutant, puis retour à un seul million de chiffres à virgule fixe suite à la gestionnaire de l'unité centrale de traitement:

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

que le CPU peut ajouter tous les termes dans la série des premières rationnelle de l'arithmétique, et de retourner les résultats raisonnables pour le gestionnaire de l'unité centrale de traitement: deux entiers de peut-être quelques centaines de chiffres:

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

Après des milliers de termes ont été ajoutés ensemble de cette façon, le gestionnaire de CPU ne la seule division à la fin pour obtenir les chiffres décimaux après la virgule.

N'oubliez pas d'éviter PrematureOptimization, et toujours ProfileBeforeOptimizing.

Answer 2

Je ne suis pas au courant de tout "plus vite" calcul que le développement de Taylor de la série, c'est à dire:

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

ou

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

Considérant que ces ont été utilisés par A. Yee, qui a calculé le premier à 500 milliards de dollars de chiffres d' e, je suppose qu'il n'y a pas beaucoup de l'optimisation à faire (ou mieux, il pourrait être optimisée, mais personne n'a encore trouvé un moyen, autant que je sache)

MODIFIER

Une mauvaise mise en œuvre

#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;
}

Sorties

2.71828152557319224769116772222332656383514404296875
2.71828182845904553488480814849026501178741455078125

Answer 3

Si vous utilisez double ou float , il y a un M_E constant en math.h déjà.

 #define M_E         2.71828182845904523536028747135266250   /* e */
 

Il existe d'autres représentations de e dans http://en.wikipedia.org/wiki/Representations_of_e#As_an_infinite_series ; tous impliqueront la division.

Answer 4

Cette page a un bel aperçu des différentes méthodes de calcul.

C'est un tout petit programme C de Xavier Gourdon pour calculer 9000 décimales de e sur votre ordinateur. Un programme du même type existe pour le π et pour certains autres constantes définies par la moyenne des séries hypergéométriques.

[degolfed version de http://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;
  }

Ce programme [lorsque le code-ont joué au golf] a 117 caractères. Il peut être changé pour calculer plus de chiffres (changement de la valeur 9009 de plus) et pour être plus rapide (changement de la constante de 10 à une autre puissance de 10 et le printf de commande). Une question évidente est de trouver l'algorithme utilisé.

Answer 5

J'ai donné cette réponse à CodeReviews sur la question relative à l'informatique e par sa définition par la série de Taylor (ainsi, d'autres méthodes ne sont pas une option). La croix-post ici a été suggéré dans les commentaires. J'ai enlevé mes remarques pertinentes à ce sujet; Ceux qui souhaitent plus d'explications migth voulez vérifier le post original.

---

La solution en C (ce qui devrait être assez facile à adapter à adapter à 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));
}

Sortie:

2.7182818284590452354281681079939403389289509505033493041992187500
2.7182818284590452354281681079939403389289509505033493041992187500
0
1

Il y a deux points importants:

1. Ce code ne nécessite pas de calcul 1, 1*2, 1*2*3,... qui est O(n^2), mais calcule 1*2*3*... en un seul passage (qui est O(n)).

2. Il commence à partir de plus petits nombres. Si nous avons essayé de calculer

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

   et a essayé de l'ajouter 1/21!, nous serions en ajoutant

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

   2.quelque chose, qui n'a aucun effet sur le résultat (double détient environ 16 chiffres significatifs). Cet effet est appelé underflow.

   Cependant, quand on commence avec ces chiffres, c'est à dire, si nous calculons 1/32!+1/31!+... ils ont tous un certain impact.

Cette solution semble conformément à ce que C calcule avec ses expl de la fonction, sur ma machine 64 bits, compilé avec gcc 4.7.2 20120921.