Calcul modulo grand nombre
Résolu/Fermé
tchobubu
Messages postés
15
Date d'inscription
jeudi 24 avril 2008
Statut
Membre
Dernière intervention
14 avril 2009
-
24 oct. 2008 à 17:30
gbleuse Messages postés 1 Date d'inscription mercredi 26 juin 2019 Statut Membre Dernière intervention 26 juin 2019 - 26 juin 2019 à 11:00
gbleuse Messages postés 1 Date d'inscription mercredi 26 juin 2019 Statut Membre Dernière intervention 26 juin 2019 - 26 juin 2019 à 11:00
A voir également:
- Modulo 97
- Modulo c++ ✓ - Forum C++
- Modulo 97 ✓ - Forum Programmation
- Calcul clé IBAN modulo 97 ✓ - Forum Excel
- 97 tibo - Forum Mail
- Modulo 97 sous excel ? ✓ - Forum Excel
6 réponses
bizu53
Messages postés
1274
Date d'inscription
samedi 30 août 2008
Statut
Membre
Dernière intervention
21 juin 2015
859
25 oct. 2008 à 01:37
25 oct. 2008 à 01:37
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)
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)
25 oct. 2008 à 01:41
25 oct. 2008 à 01:45
11 déc. 2008 à 15:16
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.
20 déc. 2011 à 09:41
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.
Modifié le 26 juin 2019 à 11:04
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)