Calcul de factorielle, avec les chiffres significatifs

[Persalteas]

Un petit topic post-tour 2 du TI-Concours, voici mon algo...


Je n'ai pas su trouver la méthode plus rapide pour laquelle 135! est une limite.
Mon algorithme ci-dessous est donc plus lent (7 minutes et 8 secondes pour calculer 135!) mais peut calculer jusqu'à 449! (997 chiffres significatifs).


En virant les zéros de fin de liste et en stockant leur nombre dans une variable, on pourrait étendre la portée de l'algorithme jusqu'à la factorielle qui possède 999 chiffres significatifs avant les zéros, ce qui est assez puissant, quand même. (mais que je n'ai pas fait dans le cadre du concours, c'était inutile... )

Code: Select all

:Input N
:getTime→L6
:ClrHome
:Disp "COMPUTING…
:Output(3,1,"*
:abs(iPart(real(N→N
:{1→L1
:For(A,2,N
:   Output(2,1,A
:   Output(4,1,L1
:   AL1→L1
:   A-1
:   dim(L1)-iPart(Ans/5)-iPart(Ans/25
:   For(C,Ans,1,‾1
:      If 9<L1(C:Then
:         If C=1:Then
:            iPart(.1L1(C
:            augment({Ans},L1→L1
:            IS>(C,C:
:         Else
:            L1(C-1)+iPart(.1L1(C→L1(C-1
:         End
:         10fPart(.1L1(C→L1(C
:      End
:   End
:End
:DelVar ADelVar CDelVar NClrHome
:Disp "SPENT TIME:","{H,M,S}",getTime-L6,"=
:L1
:DelVar L1Pause Ans
:ClrHome

Bon, en plus de l'algo de base, j'ai ajouté des petits affichages graphiques pour occuper le correcteur, et un calcul du temps d'exécution.

Le programme permet de récupérer la liste contenant les chiffres du résultat dans Ans.

La ligne "dim(L1)-iPart(Ans/5)-iPart(Ans/25" sert à se passer des zéros en fin de liste, les calculer ne sert à rien, alors autant gagner de la vitesse. Une factorielle prend un zéro tout les 5! (à 5!, 10!, 15! ... etc) et un de plus tous les 25! , d'où cette ligne.


Autre remarque, le programme est optimisé pour la vitesse, pas pour le poids en octets, vous l'aurez remarqué
J'aimerais bien connaitre votre méthode, aussi, svp

[grosged]

Salut ! Je viens de "déchiffrer" ton listing...
Dans la boucle For(A,2,N Je vois qu'àprès la multiplication de L1 par A, tu ajustes L1 pour qu'elle ne contienne que des chiffres (lesquels composent le résultat de A!)
et si on ne faisait cet ajustement qu'une fois les calculs finis ? entre temps on ferait occasionnellement cet ajustement seulement si au moins l'un des termes de L1 risque de dépasser 9999999999
ça pourrait peut-être aller plus vite?
Qu'est-ce que t'en penses?

[Persalteas]

C'est une bonne idée

Cependant, la TI possède 14 chiffres significatifs de précision,donc au lieu d'ajuster L1 dès que les membres de la liste atteignent deux chiffres, j'aurais pu attendre qu'ils atteignent 14 chiffres, et j'aurais gagné beaucoup de temps...

Ensuite, le test à faire pour "si au moins l'un des termes de L1 risque de dépasser 9999999999999" risque lui aussi de prendre du temps si je dois faire une boucle pour tester si le cas se présente...

Du coup, je ne sais pas comment appliquer ça au code. Rajouter une boucle qui teste toute les cases de la liste pour savoir si le nettoyage est nécessaire ?

[grosged]

14 chiffres significatifs de précision, tu dis ? cool ! c'est encore mieux !
(j'ai naïvement pensé 10 , parce qu'à l'affichage d'un nombre>9999999999 , la notation scientifique "E" apparaît)

Pour savoir si au mois l'un des termes risque de dépasser euh ...99 999 999 999 999 , la fonction max(L1 nous donnera le terme le plus grand contenu dans L1 :
avant de multiplier L1 par A,
LBL 1 on vérifie si A x max(L1 est bien < 10^14
si c'est pas le cas , alors il faut d'abord "ajuster" L1 avec comme point de départ L1(x)
contenant le terme max de L1, et dont on ne garde que les unités, car le reste Int(L1(x)/10 est ajouté à L1(x-1)
si L1(x-1) risque aussi un dépassement, alors on continue le même traitement avec L1(x-1 ...etc
enfin, avant de multiplier L1 par A, on vérifie encore si un terme risque encore le dépassement (donc on repart au LBL 1
en bref, cet ajustement occasionnel serait plus rapide que le final (car partiel)
mais bon!... à vérifier car on aurait besoin je pense , de passer par un tri décroissant pour savoir exactement où est situé ce terme max de L1....faut voir si ça resterait toujours plus performant qu'un nettoyage entier de L1...

Désolé si c'est pas très clair, j'essaye d'expliquer au mieux ce qu'il me passe par la tête

[grosged]

Encore une idée !
J'ai pensé à une table de précalculs
Dans la boucle For(A,2,N, il y a successivement 2L1->L1, puis 3L1->L1 ...4L1->L1 ...etc

on peut s'aider d'une table L6 contenant {1,1*2,1*2*3,1*2*3*4,
ainsi, avec x=9, pour calculer par ex x! on fait directement L6(x)L1->L1

avec x>16 ça se complique un peu car il faut gérer/éviter tout dépassement ( 17! >10^14 )
alors, après 16 il faut procéder à un ajustement de L1
puis, maintenant que L1 ne contient que des "unités" (donc val maxi =9)
on sait que le prochain dépassement aura lieu après 9 * 17*18*19*20*21*22*23*24*25
donc à partir de L6(17) on aura
{17,17*18,17*18*19,17*18*19*20,17*18*19*20*21,...,17*18*19*20*21*22*23*24*25
...etc...etc

en gros, pour calculer par ex 24!, on fait L6(16)L1->L1, puis ajustement, puis L6(24)L1->L1 puis ajustement
Il faut mémoriser dans une table ces "paliers" successifs qui éviteront tout dépassement
genre L5 contenant {16,25,33,41 ...etc

Merci de confirmer/infirmer...J'sais plus si j'suis dans le vrai, là ! de la fumée sort de mes oreilles !!!

[Wistaro]

Tu as participé Grosged?
Tu aurais du

[grosged]

mmmmn... j'ai failli !
En fait, les concours comportant plusieurs tours me branchent pas trop

[Wistaro]

Je me suis complètement raté sur cette épreuve.. Mais, c'est le jeu

Ton algo ne risque pas du coup d'être plus long? Le temps d'enregistrer les précalculs?

[grosged]

je suis en train de voir ça, justement ! des précalculs qui sont censés faire gagner du temps....
mais c'est vrai qu'il ne faut pas que leur enregistrement prenne une plombe !!
en fait, le temps de calcul est pris en compte dès que l'on a entré N, c'est bien ça?

edit: j'ai étudié L5 contenant les paliers qui éviteront les dépassements
il suffit des termes {16,25,33,41,48,55,62,69} ajoutés à seq(x,x, 76,136,6 et c'est ok

maintenant je regarde pour L6 combien de temps ça prendrait....

[Persalteas]

Bravo pour l'idée de max(), ça, je suis preneur...

Tu es intelligent !

Je vais sortir une amélioration ce soir, je vais prendre le temps de tester un nouveau code
Merci beaucoup !


Pour la table de précalcul, ça ne me branche pas trop... essaie de voir si tu fais mieux, mais je n'aime pas utiliser des valeurs précalculées, par principe.
Mais c'est vrai que dans un concours de vitesse, ça aurait aussi été une bonne idée.