Discussion :

[candidson]

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 :

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

[jobherzt]

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

[ol9245]

Code :

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

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 :

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

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

[millie]

Code :

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

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 :

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

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

[jobherzt]

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 /

[millie]

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

Honte à moi

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é

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

le % de facon iterative

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

Code :

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

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;

[millie]

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

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
 
/*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 :

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

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.

[acx01b]

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
}

[O( N )]

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 et que je reviendrais )

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é (trop mauvaise)
à moins que ce ne soit celle de millie alors je serais content !!!

[O( N )]

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 :

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

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

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...
par contre je recalcule la différence au lieu de baisser de 1 les décalages suivants....

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.