Discussion :

[Adrien93]

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 !

[nicolas.sitbon]

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[souviron34]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[nicolas.sitbon]

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

[Skyounet]

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

[Adrien93]

Ne vous battez pas pour moi

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

[DaZumba]

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.

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

[DaZumba]

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 !

[Gf6HqmTW]

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

[Thierry Chappuis]

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

De quel compilateur s'agit-il? Thierry

[nicolas.sitbon]

De quel compilateur s'agit-il? Thierry

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

[Gf6HqmTW]

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

[diogene]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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;
}

[Gf6HqmTW]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

est equivalent à

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Adrien93]

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 !

[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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[Médinoc]

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

[Jean-Marc.Bourguet]

Je ne comprend pas le code proposé.

Par ailleurs pour lrint ça ne compile pas :

incompatible implicit declaration of built-in function «lrint"

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

[Adrien93]

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