Calculer le modulo sans utiliser l'operateur %

Bonjour,
je suis plus ou moins nouveau en C++ et j'ai un pti probleme. Comment pourrais-je calculer le % de facon iterative et sans utiliser les operateurs %, * et /.
Mon idée est la suivante:
Calcul de i%j:
i > j et j!=0;
calculer i - j et redonner le resultat juska ce ke i<j.
Mais je nariv pa à implementer i - j de facon periodique, cest a dire, i-j de facon repetee.

Voici ce ke g pu fair juska present:
Natural est la classe.

Code:

---

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

Natural operator%(Natural n1, Natural n2) { int modulo(0); assert(n2.getValue()!=0); modulo = n1.getValue() - n2.getValue();   if ( n1 == n2) { return modulo = 0;} else if(n1.getValue()<n2.getValue()) { return modulo = n1.getValue();} else // c'est ici ke commencent les ennuis!!! { while (n1.getValue()>n2.getValue()) return modulo = modulo - n2.getValue(); }     return modulo; }

---

Merci pour l'aide!

essaie d'utiliser la balise code, et si tu poste dans la rubrique algorithme, presente les choses sous la forme d'algorithme...

je ne suis pas un specialiste, mais le "return modulo=0", a mon avis ca ne va pas faire ce que tu veux.....

et on est bien content de savoir ou les ennuis commence, mais faudrait aussi preciser lesquelles :) meme si la c'est assez evident : pourquoi vient tu mettre un return au milieu de ta boucle ??? je te rappelle que return interrompt la fonction et retourne la valeur qui le suit. donc si tu vire tes return qui ne sont pas a leur place, ca devrait presque marcher...

sauf que "while (n1.getValue()>n2.getValue())" est toujours vrai puisque ces valeurs ne varient pas -> ca va tourner en rond. donc faut re-reflechir a ta boucle.

bon courage :)

Code:

---

1 2 3 4 5 6 7

fonction modulo(entier : n, entier : modulo_m) : entier vérifier n > 0 et modulo_m > 0 if n < modulo_m then return n else return modulo (n - modulo_m, modulo_m) end if

---

sinon, u peux exploiter que la division d'entier arrondit à l'entier inférieur ou égal le plus proche

Code:

---

1 2	fonction modulo(entier : n, entier : modulo_m) : entier return n - (n/modulo_m) * modulo_m ;

---

Citation:

---

Envoyé par ol9245

Code:

---

1 2 3 4 5 6 7

fonction modulo(entier : n, entier : modulo_m) : entier vérifier n > 0 et modulo_m > 0 if n < modulo_m then return n else return modulo (n - modulo_m, modulo_m) end if

---

sinon, u peux exploiter que la division d'entier arrondit à l'entier inférieur ou égal le plus proche

Code:

---

1 2	fonction modulo(entier : n, entier : modulo_m) : entier return n - (n/modulo_m) * modulo_m ;

---

---

J'ai une préférence pour la deuxième méthode qui a l'avantage d'être fait en temps "constant". La première méthode a une écriture récursive sympatique mais peut avoir tendance à être très long, rien que : 999999999999 % 1 risque de prend pas mal de temps ;)

Citation:

---

Envoyé par millie

J'ai une préférence pour la deuxième méthode qui a l'avantage d'être fait en temps "constant". La première méthode a une écriture récursive sympatique mais peut avoir tendance à être très long, rien que : 999999999999 % 1 risque de prend pas mal de temps ;)

---

il a indiqué qu'il n'avait pas le droit d'utiliser * et / :)

Citation:

---

Envoyé par jobherzt

il a indiqué qu'il n'avait pas le droit d'utiliser * et / :)

---

Honte à moi :sm:

Alors c'est facile, il suffit d'implémenter * en utilisant une méthode basée sur la transformée de Fourier rapide. Tu pourras ensuite faire une division à la manière classique, et le tour est joué :mouarf:

Bon, vu que c'est demandé de manière itérative et non récursive (et pas une méthode bourrine) :

Citation:

---

le % de facon iterative

---

Un truc dans le genre devrait suffir (roh la la, j'ai beaucoup réflechi :mouarf: ) :

Code:

---

1 2 3 4 5 6 7 8

/*précondition : modulo_n >=1*/ fonction modulo(Entier n, Entier modulo_n)-> Entier Entier temp = n; while(temp>=modulo_n) temp <- temp- modulo_n;   return temp;

---

Je propose la méthode suivante qui est plus rapide sur des grands nombres :aie: :

Code:

---

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

/*Je ne pourrais être tenu pour responsable des dommages irrémédiables que pourrait provoquer ce code*/ #include <stdio.h> #include <stdlib.h> #include <stdint.h>   int getMaxPower(int n) { return(log(n)/log(2)); }   int modulo(int n, int modulo_n) { int currentPower = getMaxPower(n) - getMaxPower(modulo_n); int temp = n;   while(currentPower>=0) { int currentModulo = modulo_n<<currentPower; while(temp>=currentModulo) { temp -= currentModulo; } currentPower--; } return temp; }   int main(void) { int i;   fprintf(stderr, "%d\n", modulo(1000,7));   return EXIT_SUCCESS; }

---

EDIT :
Arf : j'ai triché, j'utilise / dans le getMaxPower, je propose alors la nouvelle fonction :

Code:

---

1 2 3 4 5 6 7 8 9 10 11

int getMaxPower(int n) { int temp = n; int power = -1; while(temp>0) { temp = temp>>1; power++; } return power; }

---

EDIT 2 En fait, il y a moyen de faire quelque indépendemment du nombre de bit des entiers en utilisant simplement n. J'ai édité en conséquence.

salut

il y a un moyen très simple qui dépend du nombre de bits du nombre binaire

mettons que
int getbit(n,i);
renvoie 0 si le bit numéros i de n est 0
renvoie 1 si le bit numéros i de n est 1

int taille(n); renvoie la taille en bit de n

le bit 0 c'est le bit de poids fort bien sûr

int modulo(int n, int m) {
int i;
int r = 0;
for (i = 0; i < taille(n); i++) {
r = r*2 + getbit(n,i);
if (r > m) r = r - m;
}
return r;
}


pour illustrer avec un programme qui fonctionne:

int taille;
int modulo(char *n, int m) {
int i;
int r = 0;
for (i = 0; i < taille; i++) {
r = r*2 + n[i];
if (r > m) r = r - m;
}
return r;
}

int main() {
char tab[] = {1,1,0,1,0,0,1,1,1}; // 423 en binaire
taille = sizeof tab;
printf(" %d ", modulo(tab,67)); // affiche 21 : 423 = 6*67 + 21
}

Bonjour a tous ;)

Chouette question ...

J'aimerais voir ce problème du côté complexité :

Pour acx01b un algo trés sympathique en O(4*log(n)) opérations + O(log(n)) comparaisons, ll me semble !

Pour millie un algo sympa aussi mais moins apparent (même pas encore trés clair pour moi) !
(J'ai eu une idée presque pareil, il me semble (si je comprends ta démarche), je la
donnerais plus tard quand je l'aurais écrite :mouarf: et que je reviendrais 8O )

Son algo en O(log(n)+log(m)) * (1 comparaison + 2 opérations) +
O(log(n)-log(m)) * (1 comparaison + 3 opérations) , il me semble :?

J'ai oublié dans les comparaisons les log(m) pour acx01b ?

Dès que possible je vous envoie mon algo que je rigole sur sa complexité :aie: (trop mauvaise)
à moins que ce ne soit celle de millie alors je serais content !!!

Bon ben voilà mon algo est sensiblement le même à celui de millie, il est moins efficace je crois...
j'aurais ajouté cette ligne en plus, à la place de currentPower--;

Code:

---

1 2	currentPower = getMaxPower(temp) - getMaxPower(modulo_n);

---

je cherchais à avoir un log dans le quotient (q) plutôt que dans le numérateur n. avec n = q*m+r.

L'idée étant de trouver la différence de puissance de 2 entre n et m
puis d'augmenter m d'autant de puissance => décallage. m << d ou m >> d (j'ai oublié :aie: ).

puis on retire m (décallé de d) à n et on garde dans une variable temporaire (cf millie).
Je suis plutôt content j'ai eu la même idée... :mouarf:
par contre je recalcule la différence au lieu de baisser de 1 les décalages suivants....:aie:

D'après estimation j'aurais comme complexité
log(m)+log(n) + (log(n)-log(m))*(log(m)+log(temp))

Il me semble que l'algorithme le plus efficace reste celui de millie et l'algorithme le plus lisible celui de acx01b.