Bibm@th

Forum de mathématiques - Bibm@th.net

Bienvenue dans les forums du site BibM@th, des forums où on dit Bonjour (Bonsoir), Merci, S'il vous plaît...

Vous n'êtes pas identifié(e).

#26 06-02-2018 19:56:38

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 943

Re : divisions de grands nombres

Re,

Bin, il y a toujours quelque chose qui cloche...
Pour avoir le cœur net, j'ai traité un exemple à la main...
Voilà.
p=57 donc P = [0 , 0 , 5 , 7]
q=86 donc Q= [0 , 0 , 8 , 3]


P = [0 , 0 , 5 , 7]
     4   3   2   1     (indices)
Q = [0 , 0 , 8 , 3]
Prod =[0 , 0 , 0, 0}

      Donc tu fais :
s=0
Pour i de 1 à 4:
     Pour j de 1 à i:

Soit
i = 1
    j=1
         s=0+P[1-1+1]*Q[1]=0+P[1]*Q[1]=0+7*3 = 21 
         21%10 =1 d'où Prod[1]=1  soit Prod=[0 , 0, 0 , 1]
         s=s//10=21//10 =2
i = 2
    j=1
         s=2+P[2-1+1]*Q[1]=2+P[2]*Q[1]=2+5*3 = 17 
         17%10 =7 d'où Prod[2]=7  soit P=[0 , 0, 7 , 1]
         s=s//10=17//10 =1
   j=2
         s=1+P[2-2+1]*Q[2]=1+P[1]*Q[2]=1+7*8 = 57 
         17%10 =7 d'où Prod[2]=7  Prod[2] déjà vu étape précédente !!!
         s=s//10=57//10 =5
Et après ?
Que devient le s ?
         
@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#27 06-02-2018 20:17:28

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : divisions de grands nombres

J'ai envoyé un message tout à[ l'heure, mais il y a eu apparemment un raté ...

Si le coeur du programme peut être compressé sur 5 lignes, au détriment de la clarté et du contrôle de l'algorithme, il y a par ailleurs toutes les instructions préliminaires relatives à la déclaration des constantes, des types et des variables, qui représentent une part non négligeable du code source.

On est donc très au-delà des cinq lignes de code annoncées ! ... même en laissant de côté les instructions d'affichage.

Il faut aussi tenir compte des restrictions imposées aux indices, à moins que les tableaux ne présentent tous la même longueur (d'où un gaspillage inutile d'espace mémoire); songer de plus à la rapidité en évitant de sommer des termes nuls.
Le programme suivant utilise la notation en base 10000 (solution la plus simple); les variables ont été introduites sous forme de constantes, afin de faciliter la vérification du résultat (sur Maxima).


  PROGRAM Multiplication;

  USES Crt, E_Texte;

  CONST Max1 = 10; Max2 = 2 * Max1; D_4: LongInt = 10000;

  TYPE LstE1 = ARRAY[0..Max1 - 1] OF LongInt;
       LstE2 = ARRAY[0..Max2 - 1] OF LongInt;

  CONST x: LstE1 = (1234, 2345, 3456, 4567, 6789, 7890, 8901,
                    9012, 0123, 1234);
        y: LstE1 = (4321, 5432, 6543, 7654, 8765, 9876, 0987,
                    1098, 2109, 0000);

  VAR NtX, NtY: Word; p, q: LstE2;

  PROCEDURE AffXYP;
    VAR k: Word;
    BEGIN
      E(1015); Wt(2, 2, 'Valeur de X:'); E(0012);     GotoXY(11, 4);
      FOR k:= (Max1 - 1) DOWNTO 0 DO Write(x[k]:5);
      E(0015); Wt(2, 6, 'Valeur de Y:'); E(0012);     GotoXY(11, 8);
      FOR k:= (Max1 - 1) DOWNTO 0 DO Write(y[k]:5);
      E(0015); Wt(2, 10, 'Valeur du produit (X*Y):'); E(0010);
      GotoXY(11, 12);
      FOR k:= (Max2 - 1) DOWNTO Max1 DO Write(p[k]:5);
      GotoXY(11, 14);
      FOR k:= (Max1 - 1) DOWNTO 0 DO Write(p[k]:5); A_
    END;

  PROCEDURE CalculP(VAR Im, Jm: Word; VAR X1, Y1: LstE1; VAR Pr: LstE2);
    VAR h, i, j, Hm: Word; s, t: LongInt;
    BEGIN
      FOR h:= 0 TO (Max2 - 1) DO Pr[h]:= 0;                                             // Mise à zéro
      h:= 0; WHILE ((X1[h]>0) AND (h<Max1 - 1)) DO Inc(h); Im:= h;            // Nombres de tranches de x et y
      h:= 0; WHILE ((Y1[h]>0) AND (h<Max1 - 1)) DO Inc(h); Jm:= h;
      Hm:= Im + Jm; s:= 0;                                                                     // Nombre de tranches pour le produit
      FOR h:=0 TO Hm DO
        BEGIN
          FOR i:= 0 TO h DO
            IF (i<=Im) THEN
              BEGIN
                j:= h - i;
                IF (j<=Jm) THEN Inc(s, X1[i] * Y1[j])
              END;
          Pr[h]:= s MOD D_4;
          t:= s DIV D_4; s:= t
        END;
      AffXYP
    END;

  BEGIN
    CalculP(NtX, NtY, x, y, p)
  END.

Il vaut mieux évidemment commencer l'indexation à zéro.

Voilà ce qu'affiche le programme Pascal, et le calcul effectué sur Maxima:
2njk5cp.png
(les éventuels zéros sur la gauche de chaque tranche ne sont pas représentés)
2dvv5lw.png

Dernière modification par Wiwaxia (07-02-2018 08:17:35)

Hors ligne

#28 06-02-2018 20:36:45

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : divisions de grands nombres

salut

je crois que i n'a pas encore était atteint ( on doit arrivé à i=4). Voici comment on procède à la main (en base 10)

Soit à calculer    123*54
1ère étape

0......0......1.......2.......3  ******  4
                                                 5       on fait 4*3=12    on pose le chiffre 2 sous le 3 et la retenue 2 au dessus de 3

(j'ai volontairement omis de fixer les 3 zéros sous le 5)

.................................1
0......0......1.......2.......3**********4
................................2**********5

2éme étape
on fait   1+2*4+3*5=24   on pose 4 sous le 2  et la retenue au dessus de 2  et donc on a


........................2.........1
0........0........1..........2..........3**************4
...............................4..........2**************5
et après cela on  2+1*4+2*5=16  , on porte le
6  sous le 1  et 1 au dessus de 1 et on continue pour obtenir enfin


..............0...........1.............2............1
0.............0...........1............2............3*********4
0.............6...........6............4............2*********5

Cordialement

Dernière modification par hgaruo1951 (06-02-2018 21:05:11)

Hors ligne

#29 06-02-2018 21:25:31

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : divisions de grands nombres

Re ,

Yoshi il faut  exécuter:
 
pour i fixé faire varier    j de  1 à i  et clculer s=s+.... et une fois j=i 
on calculera  pro=    et  s=s div 10 et ce n'est qu'après que l'on incrémentera i

D'après ce que vous faite vous calculez  pro= s mod 10 et s= s div 10 à chaque valeur de j

Cordialement.

Hors ligne

#30 07-02-2018 08:58:52

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : divisions de grands nombres

J'ai repris les consignes d'affichage, afin de faire apparaître tous les zéros ...


  PROCEDURE We30(k: LongInt);
    CONST E1 = 10; E2 = 100; E3 = 1000;
    BEGIN
      IF (k<E1) THEN Write(' 000', k:1)
                ELSE IF (k<E2) THEN Write(' 00', k:2)
                               ELSE IF (k<E3) THEN Write(' 0', k:3)
                                              ELSE Write(' ', k:4)
    END;

  PROCEDURE AffXYP;
    CONST C1 = 2; C2 = 11;
    VAR k: Word;
    BEGIN
      E(1015); Wt(2, 2, 'Valeur de X:'); GotoXY(C2, 4);
      E(0012); FOR k:= (Max1 - 1) DOWNTO 0 DO We30(x[k]);
      E(0015); Wt(2, 6, 'Valeur de Y:'); GotoXY(C2, 8);
      E(0012); FOR k:= (Max1 - 1) DOWNTO 0 DO We30(y[k]);
      E(0015); Wt(2, 10, 'Valeur du produit (X*Y):');
      E(0010);
      GotoXY(C2, 12); FOR k:= (Max2 - 1) DOWNTO Max1 DO We30(p[k]);
      GotoXY(C2, 14); FOR k:= (Max1 - 1) DOWNTO 0 DO We30(p[k]); A_
    END;

... et voici ce qui apparaît sur l'écran:x3u9i1.png

Hors ligne

#31 07-02-2018 11:18:34

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 943

Re : divisions de grands nombres

Bonjour,

@hgaruo1951.
je n'ai fait qu'appliquer à la lettre ce que font tes quelques lignes de code page précédente post #19.
Oui, j'aurais dû continuer jusqu'à n+m soit 4...
Mais je me suis arrêté lorsque j'ai vu que j'accédais pour la 2e fois à P[2] et que j'allais y stocker la même valeur que précédemment : ça m'a paru anormal...
Dans ton post #28, tu m'as tout l'air de ne pas suivre pas à pas tes lignes de code ? Oui/Non
Moi, oui. Oui/Non ?
Peux-tu essayer de refaire à la main ma multiplication, en suivant à la lettre tes lignes de code, comme moi, je l'ai fait ? Ainsi, on verra, si le code publié est le bon...
Je retourne à ma revue, je l'ai un peu négligée hier...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#32 07-02-2018 14:17:32

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : divisions de grands nombres

Bonjour

Soit
s=0
i = 1
    j=1  s=0+P[1-1+1]*Q[1]=0+P[1]*Q[1]=0+7*3 = 21 

21%10 =1 d'où Prod[1]=1  soit Prod=[0 , 0, 0 , 1]
s=s//10=21//10 =2
i = 2
    j=1  s=2+P[2-1+1]*Q[1]=2+P[2]*Q[1]=2+5*3 = 17 
    j=2  s=17+P[2-2+1]*Q[2]=17+P[1]*Q[2]=1+7*8 = 73 
73%10 =3 d'où Prod[2]=3  d'où Prod[0,0,3,1]
s=s//10=73//10 =7
i = 3
     j=1   s=7+P[3-1+1]*Q[1]=7+0*3=7
     j=2 s = 7 + P[3-2+1]*Q[2]=7+5*8=47
     j=3  s = 47 + P[3-3+1]*Q[3] =47+7*0=47
47%10 =7 d'où Prod[2]=7  d'où  Prod[0,7,3,1]
s=s//10=47//10 =4
i=4
      j=1   s=4+P[4-1+1]*Q[1]=4+0*3=4
      j=2   s=4+P[4-2+1]*Q[2]=4*0*8=4
      j=3   s=4+P[4-3+1]*Q[3]=4+5*0=4
      j=4   s=4+P[4-4+1]*Q[4]=4+7*0=4
4%10 =4d'où Prod[2]=4  d'où  Prod[4,7,3,1]
s=s//10=4//10 =0

Il est clair qu'en programmant on peut éviter les lignes j=2,3,4  pour i=4 comme d'ailleurs d'autres
calculs qui précèdent les cas où  i=n+m .

Cordialement.

Dernière modification par hgaruo1951 (07-02-2018 14:18:47)

Hors ligne

#33 07-02-2018 16:51:44

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : divisions de grands nombres

Salut

Même si j'ai minimisé le volume du programme pour effectuer une multiplication et que l'on reconnaisse cela c'est bien :

"Si le coeur du programme peut être compressé sur 5 lignes, au détriment de la clarté et du contrôle de l'algorithme, il y a par ailleurs toutes les instructions préliminaires relatives à la déclaration des constantes, des types et des variables, qui représentent une part non négligeable du code source."

et que cela n'a rien a voir à plusieurs pages

"mais qu'il se réduise à cinq lignes de code, cela ressemble fort à de la prestidigitation !
hgaruo1951 a écrit :
... Pour une division d'un nombre de 3000 chiffres par un nombre de 2000 chiffres (à titre d'exemple ) le programme principal pour effectuer une telle division (si le diviseur a comme chiffre des unité l'un des chiffres 1 , 3 ,7 ,9 et le reste de la division est un zéro )  ne comporte qu'une dizaine de lignes ...
Le programme principal peut se réduire à l'appel d'une procédure
BEGIN
  P1
END;
laquelle peut dissimuler cinq ou dix pages de code source !"

J'affirme que la divisions avec les contraintes citées peut être écrite avec 5 ou 6 lignes de plus que celui pour
effectuer la multiplication . Malheureusement ma méthode ne fonctionne pas dans tous les cas et
donc je suis à la recherche d'un algorithme pour effectuer toutes division , algorithme différent et plus performant
de celui qui traduit les opérations que l'on fait à la main au moyen de la potence.

Cordialement.

Dernière modification par hgaruo1951 (07-02-2018 16:57:45)

Hors ligne

#34 07-02-2018 17:44:35

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 943

Re : divisions de grands nombres

Salut,

J'ai cherché une idée ce matin et je suis tombé sur plusieurs implémentations de l'Algorithme de Knuth...
Je réserve ça pour une autre fois, mais rien ne t'empêche de t'y intéresser.
va sur Google et tape :  Algorithme de Knuth division.
Il y a 5 liens consécutifs en haut de page...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#35 08-02-2018 15:38:26

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : divisions de grands nombres

Bonjour yoshi
je viens de consulter les différentes implémentations de l'algorithme de Knuth , algorithme qui traduit la
division longue qui doit être effectuée en base B au lieu de la faire en base 10 et il est vrai avec une petite
subtilité (je ne sais pas vraiment que c'est le mot mais je garde!) qui se traduit par une certaine
normalisation qui certainement réduit quelque peut  les calculs. Je crois qu'à ce stade de la discussion
je vais appliquer ma méthode qui aura l'avantage de faire une telle division en utilisant que les sommations
et les affectations.
Oui j'affirme que de telles divisions peuvent se faire sans aucune multiplication intermédiaire ni division intermédiaire
ce qui compensera largement  (je le crois !) cette subtilité relative à l'opération de la normalisation de cet algorithme de Knuth.
Merci à vous Messieurs.

Cordialement.

N.B.:
Même la multiplication de grands nombres  peut se faire sans aucune multiplication intermédiaire ce qui réduira
quelque peut le temps de calcul!!!!

Dernière modification par hgaruo1951 (08-02-2018 15:44:04)

Hors ligne

#36 09-02-2018 01:54:43

Wiwaxia
Membre
Lieu : Paris 75013
Inscription : 21-12-2017
Messages : 409

Re : divisions de grands nombres

hgaruo1951 a écrit :

... Oui M. Wiwaxia vous avez parfaitement raison mais ceci dit je peux obtenir le produit d'un nombre de 2000 chiffres par un nombre de 3000 chiffres en une fraction de seconde en utilisant le turbo pascal. Et ce calcul peut se faire (une fois introduit ces deux nombres ) au moyen d'un programme composer de cinq lignes pour le calcul et de trois ligne pour l'affichage ...

hgaruo1951 a écrit :

... Pour toutes ces opérations (je passe sous silence l'addition et la soustraction que tout le monde peut faire) voici comment
je procède pour la multiplication :
   supposons que l'on a à calculer le produit Prod=pq  avec p à n chiffres et q à m chifres . Une fois que l'on a introduit p
sous la forme de vecteurs c'est  à dire
  *  p(i) , i=1 à n+m     où p(i)=0 pour i variant de n+1 à n+m  , p(i) le ième chiffre de p pour i variant de 1 à n
  *  q(j)=0 pour j variant de m+1 à n+m et  q(i) représente le j ème chiffre  du nombre q
       ( dans le deux cas le comptage démarre à partir des chiffres des unités)
on aura comme partie principale de cette multiplication le moyen suivant (adaptable pour tout logiciel de programmation)
    s=0
pour  i variant de 1 à n+m  pour j variant de 1 à i  begin
              s=s+p(i-j+1)*q(j)  ;
              prod(i)=s mod 10 ;
              s=s div 10  ;
             end;

Traduisons donc en Turbo Pascal le pseudo-code qui nous est fourni, en gardant les noms des diverses variables, autant que faire se peut. Cela donne pour l'essentiel


 CONST m = 800; n = 1200;
 TYPE LstB = ARRAY[1..m+n] OF Byte;
 VAR x, y, z: LstB;
 ... / ...
 PROCEDURE CalcP(VAR p, q, Prod: LstB);
   VAR h, i, j, k: Word; s: LongInt;
   BEGIN
     s:= 0;
     FOR i:= 1 TO (m + n) DO
       FOR j:= 1 TO i DO
         BEGIN
           s:= s + p[i - j + 1]*q[j];
           Prod[*]:= s MOD 10;      // Lire * = i  ... Problème de balises
           s:= s DIV 10
         END        
   END;    

Notons au passage les huit lignes de code (au lieu de cinq) résultant de l'indentation indispensable à l'intelligibilité du texte.

On ne tarde pas à s'apercevoir, dès le lancement du programme, que l'algorithme est erroné (par défaut d'une paire de délimiteurs BEGIN ... END) et conduit à des résultats systématiquement faux:
29ntpg7.png

Tout rentre dans l'ordre dès que l'on déplace les deux dernières instructions d'affectation:


 PROCEDURE CalcP(VAR p, q, Prod: LstB);
   VAR h, i, j, k: Word; s: LongInt;
   BEGIN
     s:= 0;
     FOR i:= 1 TO (m + n) DO
       BEGIN
         FOR j:= 1 TO i DO
           BEGIN
             k:= i + 1;          Dec(k, j);
             h:= p[k]*q[j];      Inc(s, h)
           END;
         Prod[i]:= s MOD 10; s:= s DIV 10
       END]
      END;    
 ... / ...
   CalcP(x, y, z);      

2ujgzfc.png

Une simple calculatrice permettait de contrôler la validité du résultat sur des nombres de cinq chiffres.
Pour s'assurer de la fiabilité du code sur les grands nombres, il suffit de vérifier l'identité des deux résultats obtenus en base 100 et 10000; l'algorithme est dans ce cas élémentaire.

Autre aspect concernant le choix des bases: la séquence de quatre bytes (9, 9, 9, 9) correspond à quatre octets; l'entier Word équivalent (9999) n'en occupe que deux, soit un espace mémoire deux fois moindre; d'où l'intérêt de choisir (pour le même algorithme) la base la plus élevée (104), l'avantage devenant décisif pour les très grands nombres, dans le cas du Turbo Pascal 7.

Dernière modification par Wiwaxia (09-02-2018 09:16:38)

Hors ligne

#37 09-02-2018 12:43:46

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : divisions de grands nombres

Bonjour,

Mon programme en turbo pascal n'a rien a voir à ce qui est proposé et pourtant j'ai d’excellents résultats.
Il peut être écrit sans faire appel à des procédures ni à des  k=i+1 , ni à des Dec ni à des Inc  .... Autre chose
il s'exécute sans faire le produit  p(k)*q(j). Ce qui est sur c'est que chacun notera que cela peut se faire
en une demi page et non en "cinq ou dix pages". Mais dans tout cela la multiplication n'est pas véritablement
le but qui était recherché au départ et à partir de maintenant laissant de côté la multiplication et parlant de division
et uniquement de division. Pour toute suggestion sur ce dernier point je serai preneur.   

Cordialement

Hors ligne

#38 09-02-2018 13:53:11

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : divisions de grands nombres

Bonjour,

Mon programme en turbo pascal n'a rien a voir à ce qui est proposé et pourtant j'ai d’excellents résultats.
Il peut être écrit sans faire appel à des procédures ni à des  k=i+1 (ce n'est d'ailleurs pas cela!!!) , ni à des Dec
ni à des Inc  .... Autre chose il s'exécute sans faire le produit  p(k)*q(j). Ce qui est sur c'est que
chacun notera que cela peut se faireen une demi page et non en "cinq ou dix pages". Mais dans tout
cela la multiplication n'est pas véritablement le but qui était recherché au départ et à partir de maintenant
laissant de côté la multiplication et parlant de division et uniquement de division. Pour toute suggestion
sur ce dernier point je serai preneur.   

Cordialement

Dernière modification par hgaruo1951 (09-02-2018 13:53:43)

Hors ligne

#39 10-02-2018 10:35:44

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 943

Re : divisions de grands nombres

Bonjour,

Je ne peux que te proposer de te mettre à Python, à défaut de le télécharger et de l'installer sur ta machine, après quoi je te donne ce que tu veux en Python (j'y ai travaillé ce matin).
N-B : Python est un logiciel libre et gratuit.
Quelques résultats que je dédie :
=========================== RESTART: C:/Python35/division_prolongee.py ===========================
            A DIVISER
Dividende :
37895481257143221546813651965487318837598743

diviseur :
2154687942310579875261

            RESULTATS

quotient :
17587456871599697932255.844260979309410682888

reste :
0.1594191689224132766232


-- Calculs effectués en 0.0 s --

>>>
=========================== RESTART: C:/Python35/division_prolongee.py ===========================
            A DIVISER
Dividende :
19088056365943122940541794220537428621641675395

diviseur :
867361744355209308114990226437388508364626

            RESULTATS

quotient :
22007.30503902441956887970715783412257519213425

reste :
0.426591224561703600238532930895479385695950


-- Calculs effectués en 0.0 s --
>>>
>>>
=========================== RESTART: C:/Python35/division_prolongee.py ===========================
            A DIVISER
Dividende :
15149325619608428682272606395692302090200668950471643737899702268131764198026798223513172814369926907590387917716427555765152074359119952550443100649728847275046311917842127859002059316422275201872005396807204362243444488670604009443350981699616559311016989956581899397656770295836800883042165791856580580092624801442307283756673168497810197489825584280352568841668329872512635276659707158107856677955278970053971666058433279810943392589914842698774633004125487648687187671429202071964365778357626617509645510151686603855116775582693400143070930424092143451985904909854527222107306186237427181783398089176948893361559144966121116647914338500690625105927185540386354829091632580473556727991296578209902841681612331761353874261424212112278807708963154468854611805353981459650818983302783812467952185338798682565369752671277025122255546095434848978234885706727692954189210984970992995769897306476415099263958750446255352775016023980590605010640934094275625429208942285022613340336399144563731434417963069861643623749774638475563275859869562158592989395051605972433233501119980227178885869238413818631319894028945413367399256185248418773797134981134241468517825898640611167746408277977306814471687406808028626139222

diviseur :
26261687981843384155300832335878991119743334191303703370891902150480112681190431889909217925165026602810696101005771121388145209431698138857915893649374936943912461597361806189376944434117955412568342473519617383420226658112429102406129546014974217861740618185596755430597655579813173497804447192849067371953725417231932626005106293867324809787969460249785246759669551249342079541835976260521758157409293222445827959322894182044133044878378835779465969544326399858927294490296914932370412766348282257144926399868882348556023663315283713058037112317040684137529670006123667807193862602773051628996800733711044957651908468456231698430584322869000805614392763778027656472806077465256221791197721417472851593668546587443062341165358356483114958089213136410876156083546899511875533192816773856322422261240987815657569618892972149777474290325722925037207680118780485984082046278069365748784240672347927239

            RESULTATS

quotient :
576860315684287309719165848921384446951659929605648697971787511177015718907006721276028953145061046217843114287427952993966280335664593681653532930292168747939237370183583702467620698991322746330075443115386913927427111785775345483053943599197400584425219107975535119798570956983180914085498588275157212667219372<.>65121774076498257748939813771152239938537822498102546534408536081533079585051196891122635559614687835812120410325682692308386427019007222485379184799751183204172370361099091708664745064075629078575775738550335346325888815950481243009370389445891417536438551304539992909199933132605968494335477411295099275875799828901917794902258936208105738499901501615448994014620540480150108935954427223285011366170121452016680814943024464473342547191596945559239211562981790566954219783282957328747396680770245863899373276503366731247518234557162545707065382389728681536886715390750839640021520087366632261866754363949758091568590898123264089056367999359710890825179593233426831044700658797463305498808681692749100319283901923685046145121775988008707780021445789968950721313634501365231227121675827318666423368234639444282820800308934885024798648531617904309563875931808522868425080968329092399645894028955972445

reste :
0.20738412902336523006172616656245165053340994209120328717410282064133650593741283904916516146092197285218160191503839402153272514434217280441804714725697415626262782619583101739116298573845566218681862235621475598044139470210164437643691596396600362584066585735852571239449494853411561945487122155468616153688859522137542938252477415608260838476524773974815561455744403168109232936978432845684719451518134923210036579199363009923045143074100747674162018006501336727159691952073800449005837732320622211779847087358964239359966399510192918493799540210637117659932636971102858074014731830729798153735321982501711028312961032307629856981773854354633241448939758348708905119502591104556304586679153525012264697202361075943079021479859034500976784964023746512682084748661528795387497212864669425882833806771640487711835748056791727148028914442391423877476734197530158140259349544991286364138479414651070645

longueur Dividende : 1211 chiffres
longueur diviseur : 899 chiffres.
Pour qu'il soit bien visible au quotient, j'ai encadré le . décimal au quotient entre < et >
Je peux rajouter au quotient un nombre de chiffres "à volonté", ici le nb de chiffres du quotient est égal à celui du dividende : c'est un choix...


from math import log
from time import time


start=time()
#Entrée des nombres à diviser, calcul de leurs longueurs et nb de chiffres supp. au quotient
Dividende,diviseur=7**1432+21,3**1883+12
Chiffres_supp=0

start=time()
#longueurs
l_Dvd,l_dvs=len(str(Dividende)),len(str(diviseur))

# Calcul des quotient et reste entiers
q_int,r_int=divmod(Dividende,diviseur)

# calcul des longueurs des quotient et resre
lq_int,lr_int=len(str(q_int)),len(str(r_int))
# calcul du différentiel de longueurs entre Dividende et quotient
Delta_lg=l_Dvd-lq_int

#Ajustement de la longueur du nouveau Dividende et nouvelle division
Dvd_d=r_int*10**(Delta_lg+Chiffres_supp)
q_pv,r_pv=divmod(Dvd_d,diviseur)

# Recherche longueur partie décimale du quotient
lr_pv=len(str(r_pv))
nbzeros_pv=Delta_lg-lr_pv

# Affichage
temps=time()-start
print ("            A DIVISER")
print(" Dividende :")
print (Dividende)
print ("\n diviseur :")
print (diviseur)
print("\n            RESULTATS")
print ("\n quotient :")
print(str(q_int)+"<.>"+str(q_pv))
print ("\n reste :")
print ("0."+"0"*nbzeros_pv+str(r_pv))
print("\n\n-- Calculs effectués en",temps,"s --")
 

[HS]
J'ai écrit une multiplication sur la base du procédé dit de "la multiplication arabe".. : multiplication chiffre par chiffre, séparément sur la base des tables de multiplication, sans retenue pendant les x, mais dans les additions qui suivent...
Je ne peux pas avec Python, lutter en vitesse pure avec un logiciel compilable, et j'ai, et les déclarations diverses,  avec la préparation plus de 5 lignes,comme tu as pu le constater...
Le produit des deux nombres de 1211 chiffres et 899 chiffres prend, avec mon script, 1,9 s hors affichage...

Je vais essayer de l'optimiser, mais je  ne pense pas que cela sera possible, sauf à utiliser l'extension, destinée au calcul scientifique, numpy.
[/HS]

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#40 10-02-2018 12:18:33

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 943

Re : divisions de grands nombres

Re,

Je viens de modifier les lignes du début pour définir Dividende et diviseur, aléatoirement à 3000 et 2000 chiffres : temps de calcul : 0.001 s...

@+


Arx Tarpeia Capitoli proxima...

Hors ligne

#41 10-02-2018 16:55:51

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : divisions de grands nombres

Bonjour yoshi ,

Merci pour tous vos efforts et je suis très satisfait pour ce que vous me proposez et je vais me mettre
à programmer avec Python car les résultats que vous me montrez sont (pour moi!!)  plus que satisfaisants.
Merci encore yoshi .

Cordialement.

Hors ligne

#42 10-02-2018 17:47:39

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 943

Re : divisions de grands nombres

Salut,

Alors, c'est bien...
Pour télécharger Python :
https://www.python.org/downloads/

Attention version 64 bits !

(Les versions 32 bits sont dispo aussi)
Cliquer cette ligne :
Windows x86-64 executable installer     Windows     for AMD64/EM64T/x64, not Itanium processors     bee5746dc6ece6ab49573a9f54b5d0a1     31684744     SIG

Pour apprendre Python, télécharger (gratuit et parfaitement légal) :
https://inforef.be/swi/download/apprendre_python3_5.pdf
Bonne lecture (+ de 300 pages)

Tu risques d'être dérouté et j'avoue que c'est ce qui me dérange avec Python
- le typage  est dynamique : pas de déclarations  de type, mais existent quand même hein... Types : int, str, float
- Pas de begin / end : tout est géré par l'indentation...
- Pas de tableaux, mais des listes... On peut les lire à l'endroit, à l'envers, par tranches, passer d'une liste à un string et réciproquement
- Division avec quotient décimal : /. Avec quotient entier : //. Reste : % (modulo). Puissance : ** --> 2**3 = 8


Sinon, c'est assez amusant : les concepteurs de Python le définissent comme user friendly...

[HS]
j'ai optimisé ma multiplication : de 1,9 s, je suis descendu à 1,4 s : gain de 25 %.
Puisque tu te mets à Python, voilà le code de ma multiplication :


from math import log
from time import time

start=time()
Prod=[]
p,q=7**1432+21,3**1883+12
P,Q=[int(i) for i in str(p)],[int(i) for i in str(q)]
lp,lq=len(P),len(Q)
Q.reverse()
nbc,tot=lp+lq,lp*2
finQ,finR=lq-1,lp+lq-1
Z=[0]*nbc
Res=[Z[0:]for i in range(tot)]

#Je remplis mon tableau
for  i,m, in enumerate(P):
    for c,j in enumerate(range(finQ,-1,-1)):
        Res[i*2][finR-c-i],Res[i*2+1][finR-c-i-1]=divmod(Q[j]*m,10)

# Je somme les colonnes et reporte les retenues
ret,s=0,0
for i in zip(*Res):
    s=ret+sum(i)
    ret,u=divmod(s,10)
    Prod.append(u)
Prod.reverse()
fin=time()

# Affichage
print("Produit calculé par le script :")
print (''.join(str(e) for e in Prod)) # Passage de la liste à la chaîne
print("\nProduit obtenu directement par multiplication :" ) # Pour contrôle}
print (p*q)
print ("\nTemps de calcul hors affichage :",fin-start,"s")
 

@+

Dernière modification par yoshi (10-02-2018 18:36:58)


Arx Tarpeia Capitoli proxima...

Hors ligne

#43 10-02-2018 21:01:16

yoshi
Modo Ferox
Inscription : 20-11-2005
Messages : 16 943

Re : divisions de grands nombres

Re,

A partir de la grille classique, où on inscrit
- le multiplicateur de haut en bas, et le multiplicande normalement (multiplication présentée : 34578 * 273)
- en diagonale montante, en ayant partagé chaque cas en 2 en diagonale, dizaine unité
je me suis vite aperçu que programmer ça allait être (très) coton...
Il m'est alors venu l'idée de remplacer une case par un carré de 2 cases sur 2, chaque chiffre ayant sa case...

Là, j'ai vu que les calculs en diagonale m'obligeaient à calculer les coordonnées des cases : sacrée perte de temps !
Alors, j'ai finalement pensé à remplacer les diagonales par des colonnes...
C'était encore long...
Puis je me suis dit qu'il devait y avoir une fonction pour ça : c'était sum et que ça irait bien plus vite que deux boucles imbriquées, pour sommer case après case (Python est écrit en C).
Mais faire sum([1,2,3,4,5]) c'était simple avec une seule liste...
Mais moi, j'avais une liste de listes (grosso modo l'équivalent d'un tableau à deux dimensions, sauf qu'une liste n'est pas un tableau. Avec des vrais tableaux en Basic, j'avais fait bien compliqué) comme : [[1,2,3],[4,5,6],[7,8,9]]...
Alors, j'ai fouillé les forums...
Et j'ai trouvé comment utiliser sum( ) dans de cas, dont j'ai vérifié l'adaptabilité : présence de retenues...
Ça marchait !...
Sauf que...
Je ne pouvais pas l'employer à cause de l'ordre des colonnes qui suivait l'ordre naturel d'écriture d'un nombre...
Pour les retenues, je devais commencer par la fin et - apparemment - ce n'était pas possible.
Retour à la case départ...
J'ai donc pensé à plusieurs solutions, mais aucune de probante.
Et l'idée m'est venue de modifier la version classique et j'ai mis au point la 2e grille, puis le passage en colonnes...
Et là, j'ai divisé le temps par 2.
Pour l'affichage, j'ai quand même dû renverser l'ordre des éléments de la liste : c'est la méthode reverse().
Et à partir de la nouvelle liste en faire une chaîne...
(Exemple donné pour 34578 * 273)
18021203030614848.jpg
Pour pouvoir calculer, les points sont remplacés par des zéros, qui dans les calculs sont une perte de temps : j sais repérer très précisément leurs positions, mais ces calculs ne me faisaient gagner que 19% de calculs avec les colonnes constituées à partir de la grille classique...
J'ai préféré optimiser autrement le calcul des colonnes : c'est assez court...
Évidemment si je pouvais aussi éviter d'additionner tous les zéros inutiles...

@+

[EDIT]
Du coup, j'ai eu une idée, j'ai remodifié ma grille pour pouvoir sommer en colonnes de droite à gauche et pas le contraire :
je suis descendu à 1,1 s...
Mais un nombre d'un peu plus de 3000 chiffres par un d'un peu plus de 2000 chiffres : 7,1 s au lieu de 8,5 s !
Mais j'ai toujours cette histoire de zéros...

Dernière modification par yoshi (12-02-2018 17:10:55)


Arx Tarpeia Capitoli proxima...

Hors ligne

#44 12-02-2018 17:18:19

hgaruo1951
Membre
Inscription : 13-09-2017
Messages : 104

Re : divisions de grands nombres

Bonjour yoshi,

Je viens de lire votre message et comme je vous l'ai dit je vais me mettre sous Python.
Je vous promets que si ma méthode me donnera un résultat ( décomposition du RSA400 en ses deux
facteurs premiers) je reviendrai et j'afficherai ce résultat à la suite de la présente discussion .
Pour terminer Merci encore.

Cordialment.

Hors ligne

Pied de page des forums