Discussion :

[méphistopheles]

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/viewtopic.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

[Jean-Marc.Bourguet]

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.

[méphistopheles]

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

[Jean-Marc.Bourguet]

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.

[méphistopheles]

je vais chercher,je te contacterais si je ne trouve pas.


merci

[Le Furet]

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)

[Jean-Marc.Bourguet]

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.

[ar_men]

et les bon vieux ppcm et pgcd tu as essayé ???

[méphistopheles]

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

[ar_men]

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

[TheShade]

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...

[Jean-Marc.Bourguet]

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.

[TheShade]

merci beaucoup

[Twin111]

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 ^^

[pseudocode]

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).

[Zavonen]

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()

[Twin111]

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

[Jean-Marc.Bourguet]

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.

[Twin111]

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.

[Zavonen]

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;
}