Bonjour,

http://pastebin.com/HTRFrz8C

j'ai essayé de calculer la factorielle de grand nombre comme 99999
Quelqu'un saurait m'expliquer (ou me donner un site où c'est expliqué)
Comment fait Haskell pour gérer des nombres aussi gigantesques instantanément ?

je n'ai pas trouvé d'explications à ce sujet sur le net

fact 99999 ici : https://wall.deblan.org/x1be8/html/1/
qui a été calculé quasiment instantanément, je ne sais pas si ce nombre correspond bien à 99999!

par contre le résultat sorti de 5! et autre factoriel vérifiable sont corrects

le resultat sortie est d'environ 456570 chiffres, comment gère t-il des nombres aussi grand ? il utilise des tableau de chiffres ? Mais dans ces cas là, pour multiplier 2 nombres representer par des tableaux de variable entières, comment fait-il pour les multiplier ? En posant la multiplication comme on la pose en primaire ? Mais ça m'étonnerait beaucoup sinon ce serait pas aussi rapide j'imagine, si?

à part ça je ne vois pas du tout comment ces nombres pourraient être representé, pour le resultat final de l'ordre de 10^456570, je ne pense pas que ce soit representable comme une simple variable de type primitif comme un simple integer, sinon ça voudrait dire que pour le representer en mémoire il faudrait environ lb(10)*456570 bits soit quasiment 189kB pour le résultat final, non? Puis sans compter les 99990 autres big nombres nécessaires à la multiplication qui ont un ordre de grandeur allant de 10 à 10^456570, ça me parait quand même assez colossale, d'où mon incompréhension face au resultat quasi instantanné

si j'ai bien compris, Haskell est qualifié de paresseux car il calcule seulement ce dont il a besoin et que même si on lui demande de calculer quelque chose il ne le calculera pas s'il en a pas besoin dans l'immediat pour afficher ce qu'on lui demande
mais dans le cas de la factorielle, il y a bien à un moment donné où il devra faire de la multiplication de grand grand nombre pour arriver au résultat final

merci pour vos futures réponses/explications/liens

Salut,

Niveau stockage des grands nombres, c'est la même chose que dans tous les langages qui les gèrent de façon transparente (la plupart des langages haut-niveau, donc) : une classe/un type véhiculant l'idée de BigInt est créé et l'Int, lorsqu'il dépasse les bornes possibles, est converti en ce type. Le stockage des données va différer selon les implémentations (souvent vecteurs, listes ou tableaux), mais globalement les calculs sont gérés par des opérations bits à bits ou digit par digit, avec des systèmes de retenue.

En Haskell, la coercition Int -> Integer (le "bigint") est faite automatiquement quand le nombre a besoin de plus de 32 bits (peut varier selon l'implémentation), donc c'est totalement transparent pour l'utilisateur.
Tu peux forcer le type ( foo = 1 :: Integer ) si tu veux, mais je présume que le compilateur optimisera ça si t'as pas besoin d'un nombre arbitrairement long.

DenshaOtoko,
ca n'est que DenshaOtoko 99999 multiplication sur un nombre de moins de 189kB. (sachant que la taille grandit concretement de facon lineaire.) Ca fait donc moins de 186*1024/8*2 operation floatante soit 4G operation flotante double precision. Je ne sais pas quel machine tu utilise, mais 4GFlop double precision, c'est pas beaucoup. Un seul core de ton processeur peut certainement faire plus de 16Gflop par secondes.

Caletlog donc un très grand nombre n (superieur à 10^10) sera utilisé en interne sous forme de vecteurs (ou listes ou tableaux) de ceil(log_10(n)) cases avec un chiffre du nombre dans chaque case du vecteurs, c'est ça ?

et du coup lorsqu'on veut multiplier 2 nombres representé de cette manière, ça pose la multiplication comme quand on la pose en primaire avec les retenues ? (ou ça utilise l'algo de karatsuba?)

si on veut multiplier 2 nombres de même taille par exemple, n et m
on veut p = n*m

n et m seront representé sur ceil(log_10(n)) cases, et p sur ceil(log_10(n*m)) cases si j'ai bien compris

du coup pour multiplier ces 2 nombres on aura ceil(log_10(n))^2 operations sans prendre en compte les operations nécessaires à la gestion des retenues
pour 99999 en entrée ça fait du coup 456570^2 multiplications seulement pour le dernier appel recursif 99999*99998!

"la coercition Int -> Integer (le "bigint") " Int -> Integral ou Int -> Integer ?

le "bigint" c'est le type "Integral" non?

et sinon ok je vois, dans ma fonction de toute façon j'ai directement donné le type Integral à mon entrée et ma sortie

godrik "Ca fait donc moins de 186*1024/8*2" il represente quoi le "/8*2" ?

merci pous vos réponses

je pense que je vais essayer de faire un petit programme minimaliste gerant des bigint avec les operations de bases histoire de mieux me visualiser tout ça

Le dernier nombre prends "186*1024" octet. Mais tu stocke tres certainement tes nombre avec un type primaire 64-bit donc "186*1024/8" entier 64-bit. pour faire une multiplication par un nombre qui tient dans un entier 64 bit, tu as probablement besoin d'une multiplication et d'une addition par entier 64-bit. Donc "186*1024/8*2" operations pour une seul multiplication. Tu fais au total 99999 multiplications comme ca, donc "99999*186*1024/8*2"=4.7Gflop.
Sachant qu'en vrai, ici je compte que les multiplications se font toutes sur un nombre de taille 186KB. Mais certainement je compte un facteur 2 de trop (la somme des n premiers entiers et en gros n*n/2). Donc certainement il n'y a que 2.35Glop a effectue.

Si tu prends un core d'un processeur moderne a 2Ghz, ca a des vecteur de 128-bits = 4 entier 64-bit (ca a au moins du SSE4, si c'est un processeur plus recent comme un haswell, ca fait du AVX2 et ca peut traiter des entier avec des registres de 256 bit. Mais c'est vraiment tres recent, tu n'as probablement pas ca.). Et ca peut faire une multiplication et un addition a chaque cycle soit 2Gcycles/s*128-bit/8-bit*2operations=16Gflop/s

Et je viens de me rendre compte que c'est tout des operations entieres, donc c'est des iop/s et pas des flop/s.

En effet. C'est relativement etrange. La multiplication peut etre effectue en parallel. Mais peut etre que la gestion du carry empeche d'utiliser ces instructions. Quelqu'un en sait plus?