Discussion :

[necureil]

Bonjour,

Pour effectuer une vérification d'un nombre, je souhaiterais obtenir le modulo 97 d'un nombre.

Après récupération et traitements, j'obtiens le nombre dans une chaine (buff). La chaine peut contenir jusqu'à 68 chiffres donc un double est le mieux adapté... enfin ce que je pensais.

lg = atof(buff);
lg = fmod(lg, 97);

Cependant atof() arrondi le nombre après les 14 premiers chiffres.

Voici le trace.

buff : 18206001203540507700148152776
atof : 18206001203540507000000000000.000000
modulo : 33.000000

Le modulo est donc fausser à cause de la conversion de la chaine vers un double.

Auriez vous une solution pour réaliser le modulo d'un très grand nombre?

[Invité(e)]

Bonjour,

Pour travailler avec de très grands nombres, on peut utiliser gmp.

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
37
#include <stdio.h>
/* utilisation de lib gmp */
#include <gmp.h>
 
 
int main(void)
{
    char result[256];
 
    /* trois entier gmp */
    mpz_t integ[3];
 
    /* initialisation des entiers gmp */
    mpz_init(integ[0]);
    mpz_init(integ[1]);
    mpz_init(integ[2]);
 
 
    /* assignation des entiers gmp */
    mpz_set_str(integ[0], "18206001203540507700148152776", 10);
    mpz_set_str(integ[1], "97", 10);
 
    /* operation modulo */
    mpz_mod(integ[2], integ[0], integ[1]);
 
    /* affichage du resultat gmp */
    if (NULL != mpz_get_str(result, 10, integ[2])) {
        printf("result: %s\n", result);
    }
 
    /* nettoyage gmp */
    mpz_clear(integ[0]);
    mpz_clear(integ[1]);
    mpz_clear(integ[2]);
 
    return 0;
}

Code :

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

result: 1

[diogene]

Il ne faut pas procéder ainsi avec de très grands nombres pour calculer le modulo.
On utilise les propriétés suivantes :

(A+B)mod(N)= (A mod(N)+ Bmod(N))mod(N)
et
(AxB)mod(N)= (A mod(N)x Bmod(N))mod(N)

Ton nombre A est écrit en décimal a(k),a(k-1),a(k-2),...a(0) avec a(i) valant 0..9. Alors :

A = a(k)10^^k +a(k-1)10^^(k-1)+ ...

On peut alors construire la suite

R(k) = a(k)mod(N)
R(k-1) = (R(k)* 10 + a(k-1) ) mod(N)
...
R(i) = (R(i+1)* 10 + a(i) ) mod(N)

Alors R(0) donnera la valeur du reste de la division de A par N

On aura donc par exemple :

Code :

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

1
2
3
4
5
  char tab[]= "18206001203540507700148152776";
  int i;
  int R = 0;
  for(i=0; tab[i] != '\0'; i++)  R = (10*R+tab[i]-'0')%97;
// R est alors le reste de la division par 97

[Invité]

Auriez vous une solution pour réaliser le modulo d'un très grand nombre?

Si ton nombre est sous forme 'chaine de caractères en base 10', la solution consiste à découper la chaine en sous chaines, et à calculer les modulos sur chacune.

Explication en base 97

100=3 mod 97
donc, 10000=9 mod 97
et 100000000=81 mod 97

Donc, si tu découpes ta chaine de 68 chiffres, en 9 groupes de 8 chiffres (en partant de la droite), que tu convertis ces nombres en entiers (int v[9] disons), tu peux de proche en proche calculer ton modulo.

Ca devrait te donner quelque chose comme (mod=le modulo que tu veux, ici 97, res le résultat)

Code :

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

1
2
3
4
 
int mult=100000000%mod;
int res=0;
for(i=8;i>=0;i--) res=(res*mult + (v[i]%mod) )%mod;

Francois (coiffé au poteau par Diogène, désolé...)

[necureil]

Merci beaucoup pour vos réponses.

Ca marche nickel