samedi 6 juin 2020
Prétexte pour construire à la volée une pile LIFO en C.
Dans tout cet article il ne sera question que d'entiers naturels non nuls. Leur ensemble est noté ℕ*. ℕ*={1, 2, 3, 4, ...}
Étant donné un entier naturel non nul $n$, on dit que l'entier naturel $d$ divise $n$ s'il existe un entier naturel $p$ tel que $n=dp$. On dit aussi que $d$ est un diviseur de $n$.
On souhaite écrire l'ensemble $D(n)$ des diviseurs de $n$ ($n\in$ ℕ*). On voudrait de plus que cette écriture soit ordonnée dans l'ordre des naturels.
Exemples :
$D(12) = \{1, 2, 3, 4, 6, 12\}$
$D(25)=\{1, 5, 25\}$
Sachant que tous les diviseurs de $n$ appartiennent à $[1, n]$ on peut tester tous les entiers de cet intervalle, c'est à dire calculer le reste de la division entière de $n$ par chacun d'eux et regarder si elle est nulle. (n \% d == 0 en C).
Cet algorithme donne bien l'ensemble ordonné des diviseurs de $n$ mais au prix de $n$ calculs de restes et autant de comparaisons.
Les diviseurs vont par paires. Exemples :
$$D(12)=\{1, 12\}\cup\{2,6\}\cup\{3,4\}$$
$$D(25)=\{1,25]\cup\{5\}$$
Dans le dernier exemple 5 est appareillé avec lui même.
Faisons une partition de $D(n)$ en :
$$D_1(n)=\{p\in D(n)~|~ p\lt \sqrt{n}\}$$
$$D_2(n)=\{q\in D(n)~|~q\gt \sqrt{n}\}$$
$$D_0=\{m\inD(n)~|~m=\sqrt{n}\}$$ ce dernier pouvant être vide.
Par définition si $p$ divise $n$, alors il existe $q$, tel que $pq=n$.
De plus, si $p\gt\sqrt{n}$ alors $q\lt\sqrt{n}$. (il suffit de multiplier les deux membres de $p\gt \sqrt{n}$ par $\dfrac{q}{\sqrt{n}}$ qui est positif).
Donc, tout élément de $D_2(n)$ peur être obtenu comme quotient de $n$ par un élément de $D_1(n).$
Il devient moins onéreux en termes de calcul de tester tous les entiers $p$ positifs inférieurs à $\sqrt{n}$ et de réserver le quotient $q=\dfrac{n}{p}$ qui est aussi un diviseur de $n$.
On utilise une pile LIFO pour stocker ces autres diviseurs.
Remarque : On évitera d'empiler $\sqrt{n}$ dans le cas où celui-ci est un entier qui divise $n$, afin de ne pas afficher un doublon.
Voici le source du programme divisors.c
/*:w | !gcc % -o .%< -lm:w | !gcc % -o .%< -lm && ./.%<*/#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>// integertypedef unsigned long int ulong;// stack used to store divisors greater than sqrt(n)typedef struct stack {ulong u;struct stack *next;} *stkptr; // stack pointer type/**divisors(u) prints divisors of uu ulong*/void divisors(ulong);/**getulong(&u) reads an unsigned int from stdinu ulongreturns 1 if succes and 0 else*/int getulong(ulong *);int main(){printf("Integer factorization\n");ulong n;while(getulong(&n))divisors(n);puts("End");}void divisors(ulong u){stkptr top = NULL; // stack pointerulong d2; // other divisorulong sqrtu = (ulong)sqrt((double)u);printf("D(%lu) = {", u);for(ulong d1 = 1; d1 <= sqrtu; d1++) { // low divisorsif(u % d1 == 0) {d2 = u / d1; // d1*d2 = uprintf("%lu, ", d1);// push d2if(d2 > d1) {stkptr node = (stkptr )malloc(sizeof(stkptr));node->u = d2;node->next = top;top = node;}}}// pull remaining divisorswhile(top->next != NULL) {printf("%lu, ", top->u);stkptr freed = top;top = top->next;free(freed);}printf("%lu}\n", top->u); // the last must be ufree(top);}int getulong(ulong *u){char *line = NULL;size_t len = 0;int result;printf("unsigned int : ");getline(&line, &len, stdin);result = (sscanf(line, "%lu", u) == 1);free(line);return result;}
Le type ulong peut être adapté, par exemple unsigned long long int.
La structure stack est un nœud de pile LIFO. Chaque nœud pointe sur le suivant, le dernier étant NULL.
stkptr est un pointeur sur une structure stack.
Le programme. Il demande un entier non signé et affiche l'ensemble de ses diviseurs. Le programme s'arrête lorsqu'on ne saisit aucun entier (on tape Enter seul).
La fonction qui recherche et affiche les diviseurs d'un entier. Ici la notation est u, pour ulong et non $n$.
Initialisation de la pile.
Calcul de la racine carrée de u.
Attention : il faut inclure math.h et compiler avec l'option -lm. Voir les lignes 2 et 3. Pour comprendre comment j'utilise ces lignes dans vim voyez mon article vim.
Calcul des diviseurs inférieurs à $\sqrt{u}$. Chaque diviseur d1 est affiché et le quotient de u par d1, s'il est différent de d1 est empilé.
C'est ici qu'on réserve les diviseurs associés. On crée un nouveau nœud node qui contient le diviseur à réserver et qui pointe sur le haut de la pile, puis on le fait devenir le haut de la pile.
Lorsque les calculs précédents sont terminés, on dépile un à un les diviseurs qui ont été empilés en les affichant. On libère alors la mémoire allouée au nœud qui vient d'être dépilé et on abaisse le haut de la pile.
Remarque : la pile n'est jamais vide, elle contient au moins u.
La fonction getulong est la fonction de saisie.
J'ai choisi d'utiliser la fonction getline (voir man 3 getline) qui semble avoir été ajoutée pour ça, d'abord par GNU puis standardisée.
Voir man 3 gets et man 3 fgets.
Voir aussi fgets vs. getline in C et Why is the fgets function deprecated?.
Habituellement j'utilisais fgets et cette fois j'ai voulu essayer getline.
La différence entre l'algorithme naïf et le second peut être significative.
Pour le nombre 1234567890 le premier met 9,478417 secondes, alors que pour le second il ne faut que 0,001199 secondes.
Je pouvais coder la pile de façon plus classique en définissant les fonctions pop et push (fichier joint ulstack.c).
/*:w | !gcc % -o .%< -lm:w | !gcc % -o .%< -lm && ./.%<*/#include <stdio.h>#include <stdlib.h>#include <string.h>#include <limits.h>#include <math.h>typedef unsigned long int ulong;#define Nan ULONG_MAX; // not a numbertypedef struct ulstack {ulong u;struct ulstack *next;} *ulstkptr; // must be initilized to NULL/*ulstk_push(stk, u) push u on the top of the stack *stk*stk is an ulstkptru is an ulongreturns void*/void ulstk_push(ulstkptr *, const ulong);/*ulstk_pop(*stk)*stk is an ulstkptrreturns top value if the stack is not emptyreturns Nan if the stack is empty*/ulong ulstk_pop(ulstkptr *);/**divisors(u) prints divisors of uu ulong*/void divisors(ulong);/**getulong(&u) reads an unsigned int from stdinu ulongreturns 1 if succes and 0 else*/int getulong(ulong *);int main(int argc, char *argv[]){printf("Integer factorization\n");ulong n;while(getulong(&n))divisors(n);puts("End");}void ulstk_push(ulstkptr *top, const ulong u){ulstkptr newtop = (ulstkptr)malloc(sizeof(struct ulstack));if(newtop == NULL) {puts("push failed");exit(1);}newtop->u = u;newtop->next = *top;*top = newtop;}ulong ulstk_pop(ulstkptr *stk){if(*stk == NULL) return Nan; // empty stackulong u = (*stk)->u; // value of the topulstkptr top = *stk; // to be freed*stk = (*stk)->next; // new top pointerfree(top); // free the old topreturn u;}void divisors(ulong u){ulstkptr top = NULL; // stack pointerulong d2; // other divisorulong sqrtu = (ulong)sqrt((double)u);printf("D(%lu) = {", u);for(ulong d1 = 1; d1 <= sqrtu; d1++) { // low divisorsif(u % d1 == 0) {d2 = u / d1; // d1*d2 = uprintf("%lu, ", d1);// push d2if(d1 < d2)ulstk_push(&top, d2);}}// pull remaining divisorswhile(top->next != NULL) {printf("%lu, ", top->u);ulstk_pop(&top);}printf("%lu}\n", top->u); // the last must be ufree(top);}int getulong(ulong *u){char *line = NULL;size_t len = 0;int result;printf("unsigned int : ");getline(&line, &len, stdin);result = (sscanf(line, "%lu", u) == 1);free(line);return result;}
Est-ce bien utile ? On n'utilise ces fonctions qu'une seule fois.