Calcul de factorielle, avec les chiffres significatifs

Salut, alors voilà mon algorithme, qui effectue bêtement ce qu'on fait à la main quand on calcule une factorielle: il pose les multiplications.

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... )

prgmFACTDG a écrit:

: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

Waw c'est beau! Tu as fait comment la colorationsyntaxique?
Et que-ce que le gettime() vient faire ici?

La coloration syntaxique c'est du HTML tout droit sorti de SourceCoder ou de TI-Editor :



Le getTime me permet juste d'afficher le temps d'exécution du programme à la fin, il ne sert pas à grand chose, oublie le

Voilà ma version:

Spoiler:

EDIT: j'ai caché pour que les éventuelles personnes ne devant pas voir mon code ne le voient pas.

On est pas sensé attendre les résultats en théorie avant de publier ?

Je poste quand même mon code : (EDIT: du coup j'ai fait pareil que Samos)

Spoiler:

Je n'ai pas non plus compris la limite 135! ...

Je posterais bien le mien mais comme il ne fonctionne pas :-(

Samos: Tu peux expliquer comment fonctionne le tient stp? Merci.

Persalteas: Au lieu de passer par un Get_Time tu pourrais passer par un StartTmr. Tu stockes sa valeur avant l'exécution du programme, puis celle après le programme et tu fait une soustraction...Le temps est en seconde, mais ce n'est pas plus mal et tu gagnes quelques octets

m@thieu, tu fais combien en temps pour 135! ?

@Wistaro oui mais de toutes façons je te dis, le programme n'est pas optimisé en octets...

Sur Wabbitemu (vitesse 100%): 28 secondes.
Sur ma calto (mémoire pleine): 56 secondes (le double...).
Je ne sais pas si: Wabbitemu est plus rapide avec la nouvelle version ou si c'est ma calto qui avec sa mémoire pleine et des piles pas pleines qui est plus lente...

@Wistaro
Le mien fonctionne d'une manière très simple et apparemment pas du tout optimisée

Spoiler:

J'aurais eut besoin d'une formule pour connaitre le nombre de chiffres d'une factorielle, j'ai trouvé ceci:
⌊(log(2π)−2n+log(n)∗(1+2n))/(2log(10))⌋+1
ici: http://www.dcode.fr/calcul-factorielle
Mais je ne sais pas à quoi correspondent les ⌊⌋...
Quelqu'un a une idée?

Valeur absolue?...

Merci Samos

Nan c'est pas ça...
Ils auraient mis || de toute façon je pense...

ça correspond à l'arrondi à la valeur inférieure

ouais, la partie entière.

ah oui, et j'ai mis 135 parce que un multiple de 5 ça fait plus classe, en théorie j'aurais pu aller jusqu'à 136, 137.

Nooon, sérieux?...

Bah la formule n'est pas bonne alors...

Ah mais... Tu n'avais pas dis que 135 n'avait pas été choisi au hasard?   

Non, il n'a pas été choisi au hasard. En fait, j'aurais pu aussi choisir 138 ou 139, je m'en rends compte avec le recul.

Moi je pensais que comme 135/2 = 67,5, on pouvait utiliser sa et que sa pouvait nous être utile...

Mais pourquoi 135 138 ou 139? Pourquoi pas par exemple 120 ou 150?

Aucune idée, comme vous

Donc à priori c'est m@thieu qui a le meilleur temps entre nous tous...
Fuu, tu va foncer vers le podium ! je suis jaloux

Ah ça fait plaisir   
je m'y attendais pas au début

Mais bon il reste encore la finale vous allez pouvoir me rattraper même si je vais faire mon possible pour que ça n'arrive pas