Posez votre question Signaler

Calcul modulo grand nombre [Résolu]

tchobubu 15Messages postés jeudi 24 avril 2008Date d'inscription 14 avril 2009Dernière intervention - Dernière réponse le 20 déc. 2011 à 09:41
Bonjour,
je voudrais calculer le modulo d'un nombre a 15 chiffres maxi exemple: 123456789012345%97
sa a l'aire simple mais je ne n'arrive ni a enregistrer un aussi grand nombre dans une variable a ni a utiliser l'opérateur modulo car le nombre n'est pas un int
merci
Lire la suite 
Réponse
+4
moins plus
La technique (je pense) la plus simple si tu veux pouvoir gérer des nombres énormes, c'est de les saisir en tant que chaine de caractères, que tu fractionnes ensuite dans plusieurs int (ils sont gentils les int :)) après t'as juste à faire une petite fonction qui te prendre ce tableau (unicolonne) de int et t'en fais ce que tu veux ^^.

Pour le cas du modulo, tu sais que (a×b+c)%m = ( (a%m)×(b%m)+c%m ) % m
Ici le b serait une simple puissance de 10 correspondant à la situation de la coupure.

Pour reprendre ton exemple :
x_initial = 123456789012345
m = 97
Par exemple en coupant de cette manière :
x[0]=1234567
x[1]=89012345
on a donc x_initial = x[0] × 10^8 + x[1]

tu fais donc :
1234567 % 97 = 48
(10^8) % 97 = 81 (obtenu avec une simple boucle for autant de fois que la puissance de 10, en multipliant par 10 à chaque fois et en prenant le modulo : 10%97=10 ; 100%97=3 ; 30%97=30 ; 300%97=9 ; 90%97=90 ; 900%97=27 ; 270%97=76 ; 760%97=81)
89012345 % 97 = 4

ce qui te donne (48*81+4)%97=12

Tu peux bien évidemment fractionner ton nombre de + de morceau la formule est bien sûr toujours valable, ça te ferait juste de simples additions supplémentaires. Tu peux ainsi trouver le modulo 97 d'un nombre de 8000 chiffres si tu veux de la même manière (en ayant fractionné ton nombre en 1000 int de 8 chiffres chacun)
fiddy 10365Messages postés samedi 5 mai 2007Date d'inscription ContributeurStatut 26 mai 2015Dernière intervention - 25 oct. 2008 à 01:41
Pour les grands nombres oui. Sauf qu'il demande pour 15 chiffres maximum ;)
Répondre
bizu53 1275Messages postés samedi 30 août 2008Date d'inscription 21 juin 2014Dernière intervention - 25 oct. 2008 à 01:45
en effet j'avais pas fait attention au mot "maxi" qu'il avait bien précisé ^^ ça pourra toujours être utile à qqu'un qui tomberait sur ce sujet en cherchant pour des bigs bigs nombres comme ça :)
Répondre
ermite67- 11 déc. 2008 à 15:16
MERCI bizzu53, moi cela m'a servi en tous cas !!

J'utilise un langage qui ne me permets pas de traiter des nombres de plus de 15 chiffres, et je devais calculer un modulo 97 de nombres jusqu'à 18 chiffres !

Pour infos, voici une deuxième méthode que j'ai trouvé :

Exemple sur 9 chiffres pour le numéro 510007547061111462 :

1 Calculer le modulo 97 des 9 premiers chiffres du numéro considéré.
Modulo 97 de 510007547 = 74

2 Recomposer, en partant du reste, un nouveau nombre de 9 chiffres et calculer son
modulo97 :
Modulo 97 de 740611114 = 12.

3 Répéter l'étape précédente jusqu'à ce que tous les chiffres aient été traités.
Modulo 97 de 1262 = 1.
Ce résultat est identique au reste de la division 510007547061111462 par 97.
Répondre
xoxo- 20 déc. 2011 à 09:41
Méthode intéressante, j'y avais pas pensé merci :).

Pour la petite explication, elle se base sur le fait de décomposer les nombres petit à petit en enlevant les multiples élevés aux puissances de 10 de ton nombre (97 dans ton cas) au nombre de base.

Exemple: 9876543 % 29

987 / 29 = 34
9876543 - (29 * 34 * 10000) = 16543

Le 1, c'est celui de ton explication si on fait: 987 % 34. Cette méthode fonctionne aussi très bien en binaire, et peux être utilisée de manière optimale dans les langages comme le C si le nombre modulo prend la moitié de l'espace maximale pour un calcul (par exemple, max = 32bits, le nombre modulo devrait pas faire plus que 16bits pour avoir un traitement optimale).

J'espère avoir éclairé certaines personnes, comme moi, pour lesquels cette méthode paraissait bien curieuse.
Répondre
Ajouter un commentaire
Annonces
 
moins plus
Réponse
+2
moins plus
Effectivement :
#include <stdio.h>

int main(){
    long long int x = 123456789012345;
    printf("%lld\n",x % 97);
    return 0;
}

... me donne :
(mando@aldur) (~) $ gcc -W -Wall plop.c
plop.c: In function ‘main’:
plop.c:4: warning: integer constant is too large for ‘long’ type

Ceci dit malgré le warning, le programme donne bien 12... Quand j'ai vu le warning je n'ai même pas pris le temps de tester :p
Ajouter un commentaire
Annonces
 
moins plus
Réponse
+2
moins plus
Normal. T'as obligé LL à la fin de l'initialisation.
Teste :
long long int x = 123456789012345LL;

Ca devrait enlever le warning ;)
mamiemando 25447Messages postés jeudi 12 mai 2005Date d'inscription ContributeurStatut 27 mai 2015Dernière intervention - 25 oct. 2008 à 13:26
Effectivement, je ne connaissais pas. Comme quoi on en apprend tous les jours !
Répondre
Ajouter un commentaire
Réponse
+0
moins plus
Tout dépend de ce que tu utilises. Par exemple sous linux avec bc ça se fait sans problème :
(mando@aldur) (~) $ bc
bc 1.06.94
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
123456789012345%97
12

Par contre c'est vrai qu'en C par exemple, même avec des long long int ça ne marche pas...
fiddy 10365Messages postés samedi 5 mai 2007Date d'inscription ContributeurStatut 26 mai 2015Dernière intervention - 25 oct. 2008 à 01:04
Salut,
En C, en prenant du long long int, ça marche très bien ;)
Répondre
Ajouter un commentaire
Réponse
+0
moins plus
bravo a tous et merci !
Ajouter un commentaire
Réponse
+0
moins plus
petit ajout le 'LL' est obligatoire après l'initialisation du grand nombre en C++ car il n'y a pas de warning mais une erreur a la compilation ;) encore merci
Ajouter un commentaire
Ce document intitulé «  calcul modulo grand nombre  » issu de CommentCaMarche (www.commentcamarche.net) est mis à disposition sous les termes de la licence Creative Commons. Vous pouvez copier, modifier des copies de cette page, dans les conditions fixées par la licence, tant que cette note apparaît clairement.

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes.

Le fait d'être membre vous permet d'avoir des options supplémentaires.