Nota pour plus tard : avec 30 To, on écrit 72×10¹² décimales.

Compte supprimé · Le 01/06/2015, à 03:46

Mon esprit se reposait et je me suis dit qu'en réorganisant les bits, on peut gagner de la place sur les disques pour les données décimales au format non-compressés.

Ça existe peut-être déjà, mais je perdrais plus de temps à chercher que qui se fait qu'à écrire mon idée venue la tête sur l'oreiller, si jamais ça n'existait pas, bien que je doute. Quelqu'un y a forcément pensé, donc c'est mon pense-bête.

10 octets ←→ 80 bits = 8×10 bits = (1024)⁸

Typiquement avec 10 bits, 1024 valeurs, on code facilement les entiers de 0 à 999, soient 3 chiffres.
avec 8×10 bits, (1024)⁸ valeurs, on code facilement les entiers de 0 à 999 999 999 999 999 999 999 999, soient 8×3=24 chiffres pour 10 octets (un gain de 2,4 si on n'avait mis qu'un chiffre par octet, ou un gain de 1,2 si on avait mis de chiffres formant un nombre de 0 à 99 pour un octet.)

Quelqu'un y a forcément pensé, donc c'est mon pense-bête. Et si ça sert à quelqu'un, tant mieux.

Y'a plus qu'à trouver quelques To (1 téraoctet : 10¹² octets) de disques-durs, ou louer quelques Po (1 pétaoctets : 10¹⁵ octets) et un algorithme qui fasse tomber une décimale à chaque cycle d'horloge, et Pi va vite remplir les disques !

Le dernier record date du 27/07/2013 avec un temps de 4 min 33 s 188 sur un core i7-4770k cadence à 6766 MHz sous azote par le Taïwanais Andre Yang avec le logiciel Super Pi.
Ça fait 273,1888 secondes soient 1,848395421×10¹² cycles pour calculer seulement 32 millions de décimales ? ça fait 57762 cycles par décimale …

Une itération, une décimale, c'est mieux

claudius01 · Le 01/06/2015, à 10:34

Bonjour,

C'est effectivement une bonne idée pour diminuer la taille de mémorisation d'une suite de chiffres [0-9].
Une autre idée serait d'utiliser le système trinaire très en vogue au siècle dernier.

L_d_v_c@ a écrit :

... Y'a plus qu'à trouver un algorithme qui fasse tomber une décimale à chaque cycle d'horloge ...

Me trompe-je si j'interprète "chaque cycle d'horloge" comme "chaque itération" ?
Cet algorithme existe et est appelé L'algorithme compte-gouttes

Maintenant, sauf erreur de ma part, l'algorithme utilisé dans Super Pi est l'algorithme de Gauss-Legendre qui est beaucoup plus efficace car produit 2 fois plus de décimales exactes à chaque itération ;-)

Compte supprimé · Le 01/06/2015, à 15:38

claudius01 a écrit :

Bonjour,
C'est effectivement une bonne idée pour diminuer la taille de mémorisation d'une suite de chiffres [0-9].
Une autre idée serait d'utiliser le système trinaire très en vogue au siècle dernier.

Bonjour,
Les mémoire dynamiques de type SDRAM (DDR, DDR2, DDR3…) sont utilisées en binaires (2 états : état haut - état bas), et même si chaque case mémoire se résume en un transistor et un condensateur, qui peuvent prendre plusieurs tensions entre 0V et +Vcc), les contrôleurs intégrés rafraîchissant ces mémoires ne travaillent qu'en binaire et ne peuvent plus fonctionner autrement de nos jours, garantissant la sécurité de l'information, et le prix ridicule de ces mémoires, comparées aux prix des mémoires statiques monopolisant plusieurs transistors par bit. Sans oublier les parités de mémoires dynamique ECC où on ne veut plus d'erreur. Je ne suis pas sur que les premières mémoires dynamiques, rafraîchies par un contrôleur externe à la barrette, aient pu un jour fonctionner en plusieurs niveaux. Il me semble avoir aperçu une tentative expérimentale d'un projet vidéo (niveau hardware) et très vite plusieurs niveaux entraînent un rafraîchissement plus intense, des pertes plus risquées dues aux dérives de tensions … (si on met 3 états : 0V - Vcc/2 et Vcc ça devient compliqué de garder Vcc/2 sans que ça dérive vers 0V ou +Vcc)

L_d_v_c@ a écrit :
... Y'a plus qu'à trouver un algorithme qui fasse tomber une décimale à chaque cycle d'horloge ...
Me trompe-je si j'interprète "chaque cycle d'horloge" comme "chaque itération" ?

Non, trop mauvais algorithme si les décimales tombent à chaque itérations … L'exemple calculé dans mon premier message est qu'une décimale représente 57762 cycles d'horloge (ou 57762 cycles temps machine).
(approximation entre le nombre de décimales, le temps du calcul, et la fréquence du processeur).

Il existe un algorithme qui calcule plusieurs décimales par itération que j'ai programmé sur ma calculatrice scientifique CASIO 7000GA (ou GC) vers 1992 et sortait un millier de décimales à l'écran sans forcer. (sortie écran car il n'y avait que 422 pas de mémoire maximum pour les programmes, et l'extension des mémoires algébrique monopolisait trop de pas de programmation.).

Cet algorithme existe et est appelé L'algorithme compte-gouttes
Maintenant, sauf erreur de ma part, l'algorithme utilisé dans Super Pi est l'algorithme de Gauss-Legendre qui est beaucoup plus efficace car produit 2 fois plus de décimales exactes à chaque itération ;-)

Je plaisantais à moitié en disant une décimale par cycle d'horloge , ça irait donc 57762 fois plus vite

Si je retrouve l'algorithme super-simple qui rendait plusieurs décimales justes par itération, alors je le posterai
Son énorme avantage : ne travaille que sur les dernières décimales trouvées, pas besoin d'accéder au 3,141592656 si on en est à la millième décimale. Ça veut aussi dire que cet algorithme super simple pourrait largement tourner dans le cache du processeur, en calculant au format BCD (4 Bits = 1 BCD Digit) permettant de manier les nombres de 00 à 99 par octet, directement compréhensible par le processeur et évitant des conversions binaire-décimales … si on veut un gain en vitesse, ou alors en implantant la conversion 10 octets ←→ 24 chiffres vues plus haut pour un gain en capacité.

Il faudrait lancer un test.

Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 1: Basic Architecture - page 112 sur 500 a écrit :

When operating on BCD integers in x87 FPU data registers, BCD values are packed in
an 80-bit format and referred to as decimal integers. In this format, the first 9 bytes
hold 18 BCD digits, 2 digits per byte. The least-significant digit is contained in the
lower half-byte of byte 0 and the most-significant digit is contained in the upper half-
byte of byte 9. The most significant bit of byte 10 contains the sign bit (0 = positive
and 1 = negative; bits 0 through 6 of byte 10 are don’t care bits). Negative decimal
integers are not stored in two's complement form; they are distinguished from posi-
tive decimal integers only by the sign bit. The range of decimal integers that can be
encoded in this format is –10¹⁸ + 1 to 10¹⁸ – 1.

Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 1: Basic Architecture - page 135 sur 500 a écrit :

5.1.3
Decimal Arithmetic Instructions
The decimal arithmetic instructions perform decimal arithmetic on binary coded
decimal (BCD) data.
DAA Decimal adjust after addition
DAS Decimal adjust after subtraction
AAA ASCII adjust after addition
AAS ASCII adjust after subtraction
AAM ASCII adjust after multiplication
AAD ASCII adjust before division

Et là je me rends compte qu'ils avaient déjà pensé à mettre le BCD sur 80 bits puisque le processeur x86_64 gère nativement ce mode, et permet en plus le codage des relatifs MAIS ils ne codent que 18 chiffres au lieu de 24 chiffres avec 10 octets (80 bits) en travaillant les bits par 10 pour 3 chiffres décimaux.

PS : je trouve que Pi en binaire n'est pas marrant, c'est pourquoi j'aime bien la base décimale …

Dernière modification par Compte supprimé (Le 01/06/2015, à 15:41)

claudius01 · Le 01/06/2015, à 17:11

En attendant de lire l'ensemble dans le détail:

L_d_v_c@ a écrit :

Si je retrouve l'algorithme super-simple qui rendait plusieurs décimales justes par itération, alors je le posterai ;-)
Son énorme avantage : ne travaille que sur les dernières décimales trouvées, pas besoin d'accéder au 3,141592656 si on en est à la millième décimale.

Cet algorithme existe: cf. Formule BBP qui ne fonctionne pas en base 10.
De plus, à ce jour; je cite: "Actuellement, aucune formule réellement efficace n'a été découverte pour calculer le n-ième chiffre de π en base 10."

Compte supprimé · Le 03/06/2015, à 10:34

claudius01 a écrit :

En attendant de lire l'ensemble dans le détail:
L_d_v_c@ a écrit :
Si je retrouve l'algorithme super-simple qui rendait plusieurs décimales justes par itération, alors je le posterai ;-)
Son énorme avantage : ne travaille que sur les dernières décimales trouvées, pas besoin d'accéder au 3,141592656 si on en est à la millième décimale.
Cet algorithme existe: cf. Formule BBP qui ne fonctionne pas en base 10.
De plus, à ce jour; je cite: "Actuellement, aucune formule réellement efficace n'a été découverte pour calculer le n-ième chiffre de π en base 10."

Pas mal …
Je précise un algorithme en base décimale, qui est super-rapide puisqu'il me semble qu'il faisait tomber plusieurs décimales à la fois à chaque itération, et je précise de mémoire (qu'il me semble) que l'algorithme ne se sert que de quelques compteurs et du paquet de décimales trouvées précédemment pour calculer les suivantes, sans accéder constamment à toutes les décimales précédentes.

Par exemple, l'évolution était (ou aurait pu être, car les variables de la calculatrice ne devait pas déborder de la capacité, je ne sais plus entre 12 et 15 chiffres significatifs je crois pour les CASIO) :
3.
1415926535
8979323846
2643383279
5028841971
6939937510
5820974944
5923078164
0628620899
8628034825 (plus quelques compteurs permettaient de trouver la ligne suivante)
3421170679

Il y a donc toujours besoin de calculer les premières décimales, mais pas besoin de toutes les stocker pour calculer les décimales suivantes (on peut les stocker, ou les afficher à l'écran et passer à la suite), seules le paquet de décimales précédentes et les compteurs à jour sont nécessaires pour le calcul de l'itération en cours.

Aitken sa formidable formule d'accélération de la convergence, le Delta2 ? [Je ne sais plus où ai-je connu le nom d'Aitken … à l'université en analyse numérique, ou à la fin du collège dans l'article de science et vie (ou encore dans le CPC magazine) qui publiait l'article avec l'algorithme où il était question justement de notion d'accélération de la convergence il me semble (puisqu'une itération fournissait plusieurs décimales justes)].
Mais j'ai essayé tellement d'algorithmes différents que pour l'instant c'est encore vague.
édit : Ce n'était pas Aitken pour le calcul de Pi qui m'intéresse. Je viens de vérifier dans ma bibliothèque, la méthode d'optimisation d'Aitken apparaît bien dans mes cours d'analyse numérique au chapitre "interpolation" par les polynômes de Lagrange, avec l'algorithme de Aitken.

Et l'algorithme de calcule du nombre Pi se faisait formellement : on affiche les décimales calculées à l'itération en cours, et on n'y revient plus, on les garde juste pour l'itération suivante et la boucle continue.

Dernière modification par Compte supprimé (Le 03/06/2015, à 10:51)

claudius01 · Le 03/06/2015, à 17:29

L_d_v_c@ a écrit :

Je précise un algorithme en base décimale, qui est super-rapide puisqu'il me semble qu'il faisait tomber plusieurs décimales à la fois à chaque itération, et je précise de mémoire (qu'il me semble) que l'algorithme ne se sert que de quelques compteurs et du paquet de décimales trouvées précédemment pour calculer les suivantes, sans accéder constamment à toutes les décimales précédentes.

Ne serait-ce pas ce tout petit programme écrit en Langage C de 133 caractères, dont l'auteur ne s'est jamais déclaré et qui a été un certain temps inexpliqué: 15000 décimales de Pi en 133 octets de C
et totalement expliqué ici: Comment calculer les 2400 premières décimales de Pi

Compte supprimé · Le 03/06/2015, à 18:20

claudius01 a écrit :

L_d_v_c@ a écrit :
Je précise un algorithme en base décimale, qui est super-rapide puisqu'il me semble qu'il faisait tomber plusieurs décimales à la fois à chaque itération, et je précise de mémoire (qu'il me semble) que l'algorithme ne se sert que de quelques compteurs et du paquet de décimales trouvées précédemment pour calculer les suivantes, sans accéder constamment à toutes les décimales précédentes.
Ne serait-ce pas ce tout petit programme écrit en Langage C de 133 caractères, dont l'auteur ne s'est jamais déclaré et qui a été un certain temps inexpliqué: 15000 décimales de Pi en 133 octets de C
et totalement expliqué ici: Comment calculer les 2400 premières décimales de Pi

Merci claudius01 pour ta recherche.

À l'époque j'ai traduit l'algorithme du magazine que j'avais lu et que je recherche vers la calculatrice CASIO FX 7000 G? (donc pas encore de langage C - à l'époque j'étais avec le CPC 6128 sous BASIC, et je n'ai fait tourner cet algorithme que sur la calculatrice FX 7000 G?, et plus tard FX 7700 G? …

L’algorithme de Spigot que tu cites (qu'on devine à partir du programme C)

#include <stdio.h>
int a[52514],b,c=52514,d,e,f=1e4,g,h;main()
{for(;b=c-=14;h=printf("%04d",e+d/f)) for(e=d%=f;g=--b*2;d/=g)
d=d*b+f*(h?a[b]:f/5),a[b]=d%--g;}

ne me dit rien au niveau de l'initialisation des variables, donc je ne sais pas. En plus l'algorithme de Spigot semble dater de 1995, dans ce cas ce n'est pas possible que ce soit celui-là je pense … (sans certitude), plutôt 1991~1993.

En plus le coup des deux boucles et des trois divisions ne me rappellent strictement rien.

Dernière modification par Compte supprimé (Le 03/06/2015, à 18:23)

Ubuntu-fr

Navigation

Liens de recherche

Annonce

#1 Le 01/06/2015, à 03:46