Discussion :

[NeoKript]

Bonjour a tous,
je suis en train de coder une calculette en C et je cherche le moyen de calculer le modulo et la division de deux nombres (qui sont dans des char *), j'ai code un algorithme, mais lorsque je cherche le modulo d'un nombre de + de 10 chiffres avec 2 par exemple, mais il met plus de 10s. Connaissez-vous des algorithmes "rapide" pour effectuer ce genre d'opérations.

Merci d'avance.
NeoKript

[ram-0000]

C'est quoi ton algorithme de modulo ?

Sinon, tu peux utiliser le reste de la division entière. Une division euclidienne comme on l'a apprise à l'école, cela doit se coder assez facilement.

[NeoKript]

Pour l'algo du modulo,
par exemple pour A%B, je fait A-B jusqu'a que A < B, mais ce n'est pas trop rapide.

Voila
Merci d'avance
NeoKript

[ram-0000]

C'est sur qu'avec un algo pareil cela va être long de calculer le modulo d'un nombre à 10 chiffres.

Regarde du côté de la division euclidienne.

[Obsidian]

j'ai code un algorithme, mais lorsque je cherche le modulo d'un nombre de + de 10 chiffres avec 2 par exemple, mais il met plus de 10s. Connaissez-vous des algorithmes "rapide" pour effectuer ce genre d'opérations

Fais voir ton algo, déjà. On pourra ensuite te dire si on a plus efficace ou pas (a priori oui).

Ensuite, si tu cherches le « modulo 2 » en particulier d'un nombre représenté en décimal par une chaîne de caractères, tu n'as pas besoin de le diviser : tu regardes simplement si le dernier chiffre est pair (donc si c'est un 0, un 2, un 4, un 6 ou un 8).

[dapounet]

Bonjour,

Il y a une implémentation d'un algorithme de Knuth ici : http://www.hackersdelight.org/HDcode/divmnu.c.

[NeoKript]

Merci pour vos réponses,

pour le moment pour le modulo, mon algo se limite pour A mod B par ex a faire B - A jusqu'à que le résultat soit inférieur a A...
Donc pour un grand nombre modulo un petit, c'est très (très) lent.

Pour le site que tu m'a passer dapounet, je n'ai pas tout compris.

Merci d'avance
NeoKript

[Climoo]

Evidemment, ton algorthme a une complexité exponentielle sur les "grands nombres", c'est à dire ceux qui ont beaucoup de chiffres.
Mais en effet il existe un algo polynomiale (plus rapide) pour ce problème.
Tu peux, par exemple, créer un tableau de chiffres (de la taille maximale que tu veux), pour stocker ton nombre. Et ensuite, tu dois créer une fonction qui fait A % B , mais en essayant de faire la méthode comme sur le papier, comme en primaire où on t'a appris les divisions. Je vais essayer de retrouver l'algo...
EDIT: sur ce site, ils parlent de quelque chose qui marche:
http://www.developpez.net/forums/d81...rands-nombres/

[sloshy]

On dirait un tek1 qui tente de faire une bystromatique
Note je suis la pour la même chose, le modulo n'est pas vraiment difficile il s'agit d'une division suivi d'une soustraction.

Pour la division, j'ai tenter de recoder un algo copiant l'humain (division écrite de primaire) mais le temps d'exécution reste trop long a mon gout. (mon exercice doit etre capable de gerer des nombres "infini").
Les autres algo ne m'inspire pas vraiment dans le sens ou je ne les comprend pas ...