+ Répondre à la discussion
Affichage des résultats 1 à 8 sur 8
  1. #1
    Invité de passage
    Inscrit en
    décembre 2012
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : décembre 2012
    Messages : 4
    Points : 0
    Points
    0

    Par défaut Faire son propre BigInt

    Bonjour !

    Je dois coder en Pascal mon propre type Bigint et notamment des procédures permettant d'additionner/soustraire/multiplier/diviser deux Bigint. (je ne sais pas si je suis clair...)

    Pour cela, je prends les deux nombres à additionner/soustraire/etc... sous forme de chaînes que je rentre ensuite dans deux tableaux en les inversant.
    (exemple: 123456=> 0654321 (le zéro correspond au signe du nombre, 0=positif 1=négatif)
    J'ai réussi l'addition et la soustraction mais je n'arrive pas du tout à coder la multiplication, j'ai essayé plusieurs méthodes mais rien ne marche :/ help!

  2. #2
    Expert Confirmé Sénior

    Inscrit en
    août 2006
    Messages
    3 579
    Détails du profil
    Informations forums :
    Inscription : août 2006
    Messages : 3 579
    Points : 4 625
    Points
    4 625

    Par défaut

    Rai,

    Tu fais exactement comme tu calcules à la main.

    En tenant compte du fait qu'une case de ton tableau BigInt correspond pour nous à un chiffre quand on calcule manuellement.

    Ce n'est pas vraiment difficile, mais attention aux bugs, les plus courants étant (en ne prenant en compte que ceux qui sont spécifiques) :
    - oublier de tenir compte du signe des nombres
    - oublier les retenues
    - si on les a prises en compte, oublier de mettre à jour le "chiffre"
    - oublier de mettre à jour la longueur réelle du nombre, si le calcul l'a modifiée
    Il court en ce moment une espèce de grippe, mais elle ne court pas très vite, car on peut l'attraper sans courir.

  3. #3
    Expert Confirmé Sénior
    Avatar de Paul TOTH
    Homme Profil pro
    Freelance
    Inscrit en
    novembre 2002
    Messages
    5 639
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 45
    Localisation : France, Paris (Île de France)

    Informations professionnelles :
    Activité : Freelance
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : novembre 2002
    Messages : 5 639
    Points : 16 167
    Points
    16 167

    Par défaut

    je me suis amusé il y a quelques temps à créer une unité StrMath qui travaille sur des BigInt sous forme de string #0, #1, #2...#255, #1#0 valant 256 évidemment

    et comme le dit droggo ce n'est pas plus compliqué que ce qu'on fait à la main, sauf qu'on travaille en base 256 et non en base 10...et que ce n'est pas très optimisé, il est plus efficace de garder le même principe avec des entiers sur 32 ou 64 bits.

    pour la multiplication et la division, au pire, il suffit de les transformer en addition et soustraction sachant que 3 x 4 = 4 + 4 + 4, et que 12 / 4 donne 12 - 4 - 4 - 4, soit 3 fois -4 avant d'atteindre 0
    Developpez.com: Mes articles, forum FlashPascal
    Entreprise: Execute SARL
    Produits : UPnP, RemoteOffice, FlashPascal
    Embarcadero : Ile de la Réunion, Dephi, C++Builder, RADPHP...TVA à 8,5%

  4. #4
    Invité de passage
    Inscrit en
    décembre 2012
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : décembre 2012
    Messages : 4
    Points : 0
    Points
    0

    Par défaut

    Effectivement j'avais fait une erreur totalement débile au niveau de la retenu..pardon pour la perte de temps ^^

  5. #5
    Invité de passage
    Inscrit en
    décembre 2012
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : décembre 2012
    Messages : 4
    Points : 0
    Points
    0

    Par défaut

    Bon finalement je n'y arrive toujours pas
    Code :
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    procedure multiplication(nbr1,nbr2:Bigint;var resultat:bigint);
    var temp1,temp2:Bigint; i,j,l,m,,res,retenu:integer;
    begin
    setlength(resultat,taille1+taille2+1);
    temp1:=nbr1;
    temp2:=nbr2;
    for l:=1 to length(resultat)-1 do resultat[l]:=0;
    for j:=1 to length(resultat)-1 do 
    if nbr1[0]=nbr2[0] then resultat[0]:=0 else resultat[0]:=1;
    for i:=1 to length(temp1)+1 do 
    	begin 
    	retenu:=0;
    	for j:=1 to length(temp2) do
    		begin
    		res:=(temp1[i]*temp2[j]+retenu);
    		if res>9 then begin resultat[j+i-1]:=(resultat[j+i-1]+res)mod 10; retenu:= res div 10; end else begin resultat[j+i-1]:=res; retenu:=0; end;//temp1[j+i-1] pour décaler lorsque l'on multiplie par 10/100/etc..
    		end;
    	end;
    end;
    J'ai un problème de retenue sur l'addition des valeurs à la case du résultat et je ne vois pas ce qui cloche, les résultats sont très proches mais faux...

  6. #6
    Membre chevronné
    Avatar de EpiTouille
    Homme Profil pro
    Étudiant
    Inscrit en
    mai 2009
    Messages
    332
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France

    Informations professionnelles :
    Activité : Étudiant

    Informations forums :
    Inscription : mai 2009
    Messages : 332
    Points : 721
    Points
    721

    Par défaut

    On a eu un projet qui ressemble à ça en c

    Tu doit vraiment poser ton calcul à main et réussir à le traduire en algo.

  7. #7
    Invité de passage
    Inscrit en
    décembre 2012
    Messages
    4
    Détails du profil
    Informations forums :
    Inscription : décembre 2012
    Messages : 4
    Points : 0
    Points
    0

    Par défaut

    J'ai tout repris bien proprement et effectivement ça marche manque plus que la division

  8. #8
    Rédacteur
    Avatar de darrylsite
    Inscrit en
    juillet 2007
    Messages
    1 300
    Détails du profil
    Informations forums :
    Inscription : juillet 2007
    Messages : 1 300
    Points : 2 210
    Points
    2 210

    Par défaut Unité BigInt pour la cryptographie RSA

    Salut,

    Encore dans l'esprit de Noël, je partage le code source d'une unité BigInt que j'ai codée pendant "mes ages de folie" pour faire de la cryptographie RSA sous Turbo Pascal.

    L'unité comprend les opérations suivantes :

    Code :
    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
     
    unit pbigint;
    {operations usuelles sur des entiers  pouvant atteindre 300 chiffres:bigint
     Unité developpée par KPIZINGUI DARRYL
     24 novembre 2007}
    interface
     
     const maxbig=200;
           basemax=200;
     type bigint=record
                   t:array[1..maxbig] of -1..9;
                   s:shortint;
                   end;
          tbase=array[1..basemax] of bigint;
          tbasel=array[1..basemax] of integer;
    {----------------------------------------------}
    procedure  init(var b:bigint); {initialise a … 0}
    procedure breadln(var a:bigint);{lecture au clavier}
    procedure bwriteln(a:bigint);{ecriture sur stdout}
    function comp(a,b:bigint):integer; {compare a et b:0 si a=b;1 si b<a;-1 sinon}
    procedure plus(a,b:bigint;var c:bigint); {addition comme on le fait au primaire}
    procedure moins(a,b:bigint;var c:bigint); {soustraction}
    procedure div2(a:bigint;var q:bigint);{division par 2}
    procedure mult2(a:bigint;var c:bigint); {multiplication par 2}
    procedure conv(a:longint;var c:bigint); {convertit un longint en bigint}
    procedure prod(x,y:bigint;var c:bigint);{multiplication comme on le fait au primaire}
    procedure babs(a:bigint;var c:bigint); {valeur absolue}
    procedure bdiv(a,b:bigint;var c:bigint);{division entiere}
    procedure bmod(a,b:bigint;var c:bigint);{reste d' une division euclidienne}
    procedure prodmod(x,y,t:bigint;var c:bigint);{multiplication modulo n}
    procedure brandom(n:integer;var c:bigint);{rend un nombre au hazard de n chiffres}
    procedure expo(x,n:bigint;var c:bigint);{elevation a la puissance n}
    function premier(a:bigint):boolean;{determine si un nombre est premier}
    procedure euclide(a,b:bigint;var u1,v1,c:bigint);{algorithme d' euclide etendu; c est le reste}
    procedure expomod(a,n,b:bigint;var c:bigint); {puissance modulo}
    procedure bfwriteln(var f:text;a:bigint);{ecriture de a dans le fichier f}
    procedure bfreadln(var f:text;var a:bigint);{lecture d' un bigint dans le fihier f}
    procedure tobasex(a,b:bigint;var t:tbase);{conversion de a en base b}
    procedure tobase10(t:tbasel;b:bigint;var c:bigint);{conversion en base b}
    function bigtolong(a:bigint):longint;{convertit un bigint en longint}
    type str100=string[20];
    Fichiers attachés Fichiers attachés

Liens sociaux

Règles de messages

  • Vous ne pouvez pas créer de nouvelles discussions
  • Vous ne pouvez pas envoyer des réponses
  • Vous ne pouvez pas envoyer des pièces jointes
  • Vous ne pouvez pas modifier vos messages
  •