Discussion :

[Superne0]

Bonsoir à tous,
voilà, j'ai le code suivant (calcul de a^e mod m) en méthode récursive.
Seulement, quelquechose cloche, car je n'arrive pas à obtenir le bon résultat.
J'ai l'impression d'omettre certains termes dans le calcul final, mais je ne vois pas quoi.
Si quelqu'un pouvait m'aider ...

Code :

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

1
2
3
4
5
6
7
8
9
10
11
unsigned int pModulaire(unsigned int a, unsigned int e, unsigned int m){
	if(e==1){
		return(a%m);
	}else{
		if((e%2)==0){
			return(pModulaire(a*a,e/2,m));
		}else{
			return(a*pModulaire(a*a,(e-1)/2,m)%m);
		}
	}
}

N.B : Par exemple, pour 17^27 mod 27, le résultat est 26, et avec l'algo précédent on obtient 0.

[droggo]

Hio,

Tu n'aurais pas un débordement de capacité de tes variables ?

[Jedai]

L'idée de l'exponentiation modulaire, c'est d'appliquer le modulo à chaque étape, pas seulement à la dernière, sinon tu risques un dépassement de capacité comme ici, en effet, 17^27 est égal à 1667711322168688287513535727415473, largement au-delà des capacités de représentation d'un "unsigned int"...

--
Jedaï

[droggo]

Kio,

C'est manifestement un problème de débordement, ta fonction donne le bon résultat pour des valeurs plus "raisonnables", c'est à dire évitant de tomber dans ce travers.

Si tu ne tiens pas absolument à la récursivité, voici une méthode itérative, qui donne le bon résultat avec tes valeurs.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
unsigned int pModulaire2(unsigned int a, unsigned int e, unsigned int m){
   unsigned result = 1;
 
   while (e > 0) {
      if (e & 1 > 0) result = (result * a) % m;
      e >>= 1;
      a = (a * a) % m;
   }
 
   return result;
}

[Zavonen]

Voilà une version récursive, mais l'itératif proposé par Droggo est meilleur

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
#include <stdio.h>
#include <stdlib.h>
 
unsigned int PowMod(unsigned int a, unsigned int e, unsigned int m)
{
    if (e==0)
        return 1;
    else
        return (a*PowMod(a,e-1,m))%m;
}
 
int main()
{
    printf("%u\n",PowMod(17,27,27));
    return 0;
}

[Jedai]

On peut faire en récursif quelque chose d'aussi efficace que le code itératif, mais déjà faisons mieux que Zavonen, de sorte à avoir la même complexité que Droggo au moins !

Code :

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

1
2
3
4
5
6
7
8
9
unsigned int pModulaire(unsigned int a, unsigned int e, unsigned int m) {
	if (e == 0) {
		return 1;
	} else if ( e & 1 ) {
		return(pModulaire( (a*a) % m, e >> 1, m));
	} else {
		return( (a * pModulaire( (a*a) % m, e >> 1, m)) % m);
	}
}

--
Jedaï

[droggo]

Kui,

On peut faire en récursif quelque chose d'aussi efficace que le code itératif, mais déjà faisons mieux que Zavonen, de sorte à avoir la même complexité que Droggo au moins !

Code :

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

1
2
3
4
5
6
7
8
9
unsigned int pModulaire(unsigned int a, unsigned int e, unsigned int m) {
	if (e == 0) {
		return 1;
	} else if ( e & 1 ) {
		return(pModulaire( (a*a) % m, e >> 1, m));
	} else {
		return( (a * pModulaire( (a*a) % m, e >> 1, m)) % m);
	}
}

--
Jedaï

Personnellement, je n'ai jamais vu une fonction récursive aussi efficace qu'une fonction itérative, ne serait-ce que le temps pris pour passer les arguments lors de chaque appel, sans même parler des initialisations des variables locales, s'il y a lieu d'en faire.

Sauf bien entendu si le compilateur optimise si bien qu'il ne fait pas réellement d'appels récursifs, et transforme donc le tout en fonction itérative. Il ya des cas où c'est possible.

[Jedai]

L'efficacité d'une solution récursive face à une solution itérative dépend du langage et du compilateur (et du problème), mais effectivement en disant cela je pensais à une fonction récursive terminale qu'un bon compilateur peut optimiser grandement, aboutissant carrément à une boucle dans certains cas.

NB : Le C est particulièrement peu adapté à la récursion, mais dans un langage comme Haskell c'est le seul moyen de "boucler", bien sûr en sous-main cette récursion est souvent transformée en une véritable boucle au niveau assembleur. Ce qui permet à Haskell d'avoir des performances proches du C dans de nombreux cas alors qu'il s'agit d'un langage au niveau d'abstraction considérablement plus élevé et où l'itération n'existe même pas.
Comme tu le vois, tout est relatif.

--
Jedaï

[Zavonen]

UNe exponentiation rapide, itérative.

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <stdlib.h>
// détermine le nombre de chiffres dans la décomposition binaire de e
unsigned int MaxPow2(unsigned int e)
{
    unsigned result=0;
    while (e)
    {
        e=e>>1;
        result ++;
    }
    return result;
}
 
unsigned int PowMod(unsigned int a, unsigned int e, unsigned int m)
{
    unsigned int k=MaxPow2(e);
    int i;
    unsigned int p=1;
    unsigned int * s= malloc(k*sizeof(unsigned int));
    unsigned int * b= malloc(k*sizeof(unsigned int));
//stocke les chiffres de la décomposition
    for (i=0;i<k;i++)
    {
        b[i]=e&1;
        e=e>>1;
    }
// stocke les carrés successifs
    s[0]=a%m;
    for (i=1;i<k;i++)
    {
        s[i]=(s[i-1]*s[i-1])%m;
    }
    for (i=0;i<k;i++)
        if (b[i])p=(p*s[i])%m;
    free (s);
    free (b);
    return p;
}
 
int main()
{
    printf("%u\n",PowMod(17,27,27));
    return 0;
}

[Superne0]

Bon déjà, merci pour votre intérêt au problème !
Vos méthodes ont l'air de toutes fonctionner (la plus proche postée initialement et la récursive de Jedai, il manquait le modulo m dans les fonctions de retour).
Par contre, pourriez-vous m'expliquer ce que signifie la notation e>>1 ?
Merci encore

[Zavonen]

C'est l'opérateur de décalage à droite
On pousse tous les bits d'un cran (ou de plusieurs si on remplace 1 par n) vers la droite (on perd donc des données de ce côté), on complète par des zéros sur la gauche.
De fait on obtient le quotient par une puissance de 2 sans faire appel à une routine coûteuse de division.
De la même façon un & logique avec 1, donne le bit de poids faible qui est le reste de la division par 2.
Ces opérations (>> et &) correspondent à des instructions du processeur, donc de la logique câblée extrêmement rapide.

[Superne0]

Ouai donc on opère sur l'entier codé en binaire, et non plus sur l'entier lui-même si j'ai bien compris ...
Merci

[Zavonen]

Exactement !
Mais pourquoi distingues-tu l'entier lui-même et l'entier codé en binaire.
Tu as l'entier (indépendant de toute représentation) et ses représentations dans les diverses bases (usuelles ou non).
Nous travaillons donc ici sur la représentation binaire de l'entier, correspondant à sa représentation interne en machine. Pour cette représentation il n'y a rien à faire pour obtenir le quotient et le reste de la division par 2, de la même façon qu'il n'y a rien à faire avec la représentation usuelle en base 10) pour obtenir le reste (dernier chiffre) et le quotient (tous chiffres sauf le dernier) dans la division par 10.
Les opérateurs >> et & se substituent donc ici à des /2 et %2 qui font appel à des opérateurs généraux du langage faisant eux-mêmes appel à des routines générales. Dans le cas de 2 c'est du gâchis, de la même façon qu'à la main on ne POSE jamais une division par 10.

[Superne0]

Eh bien merci, ça pourrait m'être utile pour la suite

[Jean-Marc.Bourguet]

Deux petites choses:
- aucune méthode jusqu'à présent ne fonctionne pour m > SQRT(UINT_MAX).
- jouer avec les opérateurs binaires plutôt que / et % quand ils sont équivalents n'a un intérêt sur aucun compilateur que j'ai testé les 15 dernières années. Autrement dit: écrire ce qui est le plus proche de ce qu'on veut plutôt que d'être obscur pour essayer d'être plus rapide sans y résussir. Surtout sur un forum d'algorithmique. Et quand on fait ca en présentant une solution qui utilise de l'allocation dynamique sans en avoir besoin,...

[Zavonen]

@ Jean-Marc.Bourquet
Surprenant ! mais parfaitement exact ...
Je viens de tester:

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
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <stdlib.h>
 
void test1()
{
    int i,j;
    int x=1254;
    int y;
    int z;
    for (i=0;i<1000000;i++)
        for (j=0;j<10000;j++)
        {
            y=x/2;
            z=x%2;
        }
}
 
void test2()
{
    int i,j;
    int x=1254;
    int y;
    int z;
    for (i=0;i<1000000;i++)
        for (j=0;j<10000;j++)
        {
            y=x&&1;
            z=x>>1;
        }
 
}
 
int main()
{
    test1();
    //test2();
    return 0;
}

J'ai tout d'abord cru que le compilo était suffisamment 'smart' pour détecter un paramètre 2 et agir en conséquence; mais non ! en remplaçant 2 par 3 les temps sont inchangés.
La remarque selon laquelle l'allocation dynamique n'est pas nécessaire, est également valable.
Tout est donc bon à prendre.

[droggo]

Jue,

UNe exponentiation rapide, itérative.

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
#include <stdio.h>
#include <stdlib.h>
// détermine le nombre de chiffres dans la décomposition binaire de e
unsigned int MaxPow2(unsigned int e)
{
    unsigned result=0;
    while (e)
    {
        e=e>>1;
        result ++;
    }
    return result;
}

Un moyen plus rapide, même s'il semble un peu ésotérique (pour des unsigned sur 32 bits !).

Code :

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

1
2
3
4
5
6
7
8
unsigned countBitsOne(unsigned v)
// compte le nombre de bits à 1
{
    unsigned w = v - ((v >> 1) & 0x55555555);
    unsigned x = (w & 0x33333333) + ((w >> 2) & 0x33333333);
    unsigned c = ((x + (x >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
    return c;
}