Calcul modulo grand nombre [Résolu/Fermé]

Signaler
Messages postés
15
Date d'inscription
jeudi 24 avril 2008
Statut
Membre
Dernière intervention
14 avril 2009
-
Messages postés
1
Date d'inscription
mercredi 26 juin 2019
Statut
Membre
Dernière intervention
26 juin 2019
-
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

6 réponses

Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
827
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)
5
Merci

Quelques mots de remerciements seront grandement appréciés. Ajouter un commentaire

CCM 65492 internautes nous ont dit merci ce mois-ci

Messages postés
11066
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
18 octobre 2016
1 756
Pour les grands nombres oui. Sauf qu'il demande pour 15 chiffres maximum ;)
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
827 >
Messages postés
11066
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
18 octobre 2016

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 :)
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.
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.
Messages postés
1
Date d'inscription
mercredi 26 juin 2019
Statut
Membre
Dernière intervention
26 juin 2019

J'ai du calculer le modulo 97 d'un chiffre sur 45 digits

Objectif : Calculer le modulo d’un data de 45 digits
Contrainte : résultat de calcul sur moins de 12 digits

Principes du calcul :
1) Scinder le data en 4 groupes de 10 digits et un groupe de 5 digits.
N1/N2/N3/N4 sur 10 digits
N5 sur 5 digits
2) Le modulo ne peut être que sur 2 digits maxi (R=97 max) donc quand on l’ajoutera plus tard à un nombre de 10 digits on sera sur moins de 12 digits.
3) Dans une division euclidienne N1 = 97*Q + R
donc (N1-R)*10^x=97*Q*10^x est divisible par 97.
Cela signifie que seul le reste de la première division nous intéresse pour la suite des calculs.
On ajoute R*10^10 à N2 (moins de 12 digits) et on recommence ...

Le résultat est donc pour Excel :
N mod 97 = Mod((Mod((Mod((Mod(N1;97)*10^10+N2);97)*10^10+N3);97)*10^10+N4);97)*10^5) »+N5)
Messages postés
29801
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
12 mai 2021
7 089
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
Messages postés
11066
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
18 octobre 2016
1 756
Normal. T'as obligé LL à la fin de l'initialisation.
Teste :
long long int x = 123456789012345LL;

Ca devrait enlever le warning ;)
Messages postés
29801
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
12 mai 2021
7 089
Effectivement, je ne connaissais pas. Comme quoi on en apprend tous les jours !
Messages postés
29801
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
12 mai 2021
7 089
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...
Messages postés
11066
Date d'inscription
samedi 5 mai 2007
Statut
Contributeur
Dernière intervention
18 octobre 2016
1 756
Salut,
En C, en prenant du long long int, ça marche très bien ;)
Messages postés
15
Date d'inscription
jeudi 24 avril 2008
Statut
Membre
Dernière intervention
14 avril 2009
1
bravo a tous et merci !
Messages postés
15
Date d'inscription
jeudi 24 avril 2008
Statut
Membre
Dernière intervention
14 avril 2009
1
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