Factorielle de Linkakro : Ticoncours BasicZ80 Tour2

Je vous présenterai ici ce que j'ai réalisé au Ticoncours BasicZ80 Tour2. Mon cheminement, ce que j'ai achevé, ce qui est fait ou sera fait ensuite.

Je rappelle rapidement le sujet : calculer la factorielle N avec N entier dans [1;135] puis afficher les chiffres, malgré la limitation naturelle de la TI à la factorielle 69. Et pour les incultes, par exemple 4!=4*3*2*1.

######
J'ai choisi de ranger chaque chiffre dans un terme d'une liste de taille suffisamment grande dès le début, et le poids fort est à la fin.
J'ai optimisé les produits avec comme facteur une liste de (n-1)! et un simple nombre n.
Pour les petits nombres, je calcule ou j'affiche directement.
Pour les grands nombres j'initialise avec factorielle 15 qui a 13 chiffres, et profite du fait que le produit par 16 et ses retenues permettent de ranger tout ça comme il faut pour la boucle suivante.
J'affiche dans le graphique les 230 premiers chiffres avec une boucle et le dernier (un zéro si tout va bien) serré contre le précédent. En effet 10 lignes de 23 caractères suffisamment espacés pour rester lisible.
Je fais des retenues une seule fois après chaque produit de la liste par n.

J'ai chronométré dans l'émulateur wabbitemu (84plus virtuelle dont j'ignore la cadence) avec la fonction TI-Basic getTime : 293 secondes soit 4mn53 pour calculer factorielle 135, sans compter le temps d'affichage.

Ceci est la version finale suivant mes objectifs, après correction. Des commentaires montrent des choses de la version tarée que j'ai rendu.

Code:

{1->L1
232->dim(L1 // j'ai rendu avec 234 pour supporter des tentatives de retenue
Prompt N
If N<14
Then
Disp N! // 10 chiffres, facile
Else
If N<17 // 14 chiffres, décompose
Then
N!E-7
Disp iPart(Ans
Disp E7fPart(Ans
Else // plus de chiffres
15!->L1(1 // init
13->Q
For(D,16,N
DL1->L1 // produit
1+(D>99)+(D>9)->R  // ceci n'était pas ici dans ce que j'ai rendu // ceci compte les chiffres de D
For(A,1,Q+R // retenue // le Q+R peut être remplacé par Q+R-1
L1(A->K
If K>9 // ce test est facultatif donc peut être enlevé, car la nouvelle condition
Then
10fPart(K.1->L1(A
L1(A+1)+iPart(K.1->L1(A+1
End
End

// ce que j'ai rendu
// 1+(D>99)+(D>9->R // mal placé, aurait dû être avant le For, c'est la cause des problèmes
// min(231,Q+R->Q // le palliatif

Q+R-not(L1(Q+R->Q // ce que j'avais toujours voulu, n'était pas comme ça dans ce que j'ai rendu

End
FnOff
AxesOff // ici j'avais un espace de trop, erreur syntaxe
ClrDraw
For(K,0,9
For(A,1,23
A+K23
If Ans<=Q
Text(6K,4A-4,L1(Q+1-Ans
End
End
If Q=231
Text(54,91,L1(1
   // si le calcul de Q est juste (ce qui n'était pas le cas dans mon rendu) on peut juste afficher 0
End
End
DelVar ADelVar DDelVar KDelVar QDelVar RDelVar NClrList L1 // ici j'avais un DelVar_B inutile

232 permet de supporter les conditions de compte de chiffres Q+R-not(L1(Q+R->Q, voire même une tentative de retenue si la boucle de retenue s'arrête à Q+R

Le palliatif avec la fonction min(231,Q+R)->Q surestime le nombre de chiffres, plutôt que de le sous-estimer comme ce que je semblais avoir au moment de rendre le programme.

J'ai réfuté l'optimisation de calcul de plusieurs chiffres par case pour faciliter l'affichage graphique et éviter d'hypothétiques problèmes (possibles jusqu'à preuve du contraire) de retenues qui dépasseraient la capacité.
Mais cela a probablement permis des gains de temps importants à d'autres participants.

######
Voici mon développement.

Je sépare les petits nombres de ceux qui ont besoin d'une liste, j'ai donc 3 cas. Je traite ci-après des nombres listes.

D'abord il faut décomposer les nombres et chaque multiplication.
Le nombre maximal est 135!~~2.69*10^230 soit 231 chiffres que je peux aisément ranger dans une liste.

Je me demande déjà le nombre de chiffre auquel m'attendre à chaque produit, pour pouvoir contrôler les boucles et gagner en efficacité.
S'il y a un nombre de Q chiffres et un de R chiffres, alors le résultat sans retenue a toujours Q+R-1 chiffres. Avec retenue il peut y avoir tantôt Q+R chiffres tantôt Q+R-1 chiffres.
Je vous épargne une démonstration, notez juste que les retenues de chaque produit ne peuvent amener qu'un seul chiffre supplémentaire.

Je pourrais rassembler plusieurs chiffres par case, mais c'est dangereux pour une future routine d'affichage, car des zéros peuvent être invisibles, et le compte des chiffres/cases est plus compliqué.

Et comme le TI-Basic est très lent pour redimensionner des listes, j'affecte la taille 231 dès le début.
Heureusement je n'ai pas effectué d'insertion de donnée telle que augment({0},L1) car la dimension 231 fixe aurait été défavorable.

J'ai commencé par étudier le problème de façon générale avec deux boucles et deux listes.
Voici une boucle générale utile pour les polynômes (pas de retenues).

Code:

{1,2,3->L1 //ou bien {3,2,1->L1
{1,2->L2 // ou bien {2,1->L2
{0->L3
dim(L1->Q
dim(L2->R
Q+R-1->dim(L3 // ici je sais qu'il n'y aura pas de retenue
For(A,1,Q
For(B,1,R
L3(A+B-1)+L1(A)*L2(B->L3(A+B-1
End
End
// L3={1,4,7,6} ou L3={6,7,4,1}
// 123*12=1476 et 321*21=6741

Lorsqu'il y aura des retenues, ce code sera directement adapté au sens d'écriture du poids faible vers le poids fort : 123={3,2,1}

Selon la convention d'écriture des nombres dans les listes, cela amène des incompatibilités entre entre les besoins de mémoire pour les termes de retenues et les adresses des termes dans les listes.
Cependant cela n'aura plus d'importance quand je multiplierai un simple nombre à une liste, donc cette boucle générale, ses variantes et les problèmes seront omis.
Pour résumer ces ennuis :
-il est facile de faire un produit quand les données sont au début, c'est pénible sinon (des décalages, changement de variables...)
-il est facile même si c'est un peu lent de réserver de la mémoire supplémentaire à la fin d'une liste, pour des retenues notamment (affecter la dimension)
-il est pénible et lent de réserver de la mémoire au début, surtout si la liste a été prévu à l'avance à une certaine taille

A ce stade, quand je n'avais pas envisagé le produit liste*nombre, j'ai choisi de mettre le poids fort à la fin et de caler le poids faible le plus au début, pour éviter tous les problèmes.

On ajoute une boucle de retenue soit dans la boucle de produit après chaque produit terme à terme, soit à la fin après la boucle de produit.
Placer la boucle de retenue dedans permet de ne pas parcourir des cases qui ne sont pas concernées après un produit de termes donné. Ou plutôt on a intérêt à restreindre pour gagner du temps chaque fois.
Placer la boucle à la fin est rapide car cela permet de parcourir chaque terme une seule fois, mais on ne sait pas à l'avance si c'est utile pour tous. Cela est par ailleurs selon moi un danger de dépassement de capacité, mais dans le cas présent l'expérience montre que tout va bien.

Ici la retenue sur l'ensemble de la liste et avec poids fort à la fin.

Code:

For(A,1,Q+R-1
L3(A->K
If K>9 // ce test est facultatif
Then
10fPart(K.1->L3(A
L3(A+1)+iPart(K.1->L3(A+1
End
End

On peut changer A+1 en A-1 ou For(A,1,Q+R-1) en For(A,Q+R-1,1,-1) et cela change les conventions de sens d'écriture, mais il faudra penser à d'autres changements de variable si on serre tout à la fin de la liste, ce qui est possible.

Maintenant on envisage de multiplier un nombre D avec une liste puis d'effectuer des retenues.
Déjà ça se résume à D*L1->L1 suivi des retenues.
Avec N<135, j'ai au plus 4 chiffres par terme dans D*L1. La capacité est loin et donc ça me rassure. Cependant je n'ai pas trouvé de preuve que les retenues ne causeront pas un dépassement.

Voici un code obtenu. Le poids fort à la fin, et les retenues laissées à la fin après les produits. Si on écrivais dans l'autre sens, il faudrait complémenter les adresses à la taille+1, par exemple 233-(Q+R) pour le terme de retenue supplémentaire.

Code:

{3,2,1,0,0,0->L1
12->D
dim(L1->Q
1+(D>9)+(D>99->R // nombre de chiffres
DL1->D
For(A,1,Q+R-1
L1(A->K
If K>9 // ce test est facultatif, mais évite de passer du temps sur le calcul s'il est inutile
Then
10fPart(K.1->L1(A // fPart c'est souvent dangereux mais avec 10 ça marche toujours
L1(A+1)+iPart(K.1->L1(A+1
End
End
Q+R-not(L1(Q+R->Q // nouveau nombre de chiffres

Le nouveau nombre de chiffres est soit la somme soit la somme moins 1 selon la présence d'un chiffre de retenue.
Connaitre le nombre de chiffres permet
1-de n'effectuer de retenue que sur les chiffres concernés donc de gagner du temps sur des nombres moyens
2-de gagner en lisibilité des moyens nombres en omettant des zéros inutiles au poids fort.
3-si j'avais écris un produit liste*nombre avec une boucle, de diminuer la durée de la boucle, mais je gagne un temps précieux sur les grands nombres.

Maintenant pour afficher :
1-je n'ai pas envie de retourner la liste pour ensuite afficher cette liste.
2-je veux utiliser le graphique pour que la consultation de jusqu'à 231 chiffres soit ergonomique, je peux remettre dans le bon sens au même moment.

Regardez le programme final basé sur le rendu pour voir la boucle de graphique.

######

Voici des pistes pour aller plus loin. J'en ai envisagé certaines, mais d'autres viennent du forum.

Serrer les chiffres pour gagner en largeur graphique.
C'est facile quand on affiche un par un chaque caractère.

Ranger plusieurs chiffres par terme.
C'est dangereux pour la capacité et mon affichage graphique est très pénible : je dois extraire chaque chiffre pour respecter les zéros de poids forts et afficher les fins des termes qui dépassent des lignes. 23 est un nombre premier donc ça dépassera toujours.
En revanche le calcul devient extrêmement performant puisque la plupart des retenues des produits ainsi que les développements sont gérés par le système d'exploitation.

-> Je l'ai tenté après le concours et je ne suis pas satisfait. J'ai abandonné le compte précis des chiffres car c'est très pénible, soit j'ai des divisions soit j'ai deux variables. L'affichage de chaque chiffre fonctionne en revanche et fort heureusement.

Code:

15!->L(1
5->Q
For(D,16,N
DL1->L1
For(A,1,Q+1
L(A->K
If K>=1000
Then
.001fPart(K.001->L1(A
L(A+1)+iPart(K.001->L1(A+1
End
End
min(77,Q+1->Q
End
 // 77*3=231
77->D
0->K
0->R
3->Q
For(A,1,230
Text(6K,4(R+3-Q),int(10fPart(L1(D)10^(-Q
Q-1->Q
If not(Q
Then
3->Q
R+3->R
D-1->D
End
If R+3-Q=23
Then
R-23->R
K+1->K
End
Pause
End
Text(54,91,10fPart(.1L(1
End
End

afficher directement la liste.
Si on veut enlever des zéros inutiles au début ou remettre dans le bon sens, il faut de simples boucles.
Retirer des termes est facile sur la fin sans boucle, mais ensuite remettre dans le bon sens demande une suite()/seq() ou une boucle donc il vaut mieux tout faire d'un coup avec la boucle ou la suite.

Je signale que remplacer des boucles de retenue ou de décalage par des fonctions seq/suite demande des actions supplémentaires telles que des concaténations, ou même des permutations.

J'ai lu quelque part sur le forum ou le tchat, quelqu'un a, je ne sais plus qui, stocké chaque terme avec un exposant 0, pour ne pas avoir besoin de diviser avant les deux fonctions de retenue. C'est une excellente idée je dois l'admettre. Cependant cela ajoute une division juste après la partie entière. Et pour faire joli à la fin, on multiplie tout.
Exemple dans le cas de ma boucle de retenue.

Code:

{.123,.456,0->L1
L1*3->L1
For(A,1,2
L1(A->K
If K>=1
Then
fPart(K->L1(A
L1(A+1)+.001iPart(K->L1(A+1
End
End
L1*1000

J'ai aussi envisagé de réduire le nombre de boucles nécessaires à effectuer l'ensemble des produits, en multipliant la liste de (n-2)! avec n*(n-1) au lieu de multiplier une fois par (n-1) et une fois par n.
Et idem avec des paquets de 3,4,...
Vérifions que le cas le plus défavorable ne dépasse pas la capacité.
135*134=18 090 (5 chiffres)
135*134*133 = 2 405 970
J'envisage d'avoir 6 chiffres par terme et de multiplier par des paires de coefficients (au plus 5 chiffres) pour ne pas excéder 5+6=11 chiffres.
Il est intéressant d'initialiser selon la parité de N et de multiplier ensuite systématiquement la liste par D*(D+1).

Code:

14->D
If fPart(N/2
13->D
D!->L1(1
For(D,D+1,N-1,2
D*(D+1)*L1->L1
//...
End

Je m'assure aussi que 14!*15*16=16! et 13!*14*15=15! qui sont générés dans un seul terme par mon initialisation imprudente ont moins de 14 chiffres.

Nombreux sont ceux qui ont tenu à compter les zéros de poids faible pour les omettre.
Ce n'est pas mon cas . Bien que j'ai réfléchi rapidement je n'ai pas envisagé d'économiser de la place avec ça. Je pense que je me contenterais bien de placer une condition dans la borne inférieure des boucles de produit et retenue.
>>>
Chaque fois qu'on multiplie par 2 et par 5, cela fait un zéro supplémentaire. Comme les multiples de puissances de 2 sont nettement plus nombreux que ceux de puissances de 5, il suffit d'analyser les multiples de puissances de 5. En remarquant que 25=5^2 et 125=5^3 on peut deviner le nombre de zéros d'une factorielle en regardant la précédente.

Code:

1->F
0->Z
For(D,2,N
FD->F
 // Z+not(fPart(D/5))+not(fPart(D/25))+(D=125->Z // nombre de zéros, formule 1
Disp int(D/5)+int(D/25)+int(D/125 // nombre de zéros, formule 2
End

######

J'espère avec tout ça que les uns me comprendront et que les autres progresseront.
Et puis cela me permet de garder une trace plus propre que mes propres dossiers.  
Salut.

Très beau raisonnement !