|
|
|
|
T
itre : Mathéeématique et Grands Nombres.A
uteur : Emmanuel PIERRE
Tout ceux qui, un jour, ont eu à rendre un programme, ou pire à faire pour sa propre satisfaction, un programme utilisant des fonctions mathématiques utilisant des grands nombres, se sont peut-être heurtés au problème des limitations de type du Turbo Pascal. Grande nouveauté avec le BP7, le format
COMP, mais les nombres sont encore très limités.Suite à un projet de recherche de grands nombres premiers, qui sont tous positifs, car je ne parlerai que de grands nombres positifs, la première chose que mon binôme à faite, à été d’utiliser les listes, dont il avait l’habitude. Mais tout ceux qui sont habitués à utiliser le Pascal sur des stations VAX/VMS se retrouvent marris devant leurs pauvres PC quand ils s’aperçoivent de la terrible limitation de leur système en ressource dynamique : le Pascal ne désallouant pas après un appel ( j’envoie 2 listes, et j’en renvoie une dans la 1e i.e
. NA := add( NA , NB ), l’ancien NA reste en mémoire ).Dans ce cas-là, que faire ? Passer en mode protégé est une solution, mais quand on utilise des routines asm, tout recalculer c’est la galère... , ou tout bêtement créer de nouvelles fonctions de grands nombres.
C’est donc cette méthode que j’ai choisie pour contourner cet écueil, et dont la seule limitation était la mémoire dynamique du système ( on peut toujours y appliquer le mode protégé ). L’idée est simple, deux tableaux en l’occurrence pour une suite de fibonnacci, tous deux de 32000 cases de
byte, puis créer de nouvelles fonctions d’addition, de soustraction... Avantage immédiat : une case de liste fait 5 byte, une de tableau 1, d’où un gain conséquent de mémoire.Le type est défini juste ici :
type
Numtab = array[1..32000] of byte;
BIGnum = record
t : ^numtab;
s : integer;
end;
Le record Bignum a deux champs, le premier T le pointeur sur tableau de byte, et le deuxième, la taille du nombre contenu dans T, très utile pour optimiser le calcul.
Pour les utiliser, on les crée par :
var NA : BIGnum; (* les définit *)
begin
new(NA.T);(* crée ce nombre, A NE JAMAIS OUBLIER SOUS PEINE DE MORT *)
init_BN(NA);(* on le met à 0 *)
add_c(NA,2); (* on met 2 dans NA, c.f. plus loin... );
release(NA.T);(* détruit NA *)
end;
Voyons les fonctions mathématiques de base :
On initialise en mettant des zéro partout et en mettant la taille à 0 :
procedure init_BN(var ptr:BIGnum);
(* Initialise un grand nombre a zéro *)
var i : integer;
begin
for i := 1 to 32000 do
ptr.t^ [i] := 0;
ptr.s := 0;
end;
Renvoyer le plus grand est souvent nécessaire pour deux Integers :
function max(i,j:integer):integer;
(* Renvoie le plus grand des Integers *)
begin
if i>j then
max := i
else
max := j;
end;
Il faut déjà implémenter une fonction pour savoir si on a affaire à un nombre nul, on sait jamais, mais ça va servir, je vous le promets :
function est_nul(NA:BIGnum):boolean;
begin
est_nul := (NA.s=0) OR ( (NA.s=1) AND (NA.t^[1]=0) )
end;
Première procédure intéressante après l’initialisation, l’addition de base, c’est à dire celle de plus bas niveau, l’addition par une constante inférieure à 10. (C.f. cours de numération ). J’appelle par la suite BN un Big Number, un grand nombre.
procedure add_c(var NA:BIGnum;cst:byte);
var ret : byte; (* la retenue *)
i : integer; (* le compteur *)
c : integer; (* le calcul intermédiaire *)
Begin
ret := 0; (* pas de retenue au départ *)
if not((cst=0) or est_nul(NA)) then (* zéros, rien a traiter *)
for i := 1 to na.s+1 do (* on va de 1 a n+1, en cas de retenue *)
begin
if i>1 then cst := 0; (* idiot, mais utile pour optimiser *)
c := NA.t^[i] + (cst + ret); (* valeur actuelle plus cst si*)
(* premier rang, et retenue si*)
(* il y a lieu *)
ret := 0; (* on l'a utilisée, on la retire *)
if (c>=10) then (* si il y a retenue dans notre calcul *)
begin
ret := 1; (* on la met pour le prochain tour *)
c := c-10; (* on retire de c 10 *)
end;
NA.t^[i] := c;(* on met dans la position du BN, la valeur c*)
if (ret=0) then (* plus de retenue, on peut sortir *)
exit; (* allez, hop on sort, c'est fini *)
end; (* fin du FOR BEGIN *)
if (NA.t^[na.s+1]<>0) then inc(NA.s); (* si le BN a grandi *)
end;
Et maintenant l’addition complète :
procedure add(var NA, NB, ND : BIGnum);
var ret : byte;
i : integer;
c : integer;
Begin
ret := 0; (* pas de retenue *)
if not(est_nul(NB) or est_nul(NA)) then (* des 0, on sort *)
begin
for i := 1 to max(NA.s,NB.s)+1 do(* on calcule au plus grand *)
(* des deux+1 si retenue *)
begin
c := NA.t^[i] + NB.t^[i] + ret;
ret := 0;
if c>=10 then
begin
ret := 1;
c := c - 10;
end;
ND.t^[i] := c;
end;
if (ND.t^[i]<>0) then ND.s := i(* si il y a du monde en n+1 *)
else if (i>1)and(ND.t^[i-1]<>0) then ND.s := i - 1;(* sinon*)
end
else
ND:=NA;
end;
Rien de bien nouveau et pas d’astuces, mais voyons la soustraction d’une constante :
procedure sous_c(var NA : BIGnum;cst : byte);
var ret : byte;
i : integer;
c : integer;
Begin
ret := 0; (* pas de retenue *)
if not est_nul(NA)and(cst<>0) then (* si NA est nul, rien a faire *)
for i := 1 to NA.s do
begin
if i>1 then cst := 0; (* c.f. add_c *)
if (NA.t^[i]<(cst+ret)) and (i<na.s) then
begin (* si on retire plus qu'il n'y a, retenue *)
NA.t^[i] := 10 + NA.t^[i] - ( cst + ret );
ret := 1;
end
else
begin (* sinon simple soustraction, et fin de calcul *)
(* car plus rien a retirer*)
NA.t^[i] := NA.t^[i] - ( ret + cst );
ret := 0;
if (na.s=i) then (* dernière case *)
if (i>0) and (NA.t^[i]=0) then
dec(NA.s); (* si pas
exit;
end
end;
if (NA.t^[i]<>0) then NA.s := i (* si taille inchangée *)
else if (i>1) and (NA.t^[i-1]<>0) then NA.s := i-1;(* sinon *)
end;
Ici une optimisation, renvoie le plus grand, comme on travaille seulement en nombres positifs, donc on soustrait le plus grand au plus petit :
function greater(NA,NB:BIGnum):boolean;
var ret : byte;
i : integer;
c : integer;
Begin
if NA.s>NB.s then (* on commence par regarder la taille *)
greater:=true
else if NA.s<NB.s then
greater:=false
else (* et après comparaison case a case *)
begin
i:=max(na.s,nb.s); (* taille max *)
while (NA.t^[i]=NB.t^[i])and(i>0) do (* boucle tant qu'egaux*)
dec(i); (* sens décroissant, c'est plus rapide *)
if (NA.t^[i]>=NB.t^[i]) then
greater:=true
else
greater:=false;
end;
end;
Et maintenant la soustraction, sous vos applaudissements:
procedure sous(var NA,NB,ND:BIGnum);
var ret : byte;
i : integer;
c : integer;
Begin
ret := 0;
if est_nul(NB) then
ND:=NA
else
for i := 1 to max(na.s,nb.s) do (* le parcours *)
begin
if (NA.t^[i]< (NB.t^[i]+ret) ) then (* A<B+retenue *)
begin
ND.t^[i] := 10 + NA.t^[i] - ( NB.t^[i] + ret );
ret := 1;
end
else (* A>B+retenue *)
begin
ND.t^[i] := NA.t^[i] - ( NB.t^[i] + ret );
ret := 0;
end;
end;
if (ND.t^[i]<>0) then ND.s := i
else if (i>1) and (ND.t^[i-1]<>0) then ND.s := i - 1;
end;
Voyons maintenant d’autres fonctions plus diverses, par exemple pour savoir si il y a reste dans la division de A par B :
function modulozero(var NA,NB:BIGnum):boolean;
var naa : BIGnum;
Begin
new(NAa.t); (* on crée une nouvelle *)
init_BN(NAa); (* on l'initialise *)
add(NA,NAa,NAa); (* on met NA=NAa *)
while greater(NAa,NB) do (* puis on soustrait NB a Naa tant que *)
sous(NAa,NB,NAa); (* Naa>NB *)
modulozero:= not (is_void(NAa));
dispose(NAa.t); (* on nettoie avant de quitter *)
end;
Et maintenant la division par 2, mon cours de numération me dit que diviser un nombre par 2, c’est trouver le nombre de 2 dans celui-ci, je vais donc soustraire (A div 2) fois le nombre 2 pour trouver A div 2 :
procedure div2(var NAA:BIGnum);
var t : BIGnum;
m : longint;
i : integer;
Begin
m := 0;
if (naa.s<=10) and (naa.t^[10]<=2) then
begin (* taille < 10, on peut utiliser des longint, compat. tp6 *)
for i := naa.s downto 1 do
m := m*10 + naa.t^[i]; (* on passe de BN a longint *)
m := m div 2; (* on divise par 2 *)
init_BN(naa); (* on passe de longint a BN *)
i := 0;
while (m<>0) do
begin
inc(i);
naa.t^[i] := m mod 10; (* on prend le dernier *)
m := m div 10; (* et on le retire *)
end;
naa.s := i; (* on ajuste la taille *)
end
else (* on est condamne a des calculs très longs ... *)
begin
new(t.t);
init_BN(t);
repeat
sous_c(NAA,2); (* on retire 2 *)
add_c(t,1); (* et on le comptabilise *)
until (NAA.s<=2) and (NAA.t^[1]<=1) and (NAA.t^[2]=0);
init_BN(NAA);
add(NAA,t,NAA); (* on renvoie t qui est naa div 2 *)
dispose(t.t);
end;
end;
Et après ça, il faut les afficher ces fichus nombres :
procedure show(ptr:BIGnum);
var i : integer;
s : string;
begin
for i := ptr.s downto 1 do
begin
str(ptr.t^[i],s);
affiche(s); (* on affiche un digit, une fonction de votre cru *)
end;
end;
Limitations :
Conclusion
Vous voici tout clef en main, vous n’avez plus qu’à faire du copié-collé ...
L’exemple est le programme FIB.EXE.
Bibliographie
Dr Dobb’s #226 janvier 95, avec un article sur les grands nombres en C++.
Principes fondamentaux de l’informatique, Aho,J.Ullman ed.DUNOD que je vous recommande vivement.
Remerciements
HP Mâd, pour son cours d’assembleur Flash qui me " sert " de modèle,
Murdoc, mon binôme, qui malgré ses défauts n’en est pas moins sympa,
et Ecureuil pour ses conseils, et ses routines, sans qui certains de mes programmes ne seraient pas ce qu’ils sont.
Et toi, hypocrite lecteur, mon ami, mon frère. ( Baudelaire )