Puissance et modulo

Bonjour,

Je cherche à calculer le modulo d'une puissance. Je me heurte au problème du type avec la fonction pow().

J'ai beau cherché, mon niveau ne m'a pas permis jusque là à me sortir d'affaire.

Quelqu'un saurait comment faire ce type d'opération :

long C = pow(x,y) % n ?

où x, y et n sont des entiers.

Merci beaucoup pour votre aide !

Code:

---

long C = lrint(pow((double)x,(double)y)) % n;

---

désolé mais la fonction lrint est uniquement acceptée/définie dans C99..

En C non-C99 (un programme C portable n'incluera pas des fonctions spécifiques C99), on peut se servir de la fonction modf :

http://man.developpez.com/man3/modf.3.php

http://www.linux-kheops.com/doc/man/...n3/modf.3.html

et après en tirer le modulo par %

ou bien directement faire

Code:

---

1 2	C = (long)(round(x)) % n

---

ou si x dépasse les capacités d'un long, faire

Code:

---

1 2 3 4 5 6 7

double d=1.0 ; long C ;   while ( (d*n) < x ) d = d + 1.0 ;   C = (d*n - x);

---

Citation:

---

Envoyé par souviron34

désolé mais la fonction lrint est uniquement acceptée/définie dans C99..
un programme C portable n'incluera pas des fonctions spécifiques C99.

---

La norme C99 comme son nom l'indique date de 1999, on est en 2007 faut arrêter maintenant avec ça et se mettre à la page. C'est une ironie de dire qu'un programme qui respecte la norme n'est pas portable...

Citation:

---

Envoyé par nicolas.sitbon

La norme C99 comme son nom l'indique date de 1999, on est en 2007 faut arrêter maintenant avec ça et se mettre à la page. C'est une ironie de dire qu'un programme qui respecte la norme n'est pas portable...

---

Ouais mais bon gcc ne respecte pas encore entièrement la norme C99 donc on a beau être en 2007 si ton compilateur ne supporte pas entièrement cette norme autant rester avec la norme de 89 qui elle est supportée par gcc (entre autres).

Ne vous battez pas pour moi :P

J'essairai ce soir. Quelle est la solution la plus recommandable ?

Citation:

---

Envoyé par nicolas.sitbon

La norme C99 comme son nom l'indique date de 1999, on est en 2007 faut arrêter maintenant avec ça et se mettre à la page. C'est une ironie de dire qu'un programme qui respecte la norme n'est pas portable...

---

C'est ironique mais c'est une realite. Peu de compilateurs implementent C99 en entier (Comeau est sans doute le plus complet). gcc supporte la majeure partie des nouveautes, mais d'autres ont le statut "broken", ce qui n'est pas tres rassurant. Borland et Microsoft ont choisi de ne pas implementer C99 et mettent l'accent sur le C++.
S'il existe une solution C90 equivalente, il est donc preferable de ne pas utiliser C99.

Pour moi ça n'est pas logique, mon compilateur implémente C99, dans les autres langages, quand une nouvelle version apparaît les gens ne mettent pas 20 ans pour s'y mettrent, le C a déjà assez mauvaise réputation comme ça, on dis que c'est un langage dépassé, on pourrait prétexté que la dernière révision date de 2005 mais vous vous bloquez sur 1989, et toutes les améliorations et nouvelles fonctionnalités passent aux oubliettes...

Citation:

---

Envoyé par nicolas.sitbon

Pour moi ça n'est pas logique, mon compilateur implémente C99, dans les autres langages, quand une nouvelle version apparaît les gens ne mettent pas 20 ans pour s'y mettrent, le C a déjà assez mauvaise réputation comme ça, on dis que c'est un langage dépassé, on pourrait prétexté que la dernière révision date de 2005 mais vous vous bloquez sur 1989, et toutes les améliorations et nouvelles fonctionnalités passent aux oubliettes...

---

Remarque que je n'ai pas dit qu'il ne fallait utiliser C99. J'ai ecrit "S'il existe une solution C90 equivalente, il est donc preferable de ne pas utiliser C99." Cela permet de se reposer sur une base large de compilateurs C90, complets et robustes. Evidemment, on fait se qu'on veut, du moment que le code est clairement documente comme necessitant C99.
Apres, que des gens disent que le C est un langage depasse, ca les regarde... Il m'arrive souvent de coder en Fortran 77 et, ma foi, il fait le boulot !

Sinon histoire de me la peter en resortant mes cours de term ^^ je passe juste rappeller que le modulo de la puissance est ... le modulo de la puissance du modulo ... c'est pas completement HS

Citation:

---

Envoyé par nicolas.sitbon

Pour moi ça n'est pas logique, mon compilateur implémente C99

---

De quel compilateur s'agit-il? Thierry

Citation:

---

Envoyé par Thierry Chappuis

De quel compilateur s'agit-il? Thierry

---

bonjour Thierry, il s'agit de sunstudio 12.
Cordialement.

Juste pour ma petite methode , le resultat est periodique d'une periodicité inferieur ou egale au diviseur ...

Je crois que la méthode évoquée par GuJman permet de calculer en entier, en un nombre raisonnable d'opérations avec un résultat exact. Le passage à des flottants par pow peut donner lieu à des erreurs de calculs difficiles à maîtriser.
Exemple :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14

unsigned int kNMod( unsigned int k, unsigned int N, unsigned int mod) { // (k^N)mod(mod) unsigned int resultat = 1; if(mod == 0 || k==0) return 0; // par sécurité k = k % mod; while (N != 0) { if (N & 1) resultat = resultat*k % mod; k = k*k %mod; N = N/2; } return resultat; }

---

Alors pour accelerer encore ta methode diogene tu peut garder le premier resultat du modulo que tu calcules pour racourcir encore tout le travaille !
Perso je ferais comme ca (en repompant largement tes sources ^^)

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19

unsigned int kNMod( unsigned int k, unsigned int N, unsigned int mod) { // (k^N)mod(mod) unsigned int periode = 0; unsigned int Tab[mod-1]; if(mod == 0 || k==0) return 0; // par sécurité Tab[Periode++] = k % mod; If (N != 0) { while ((N != 0)&&(Tab[Periode-1]!=Tab[0])&&(Periode!=1)) { k=Tab[Periode] Tab[Periode++] = k % mod; N--; } N = (N % --Periode)-1; } return Tab[N]; }

---

Voila c'est plus optimisé ^^

Je ne sais pas si

Code:

---

1 2	k=Tab[Periode] Tab[Periode++] = k % mod;

---

est equivalent à

Code:

---

Tab[Periode++] = Tab[Periode] % mod;

---

N'étant pas très très à l'aise avec le C, quelle solution selon votre expertise, est la meilleure pour mon problème ?

Merci en tout cas pour vos contributions !

Je ne comprend pas le code proposé.

Par ailleurs pour lrint ça ne compile pas :

incompatible implicit declaration of built-in function «lrint"

Code:

---

1 2 3 4 5

#include <stdio.h> #include <math.h> #include <stdlib.h> ... long C = lrint(pow((double)M,(double)e)) % n;

---

Ca ne me paraît pas incorrect...

Cela veut typiquement dire que la fonction lrint n'est pas déclarée (bien que gcc la connaisse comme "built-in").
Il doit y avoir un fichier d'en-tête supplémentaire à inclure...

Citation:

---

Envoyé par Adrien93

Je ne comprend pas le code proposé.

Par ailleurs pour lrint ça ne compile pas :

incompatible implicit declaration of built-in function «lrint"

Code:

---

1 2 3 4 5

#include <stdio.h> #include <math.h> #include <stdlib.h> ... long C = lrint(pow((double)M,(double)e)) % n;

---

Ca ne me paraît pas incorrect...

---

lrint n'a pas de declaration, donc elle est declaree implicitement comme retournant un int. Cela fait un conflit avec la version built-in qui retourne un long comme la version standard.

Le probleme est que math.h ne declare pas lrint, donc c'est soit que tu ne passes pas les bons arguments pour avoir la declaration, soit que tu utilises une bibliotheque qui n'est pas C99.

Hypothese la plus probable: tu utilises la version de gcc qui utilise la bibliotheque de microsoft et dans ce cas il vaut bien abandonner l'idee d'utiliser la bibliotheque c99.

Hmmm, quelle solution s'offre à moi ? J'en perds mes cheveux lol

GuJman #15:
Ce code ne fonctionne pas pour des raisons évidentes :

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

... unsigned int periode = 0; ... Tab[Periode++] = k % mod; // Periode ==1 If (N != 0) { while ((N != 0)&&(Tab[Periode-1]!=Tab[0])&&(Periode!=1)) // donc on n'entre pas dans la boucle { ... } N = (N % --Periode)-1;// et division par 0

---

De plus, il comporte des erreurs de syntaxe .
Il est préférable de tester les codes avant expédition sur le forum.