Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Algorithme de division ou de modulo sur grands nombres


Sujet :

Algorithmes et structures de données

  1. #1
    Membre éprouvé
    Algorithme de division ou de modulo sur grands nombres
    Bonjour.
    Dans mon précédent sujet, je demandaiscomment faire une multiplication de nombres composés allant jusqu'à 10^112, je vous remercie, j'ai réussi grâce à vous à le faire.
    ici, les conditions sont les mêmes que précédement, je vous revoie donc pour celles-ci au sujet précédent: http://www.developpez.net/forums/vie...c.php?t=431734

    je souaite à présent pouvoir calculer un modulo de deux grands nombres rapidement.

    auparavant, j'utilisais dans mes algoritmes une division pour les modulo, mais n'ayant pas touvé de methode pour diviser deux grands nombres entre eux (seulement un grand nombre et un petit (<=10^15))

    j'ai donc utilisé la methode bourinne de la recherche avec une boucle en multipliant un premier nombre par un indice, mais le résultat fut d'une lenteur catastrophique.

    bref, si vous avez une idée...

    Merci
    Méphistophélès
    Si la solution ne résout pas votre problème, changez le problème...
    Cours et tutoriels C++ - FAQ C++ - Forum C++.

  2. #2
    Expert éminent
    Re: Algorithme de division ou de modulo sur grands nombres.
    Citation Envoyé par méphistopheles
    je souaite à présent pouvoir calculer un modulo de deux grands nombres rapidement.
    Knuth donne la methode dans "The Art of Computer Programming". Je ne la connais pas par coeur et n'ai pas le bouquin sous la main.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  3. #3
    Membre éprouvé
    glups....
    heu, tu parle du modulo où de la division?
    sinon, il y as un endroit où je peux en trouver un équivalen (sur internet)?


    merci
    Méphistophélès
    Si la solution ne résout pas votre problème, changez le problème...
    Cours et tutoriels C++ - FAQ C++ - Forum C++.

  4. #4
    Expert éminent
    Citation Envoyé par méphistopheles
    tu parle du modulo où de la division?
    Des deux.

    sinon, il y as un endroit où je peux en trouver un équivalen (sur internet)?
    J'ai vu des implementations, mais l'explication je ne suis jamais tombe dessus. Quand j'en ai besoin je sais ou trouver le bouquin (dans ma bibliotheque). Si tu ne trouves rien, envoie moi un email.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  5. #5
    Membre éprouvé
    je vais chercher,je te contacterais si je ne trouve pas.


    merci
    Méphistophélès
    Si la solution ne résout pas votre problème, changez le problème...
    Cours et tutoriels C++ - FAQ C++ - Forum C++.

  6. #6
    Membre actif
    Tiens, j'ai vu ça mais je sais pas ce que ça vaut :

    http://www.eleves.ens.fr/home/coron/cours/nombre/no_08.pdf

    (pages 12 et suivantes)

  7. #7
    Expert éminent
    J'ai le bouquin sous la main et un peu de temps libre...

    On essaie donc de diviser un nombre exprimé en base B (genre 2^16 ou 10000) choisie de sorte qu'on puisse calculer toutes les divisions d'un nombre inférieur à B^2 par un nombre inférieur à B.

    On va diviser u = u[n+m-1] ... u[1] u[0]
    par v = v[n-1] ... v[1] v[0]
    {x} note le plus grand entier inférieur ou égal à x

    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
    Multiplier u et v par d = {b/(v[n-1]+1]} (c'est une étape de normalisation, l'important dans le choix de d est que v[n-1] soit plus grand ou égal à B/2 à la fin
    
    Pour j de m à 0 par pas de -1
       qh = {(u[j+n]B + u[j+n-1])/v[n-1]}
       rh = (u[j+n]B+u[j+n-1]) mod v[n-1]
       Si qh = B ou qh*v[n-2] > rh*B + u[j+n-2]
          qh = qh-1
          rh = rh +v[n-1]
          si rh < B et qh*v[n-2] > rh*B + u[j+n-2]
             qh = qh -1
             rh = rh + v[n-1]
          fin si
       fin si
       u = u - qh v B^j
       si u < 0 
          u = u + v
          qh = qh - 1
       fin si
       q[j] = qh
    fin pour

    Le résultat de la division est q[m] ... q[0]
    Si on veut le reste, il faut diviser u par d (pour défaire ce qu'on a fait à la première étape).

    C'est relativement difficile de passer dans la branche u < 0 à la fin -- 2 chances sur B environ si on prends des nombres au hasard.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  8. #8
    Membre du Club
    et les bon vieux ppcm et pgcd tu as essayé ???

  9. #9
    Membre éprouvé
    Citation Envoyé par ar_men
    et les bon vieux ppcm et pgcd tu as essayé ???
    En général, pour le pgcd, on utilise l'algorithme d'euclide or pour lui, on à besoin... des division :o pas trés pratique

    sinon, merci jen-marc, j'ai pu résoudre mon problème gra ce à toi. la documentation de lefuret étais intéressante, mais je n'ais pas compris

    merci à tous
    Méphistophélès
    Si la solution ne résout pas votre problème, changez le problème...
    Cours et tutoriels C++ - FAQ C++ - Forum C++.

  10. #10
    Membre du Club
    tu as une autre solution que j'avais utilisé en quick basic pour vérifier la validité des comptes bancaires en faisant une divion de nombres entiers (pour eviter les erreurs base 2 - base 10)
    tu transfome ton nombre en cahine de caractères et tu saucissonnes
    et là il n'y a plus de limites, mais c pas jouable evec le diviseur

  11. #11
    Nouveau membre du Club
    Je sais que je déterre un vieux topic mais j'ai besoin d'un tel algorithme. J'ai essayé d'appliquer celui de Jean-Marc à un exemple et cela ne fonctionne pas :
    u = 1234
    v = 45

    On trouve d=2 d'où u=2468 et v=90

    j=2 :
    qh = 2/9 = 0
    rh = 2%9 = 2
    donc q[2] = 0

    j=1 :
    qh = 24/9 = 2
    rh = 6
    u = u-2*90 = 288
    donc q[1] = 2

    j=0:
    qh = 28/9 = 3
    rh = 28%9 = 1
    u = u-3*90 = 2018
    donc q[0] = 3

    On trouve un quotient de 23 alors qu'il vaut 27...

  12. #12
    Expert éminent
    Citation Envoyé par TheShade Voir le message
    Je sais que je déterre un vieux topic mais j'ai besoin d'un tel algorithme. J'ai essayé d'appliquer celui de Jean-Marc
    C'est pas le mien, c'est celui de Knuth et j'ai fait une erreur en le recopiant.


    à un exemple et cela ne fonctionne pas :
    u = 1234
    v = 45

    On trouve d=2 d'où u=2468 et v=90

    j=2 :
    qh = 2/9 = 0
    rh = 2%9 = 2
    donc q[2] = 0

    j=1 :
    qh = 24/9 = 2
    rh = 6
    u = u-2*90 = 288
    u = u - 2*90 * 10^j = 668

    et la suite. Je corrige dans mon message original.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  13. #13
    Nouveau membre du Club
    merci beaucoup

  14. #14
    Membre à l'essai
    Bonjour, cela fait 2 heures que j'essaye de comprendre l'algo donne plus haut, mais franchement j'avoue avoir du mal avec les n, j, m etc ...

    Surtout que je ne vois pas a quoi elles sont egal au debut, lors de leur initialisation ...
    Serait il possible que quelqu'un m'explique un peu mieux ce code svp ?

    Merci beaucoup

    ps : desole pour les accents manquant, mais je suis sur un clavier qwerty ^^

  15. #15
    Rédacteur

    Citation Envoyé par Twin111 Voir le message
    Bonjour, cela fait 2 heures que j'essaye de comprendre l'algo donne plus haut, mais franchement j'avoue avoir du mal avec les n, j, m etc ...
    C'est la méthode de division apprise en primaire (long division), qui est généralisée pour une base B (au lieu de la base 10 habituelle).
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  16. #16
    Rédacteur

    Code python :Sélectionner tout -Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def modulo (n,p):
        if n<10:
            return n%p
        else:
            return ((n%10)%p+modulo(n/10,p)*10)%p
     
    def main():
        print modulo(37847894521474578914,7)
     
    if __name__ == '__main__':
        main()
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

  17. #17
    Membre à l'essai
    Merci de ta reponse, mais je voulais parler de la methode de Knuth. De plus je ne peux pas stocker mes nombre dans des INT (je code en C) donc je le stock dans des char*.

    Donc voila si vous avez des conseilles

  18. #18
    Expert éminent
    Citation Envoyé par Twin111 Voir le message
    Bonjour, cela fait 2 heures que j'essaye de comprendre l'algo donne plus haut, mais franchement j'avoue avoir du mal avec les n, j, m etc ...

    Surtout que je ne vois pas a quoi elles sont egal au debut, lors de leur initialisation ...
    Serait il possible que quelqu'un m'explique un peu mieux ce code svp ?
    n désigne le nombre de chiffre (char dans ton cas) dans le diviseur, et m+n est le nombre de chiffre dans le dividende. Quand à j, c'est l'indice de la boucle. Les v[i] sont les chiffres du diviseurs, les u[i] du dividende. C'est écrit au début du message.
    Les MP ne sont pas là pour les questions techniques, les forums sont là pour ça.

  19. #19
    Membre à l'essai
    Merci beaucoup pour votre aide

    Je ne comprend pas par contre que fait le 'B' dans cette ligne : u[j+n]B

    C'est une multiplication ? u[j+n] * B ? B etant la base si j'ai bien tout compris... ^^

    Dsl pour toutes ces questions mais je sens que ce code va me mettre sur la bonne vois, encore faut t il que je le comprenne ... Donc si vous pouviez me le clarifier au maximum, je vous en serez extremement reconnaissant ! J'ai bien compris le systeme de tete de lecture dans mes char avec les u[i] et v[i]. Mais c'est juste que le code est encore un peu abstrait.

    Peut etre pourriez vous me faire un exemple explicatif decris ligne par ligne en correspondance avec votre code ?
    Car quand je prend l'exemple donne plus haut, je ne comprend pas le resultat obtenue de qh :
    u = 1234
    v = 45

    d'ou d = 10/v[2-1]+1
    d = 10/5 -> d = 2
    donc u = 2468 et v = 90
    Or ici si j'applique ce que je lis : qh = (u[2+2]B + u[2+2-1])/v[2-1]
    qh = (8B+6)/9
    or dans l'exemple, il fait 2/9
    D'ou viens le '2' alors ?

    Merci encore pour le temps que vous m'accordez.

  20. #20
    Rédacteur

    C'est la même chose que mon programme python mais en C en itératif et avec des chaînes en entrée.
    NB: Aucun checking n'est prévu.

    Code C :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
    38
    39
    40
    41
    42
    #include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
     
    unsigned char * tableau ( unsigned char * s)
    {
        int n = strlen(s);
        unsigned char * tab;
        tab= (unsigned char *) malloc (n*sizeof(unsigned char));
        int m =0;
        while (s[m])
        {
            tab[m]=s[m]-48;
            m++;
        }
        return tab;
    }
     
    unsigned int modulo (unsigned int n, unsigned char * T, unsigned int p)
    {
        unsigned int result=0;
        unsigned int i;
        unsigned int pow=1;
        result= T[n-1]%p;
        for (i=1;i<n;i++)
        {
            pow=(pow*10)%p;
            result += (pow*T[n-1-i])%p;
            result%=p;
        }
        return result;
    }
     
    int main(int argc, char *argv[])
    {
        unsigned char * s="123456789";
        unsigned char * T;
        unsigned int n=strlen(s);
        T=tableau(s);
        printf("%d\n",modulo(n,T,6));
        return 0;
    }
    Ce qu'on trouve est plus important que ce qu'on cherche.
    Maths de base pour les nuls (et les autres...)

###raw>template_hook.ano_emploi###