Quel est le moyen le plus rapide pour calculer e pour 2 billions de dollars de chiffres?

Question

Je veux calculer e pour 2 milliards de dollars (2,000,000,000,000) chiffres. C'est environ 1,8 TiB de pur e. J'ai juste mis en œuvre un développement en série de taylor d'extension de l'algorithme à l'aide de GMP (code peut être trouvé ici).

Unfortuanetly il se bloque lors de la sommation de plus de 4000 termes sur mon ordinateur, probablement parce qu'il est à court de mémoire.

Quel est l'état actuel de l'art dans le calcul de e? L'algorithme est le plus rapide? Open source implémentations qui sont la peine de regarder? Veuillez ne pas parler de y-cruncher, il est fermé à la source.

Answer 1

Depuis que je suis l'auteur de la y-cruncher programme que vous évoquez, je vais ajouter mes 2 cents.

Pour une telle tâche, les deux principaux obstacles qui doivent être abordées sont les suivantes:

1. De mémoire
2. Au moment de l'exécution de la Complexité

De mémoire

2 billions de dollars de chiffres est extrême - pour dire le moins. C'est le double de l' actuel record établi par Shigeru Kondo et moi-même de retour en 2010. (Il nous a fallu plus de 9 jours pour calculer 1 billion de dollars de chiffres d'utiliser y-cruncher.)

En texte brut, c'est environ 1,8 TiB en décimal. Dans les paniers représentation binaire, c'est 773 GiB.

Si vous allez faire de l'arithmétique sur les nombres de cette taille, vous allez avoir besoin d' 773 GiB pour chaque opérande pas de comptage à zéro de la mémoire.

Mises en parler, y-cruncher a réellement besoin 8.76 TiB de mémoire pour faire ce calcul tous dans la ram. Vous pouvez donc vous attendre à d'autres implémentations besoin de la donner ou de prendre un facteur de 2 au plus.

Cela dit, je doute que tu vas avoir assez de ram. Et même si vous l'avez fait, il serait fortement NUMA. Donc l'alternative est d'utiliser le disque. Mais ce n'est pas anodin, car pour être efficace, vous avez besoin pour traiter de la mémoire comme mémoire cache et de la microgestion de toutes les données qui sont transférées entre la mémoire et le disque.

---

Au moment de l'exécution de la Complexité

Ici nous avons un autre problème. Pour 2 billions de dollars de chiffres, vous allez avoir besoin d'un très rapide de l'algorithme. Pas n'importe quel algorithme rapide, mais une quasi-linéaire au moment de l'exécution de l'algorithme.

Votre tentative s'étend en O(N^2). Donc, même si vous avez eu assez de mémoire, il n'arrive pas à terminer dans votre vie.

L'approche standard pour le calcul de e de haute précision s'exécute en O(N log(N)^2) et combine les algorithmes suivants:

• Le découpage binaire sur le développement en série de Taylor de l'expansion de l' e.
• FFT grande multiplication

Heureusement, GMP utilise déjà FFT grande multiplication. Mais il manque deux caractéristiques fondamentales:

1. Out-of-core (swap) de calcul à utiliser le disque quand il n'y a pas assez de mémoire.
2. Il n'est pas parallélisé.

Le second point n'est pas important puisque vous pouvez simplement attendre plus longtemps. Mais pour toutes fins utiles, vous êtes probablement va avoir besoin pour le déploiement de votre propre. Et c'est ce que j'ai fait quand j'ai écrit y-cruncher.

---

Cela dit, il ya beaucoup d'autres lâche-ends et qui doivent également être pris en charge de:

1. La finale de la division nécessitera un algorithme rapide comme la Méthode de Newton.
2. Si tu vas calculer en binaire, vous allez avoir besoin de faire une base de conversion.
3. Si le calcul est va prendre beaucoup de temps et beaucoup de ressources, vous pouvez avoir besoin pour mettre en œuvre la tolérance de pannes pour gérer les pannes de matériel.

Answer 2

Puisque vous avez un objectif de combien de chiffres que vous voulez (de 2 billions de dollars), vous pouvez estimer le nombre de termes que vous aurez besoin de calculer le e de plus que le nombre de chiffres. À partir de cela, vous pouvez estimer le nombre de chiffres de précision, vous aurez besoin de suivre pour éviter les erreurs d'arrondi lors de la 2 billionième place.

Si mon calcul de Stirling approximation est correcte, la réciproque de 10 à la de 2 billions de dollars est sur la réciproque de 100 milliards de dollars factorielle. Donc, c'est sur le nombre de termes que vous aurez besoin (100 milliards). L'histoire est un peu mieux que cela, cependant, parce que vous allez commencer à être en mesure de jeter beaucoup de chiffres dans le calcul des termes bien avant.

Depuis e est calculé comme la somme des inverses des factorielles, tous vos termes sont rationnels, et par conséquent, ils sont exprimables que de répéter des décimales. Si la décimale expansion de vos termes de (a) un exposant, (b) un non-répétition de partie, et (c) une répétition de partie. Il peut y avoir certains gains d'efficacité, vous pouvez profiter de si vous regardez les conditions de cette façon.

De toute façon, bonne chance!