Faire son propre BigInt

Version imprimable

11/12/2012, 22h08
Shabala

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!
11/12/2012, 23h41
droggo

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
12/12/2012, 06h05
Paul TOTH

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
12/12/2012, 07h55
Shabala

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

Bon finalement je n'y arrive toujours pas :cry:

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

12/12/2012, 22h12
EpiTouille

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

Tu doit vraiment poser ton calcul à main et réussir à le traduire en algo.
13/12/2012, 16h21
Shabala

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

1 pièce(s) jointe(s)

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