Référence du fichier grdnb.h

Contient les prototypes des fonctions et structures permettant de générer et travailler avec des grands nombres. Plus de détails...

Aller au code source de ce fichier.

Classes
struct	GRDNB
	Objet représentant un grand nombre, sa taille et son signe. Plus de détails...

Fonctions
GRDNB	creerGRDNB (int taille)
	Crée un grand nombre. Plus de détails...
GRDNB	diveuclidedeux (GRDNB a, GRDNB b, GRDNB *quotient)
GRDNB	str2grdnb (char *chaine)
	Convertit un nombre écrit dans une chaine de caractère en GRDNB. Plus de détails...
int	divisible (GRDNB e, GRDNB phi_n, int base)
int	egal (GRDNB a, GRDNB b)
	Permet de savoir si deux GRDNB sont égaux. Plus de détails...
void	affectation (GRDNB *a, GRDNB b)
	Permet de faire a = b sans perte de mémoire. Plus de détails...
int	tailleBase2 (GRDNB a)
	Permet de connaitre la taille en base 2 d'un GRDNB écrit en base 10. Plus de détails...
int	tailleIdentique (GRDNB a, GRDNB b, GRDNB *acopie, GRDNB *bcopie)
	Permet de mettre deux grands nombres à la même taille sans les modifier. Plus de détails...
GRDNB	somme (GRDNB a, GRDNB b, int base)
	Permet d'additionner deux GRDNB positifs. Plus de détails...
GRDNB	expomodrap (GRDNB message, GRDNB e, GRDNB n, int base)
	Permet de calculer message^e = resultat mod[n] dans une base donnée. Plus de détails...
GRDNB	sous (GRDNB a, GRDNB b, int base)
	Permet d'additionner deux GRDNB positifs avec a > b. Plus de détails...
GRDNB	soustraction (GRDNB a, GRDNB b, int base)
	Permet de faire a - b, peu importe leur signe et on peut avoir b > a. Plus de détails...
void	copie (GRDNB a, GRDNB *acopie)
GRDNB	b2Tob10 (GRDNB a)
	Permet de convertir un GRDNB de la base 2 à la base 10. Plus de détails...
int	sontpremiers (GRDNB a, GRDNB b, int base)
GRDNB	addition (GRDNB a, GRDNB b, int base)
	Permet de faire a - b, peu importe leur signe et on peut avoir b > a. Plus de détails...
void	supprimezero (GRDNB *a)
	Permet de supprimer les zéros superflus au début d'un GRDNB. Plus de détails...
int	vraishiftdroite (GRDNB *a)
	Permet de supprimer la dernière case du tableau de a. Plus de détails...
GRDNB	mulunique (int a, int b, int base)
	Permet de multiplier deux entiers et de renvoyer le résultat sous forme de GRDNB. Plus de détails...
char *	GRDNBtoSTR (GRDNB a)
	Transforme un grand nombre en chaine de caractères. Plus de détails...
GRDNB	b10Tob2 (GRDNB a, int taille)
	Permet de convertir un GRDNB de la base 10 à la base 2. Plus de détails...
GRDNB	euclideetendu (GRDNB dividende, GRDNB diviseur, int base, GRDNB *u, GRDNB *v)
	Trouve le pgcd de deux entiers a et b et le couple(u,v) tel que au + bv = PGCD(a,b) Plus de détails...
GRDNB	mulnaive (GRDNB a, GRDNB b, int base)
	Permet de faire la multiplication entre deux GRDNB dans une base donnée. Plus de détails...
GRDNB	div2 (GRDNB a)
	Permet de diviser (entièrement) rapidement un nombre en base 10 par 2. Plus de détails...
int	isMulDeux (GRDNB a)
	Permet de savoir si un nombre est divisible par 2. Plus de détails...
GRDNB	IntToGRDNB (int a, int base)
	Transforme un int en GRDNB dans une base donnée. Plus de détails...
GRDNB	diveuclide (GRDNB a, GRDNB b, int base, GRDNB *quotient)
	Permet d'exprimer a sous la forme a = b * quotient + retour, avec retour < b Plus de détails...
int	vraishiftgauche (GRDNB *a)
	Permet d'ajouter une case à 0 à la fin du tableau de a. Plus de détails...
GRDNB	sousnombre (GRDNB a, int debut, int fin)
	Recrée un autre nombre à partir d'un autre nombre et d'une position de début (inclue) et de fin (exclue) Plus de détails...
int	ismax (GRDNB a, GRDNB b)
	Permet de savoir si a >= b. Plus de détails...
GRDNB	PuissanceRapide (GRDNB a, GRDNB puissance, int base)
	Calcule a^puissance dans la base spécifiée. Plus de détails...
void	afficher (char *chaine, GRDNB a)
	Affiche dans la console un GRDNB précédé de son signe et d'une chaine de caractère, et suivi d'un retour à la ligne. Plus de détails...
int	shiftdroite (GRDNB *a)
	Permet d'ajouter une case valant 0 à gauche d'un GRDNB. Plus de détails...
int	shiftgauche (GRDNB *a)
	Permet de supprimer la case la plus à gauche du tableau d'un GRDNB. Plus de détails...
void	echanger (int *tableau, int i, int j)
	Echange deux cases dans un tableau d'entiers. Plus de détails...
GRDNB	un ()
	Crée un grand nombre valant 1. Plus de détails...
int	isBase2 (GRDNB a)
	Permet de savoir si le tableau d'un GRDNB ne comprend que des 0 ou des 1. Plus de détails...
GRDNB	modulo (GRDNB a, GRDNB b, int base)
	Permet d'exprimer a sous la forme a = b * quotient + retour, avec retour < b Plus de détails...

Description détaillée

Contient les prototypes des fonctions et structures permettant de générer et travailler avec des grands nombres.

Auteur

I. Laruelle / A. Masciulli - UTT NF05 A18

Documentation des fonctions

addition()

GRDNB addition	(	GRDNB	a,
		GRDNB	b,
		int	base
	)

Permet de faire a - b, peu importe leur signe et on peut avoir b > a.

Paramètres

[in]	a	Un GRDNB
[in]	b	Un GRDNB
[in]	base	La base de a, b et du GRDNB renvoyé.

Renvoie

Un GRDNB : a + b.

La fonction somme(GRDNB a, GRDNB b, int base) ne peut traiter que deux nombres positifs. Il faut donc faire une fonction qui va adapter les appels selon tous les cas possibles.

• Si a positif, b négatif, on renvoie |a| - |b|
• Si b positif, a négatif, on renvoie |b| - |a|
• Si a et b négatifs, on renvoie -1 * (|a| + |b|)
• Sinon a et b sont positifs et on renvoie a + b

affectation()

void affectation	(	GRDNB *	a,
		GRDNB	b
	)

Permet de faire a = b sans perte de mémoire.

Paramètres

[in,out]	a	Un pointeur sur le GRDNB qui va recevoir l'affectation.
[in]	b	Le GRDNB qui va être affecté.

• Si on a une boucle et que l'on a l'instruction
  a = soustraction(a,b,base);
  A chaque tour de boucle, la valeur de l'adresse du tableau de a va changer, mais les précédents tableaux ne seront pas libérés.
  Pour éviter cela, on libère le tableau de a avant le calcul.
  
• Problème : si on fait :
  free(a.tableau);
  a = soustraction(a,b,base);
  Un incident se produira, car on a besoin du tableau de a pour faire la soustraction !
• Il faut donc coder une fonction affectation qui s'appellera comme suit :
  affectation(&a,soustraction(a,b,base));
  Le code s'exécute de droite à gauche.
  En arrivant dans la fonction, la soustraction est déjà effectuée, on peut donc libérer le tableau de a.
• Une autre question s'est posée :
  L'instruction *a=b peut laisser perplexe, car ce "b" est le b interne à la fonction, et effacé à la fin de celle-ci.
  Or, quand on fait *a = b, C copie le contenu de b dans a (et une vraie copie). La valeur du tableau de b sera celle de a, ainsi que pour le signe...
  Donc même si b est effacé, les valeurs seront sauvegardées dans a. De plus, le tableau de b étant alloué dynamiquement, il est conservé sur la même adresse tant qu'il n'est pas libéré manuellement.

afficher()

void afficher	(	char *	chaine,
		GRDNB	a
	)

Affiche dans la console un GRDNB précédé de son signe et d'une chaine de caractère, et suivi d'un retour à la ligne.

Paramètres

[in]	chaine	Une chaine de carctère qui sera affichée
[in]	a	Le GRDNB à afficher.

b10Tob2()

GRDNB b10Tob2	(	GRDNB	a,
		int	taille
	)

Permet de convertir un GRDNB de la base 10 à la base 2.

Paramètres

[in]	a	Le GRDNB à convertir.
[in]	taille	La taille du nombre en base 2. Si taille = 0, on calcule la taille dans la fonction.

Renvoie

Un GRDNB : a en base 2.

b2Tob10()

GRDNB b2Tob10

(

GRDNB

a

)

Permet de convertir un GRDNB de la base 2 à la base 10.

Paramètres

[in]

a

Le GRDNB à convertir.

Renvoie

Un GRDNB : a en base 10.

On parcourt le tableau en base 2, et on ajoute au nouveau nombre à chaque 1 la puissance de deux correspondante.
Ex : "1011" = 1 * 2^0 + 1 * 2^1 + 1 * 2^3

copie()

void copie	(	GRDNB	a,
		GRDNB *	acopie
	)

Paramètres

[in]	a	Le GRDNB à copier.
[out]	acopie	Le pointeur sur le GRDNB qui va contenir la copie.

Note

Pourquoi ne pas faire directement acopie = a ?
Si on fait free(acopie.tableau), on libérera le tableau de a aussi. Cette fonction permet de modifier acopie sans modifier a.

On crée un grand nombre ayant une taille identique à a.
On copie case par case de a vers acopie, ainsi que le signe.

creerGRDNB()

GRDNB creerGRDNB

(

int

taille

)

Crée un grand nombre.

Paramètres

[in]

taille

La taille du tableau du GRDNB à créer.

Renvoie

Un GRDNB dont chaque case du tableau alloué dynamiquement vaut 0.
Le signe vaut 1.
Indicemax vaut taille.

div2()

GRDNB div2

(

GRDNB

a

)

Permet de diviser (entièrement) rapidement un nombre en base 10 par 2.

Paramètres

[in]

a

Le GRDNB a diviser

Renvoie

a/2 sous la forme d'un GRDNB

On divise le chiffre des unités par 2.
Ensuite pour chaque case en partant de la case à gauche de celle des unités, il faut regarder si le chiffre est pair.
S'il est pair, on divise par 2 directement.
Sinon, on divise par 2 et on ajoute 5 à la case de droite.

diveuclide()

GRDNB diveuclide	(	GRDNB	a,
		GRDNB	b,
		int	base,
		GRDNB *	quotient
	)

Permet d'exprimer a sous la forme a = b * quotient + retour, avec retour < b

Paramètres

[in]	a	Un GRDNB positif
[in]	b	Un GRDNB positif différent de zéro.
[in]	base	La base dans laquelle a,b, le quotient et le reste sont exprimés.
[in]	quotient	L'adresse pointant sur le GRDNB du quotient.

Renvoie

Le reste sous forme de GRDNB

Note

Si seul le reste vous intéresse, allez sur GRDNB modulo(GRDNB a, GRDNB b, int base)

On regarde si des cas simples se présentent, en effet :

• Si l'on veut a/1, on a a = 1*a + 0. (quotient = a, reste = 0)
• Si l'on veut a/a, on a a = a*1 + 0. (quotient = 1, reste = 0)
• Si l'on veut a/b et b > a, on a a = b*0 + a. (quotient = 0, reste = a).

Sinon on determine la taille maximale du quotient (taille de a - taille de b + 1).

On regarde ensuite combien de fois a peut contenir la puissance maximale du quotient dans la base correspondante.
Tant que a > b * puissancemax, on diminue a : a = a - b * puissancemax et on incrémente autant de fois la case du quotient correspondante.
On diminue la valeur de a autant que possible.
On décrémente la taille pour avoir la puissance inférieure et on recommence tant que a >= b.
Il est possible que la première case du quotient soit nulle, on la supprime si c'est le cas.
Le reste, c'est le a restant quand on a a < b.

Exemple : 520 / 3
Le quotient sera au maximum 999 (donc de taille 3). En effet, on peut avoir (au pire), avec des nombres de cette taille, 999 / 1 (le quotient sera 999 donc bien de taille 3).

• On calcule 10^2 (la puissance de la case 0 du quotient) : 100. On multiplie par b donc on a 3*100 = 300.
  On ne peut soustraire qu'une seule fois 300 dans 520, donc a a = 520 - 1 * 300 = 220. On a donc 1 fois quotient.tableau[0]++ donc la case 0 du quotient vaut donc 1.
  On a toujours a >= b, on continue.
• On calcule 10^1 = 10. On multiplie par b : 3*10 = 30.
  On peut peut soustraire 7 fois 30 dans 220, donc on a a = 220 - 7*30 = 10. On a donc 7 fois quotient.tableau[1]++ donc la case 1 du quotient vaut donc 7.
  On a toujours a >= b, on continue.
• On calcule 10^0 = 1. On multiplie par b : 3 * 1 = 3.
  On peut peut soustraire 3 fois 3 dans 10, donc on a a = 10 - 3*3 = 1. On a donc 3 fois quotient.tableau[2]++ donc la case 2 du quotient vaut donc 3.
  On n'a plus a >= b, on s'arrête.
  Le reste vaut la valeur de a, c'est-à-dire 1.

On a bien 520 = 3 * 173 + 1

echanger()

void echanger	(	int *	tableau,
		int	i,
		int	j
	)

Echange deux cases dans un tableau d'entiers.

Paramètres

[in,out]	Un	tableau d'entiers qui verra deux de ses cases permutées
[in]	L'indice	i < taille du tableau
[in]	l'indice	j < taille du tableau

egal()

int egal	(	GRDNB	a,
		GRDNB	b
	)

Permet de savoir si deux GRDNB sont égaux.

Avertissement

Le bit de poids fort de a et de b doit toujours être différent de zéro. Ex : "124" != "00124", car taille 3 et taille 5.
Les deux nombres doivent être dans la même base.

Paramètres

[in]	a	Un GRDNB à comparer avec b.
[in]	b	Un GRDNB à comparer avec a.

Renvoie

Un entier : 1 si a et b sont égaux
0 sinon.

Le programme regarde déjà s'il y a une différence de taille entre a et b, si oui les nombres ne peuvent pas être égaux.
Ensuite, on lit case par case. Si pour un même indice, la case de a est différente de celle de b, alors les nombres ne sont pas égaux.
Si on a parcouru toutes les cases sans trouver de différences, alors les nombres a et b sont égaux.
Nous aurions pu traiter le cas "124" == "00124", en supprimant les zéros devant à chaque fois, mais cela aurait nécessité de faire une copie, et aurait allongé le temps d'exécution.

euclideetendu()

GRDNB euclideetendu	(	GRDNB	a,
		GRDNB	b,
		int	base,
		GRDNB *	u,
		GRDNB *	v
	)

Trouve le pgcd de deux entiers a et b et le couple(u,v) tel que au + bv = PGCD(a,b)

Paramètres

[in]	a	Un GRDNB
[in]	b	Un GRDNB tel que b < a
[in]	base	Un entier précisant la base de a, de b, de u, de v ainsi que du PGCD retourné.
[out]	u	Un pointeur sur le GRDNB recevant l'un des deux coefficients de Bézout.
[out]	v	Un pointeur sur le GRDNB recevant l'un des deux coefficients de Bézout. Ce coefficient sera positif.

Renvoie

Un GRDNB r le pgcd de a et b, un entier Pour a>b, on commence par faire la division euclidienne de a par b, on obtient un quotient q et un reste r.
On obtient 1 * a - q * b = r (1)
u prend la valeur 1 et v la valeur -q.

• On fait ensuite la division euclidienne de b par r, c'est-à-dire que le diviseur devient le dividende et le reste devient le diviseur.
• On trouve un nouveau reste et un nouveau quotient tels que 1 * b – q’r = r’ et d’après (1), on a 1 * b – q’(a - qb) = r’.
• On a des nouvelles valeurs pour u = -q’et v = 1+qq’. On répète ce schéma jusqu’à obtenir un reste de 0. Le PGCD est le dernier reste différent de 0 obtenu. u et v sont sommées à chaque tour de boucle suivant les quotients et restes obtenus par division euclidienne.

On adapte la valeur de v pour que v soit positif en faisant (k = 1):

• v = v + k*a
• u = u - k*b On incrémente k tant que v est négatif.

expomodrap()

GRDNB expomodrap	(	GRDNB	message,
		GRDNB	e,
		GRDNB	n,
		int	base
	)

Permet de calculer message^e = resultat mod[n] dans une base donnée.

Paramètres

[in]	message	Un GRDNB positif qui sera élevé à la puissance e
[in]	e	Un GRDNB positif qui sera l'exposant de message.
[in]	n	Le GRDNB positif qui modulera le résultat de message^e
[in]	base	L'entier correspondant la base de message, e, n et du résultat renvoyé.

Renvoie

Un GRDNB resultat tel que message^e = resultat mod[n]

L'exponentiation modulaire rapide repose sur le principe suivant :
a*b mod n = (a mod n) * (b mod n)

Si on écrit l'exposant en binaire, on a message ^ e = produit(k=0, k < nbbits(exposant), (message^2k) ^ exposant.tableau[k]) On a donc resultat = produit(k=0, k < nbbits(exposant), (message^2k) ^ exposant.tableau[k]) mod n On fait donc, pour chaque bit de e, resultat = (resultat * message^((1 + le bit de e en cours)%2)) % n puis message = message * (message)

En pratique :
On pose resultat = 1. Tant que l'exposant n'est pas nul :

• Si l'exposant n'est pas un multiple de 2 (c'est-à-dire son écriture binaire comporte 1 pour les unités), on a resultat = (resultat * message) % n
• Sinon on ne touche pas au résultat, car son écriture binaire comporte un 0 pour les unités.
• Dans tous les cas, on fait message = (message * message) % n et exposant = exposant / 2 (division entière) pour passer au bit suivant de l'exposant

GRDNBtoSTR()

char * GRDNBtoSTR

(

GRDNB

a

)

Transforme un grand nombre en chaine de caractères.

Paramètres

[in]

a

Le GRDNB a convertir, base <= 10

Renvoie

Le GRDNB sous forme de chaine de caractères.

On sait que '0' s'écrit 48 en ASCII, '1' s'écrit 49...
Il suffit de prendre chaque chiffre et lui ajouter 48 pour obtenir son code ASCII.
On ajoute '\0' à la fin de la chaine nouvellement créée.

IntToGRDNB()

GRDNB IntToGRDNB	(	int	a,
		int	base
	)

Transforme un int en GRDNB dans une base donnée.

Paramètres

[in]	a	Le int à convertir.
[in]	base	Doit être > 0.

Renvoie

Le GRDNB comprenant a dans la base donnée.

Pour savoir quelle est la taille du nombre dans une base donnée, il suffit de compter le nombre de divisions entières successives possibles.

On remplit le tableau du nouveau GRDNB à l'envers (des unités vers les bits de poids fort)
Pour récupérer le caractère des unités, il faut récupérer le reste de la division de a par 10.
On divise a par 10 pour faire passer le chiffre des dizaines au chiffre des unités.
On répéte ça pour remplir le tableau de GRDNB.

isBase2()

int isBase2

(

GRDNB

a

)

Permet de savoir si le tableau d'un GRDNB ne comprend que des 0 ou des 1.

Paramètres

[in]

a

Le GRDNB à tester.

Renvoie

Un entier valant
1 si le nombre ne s'écrit qu'avec des un et des zéros
0 sinon

On parcourt case par case, et dès que l'on trouve un chiffre différent de 0 ou 1, on renvoie 0.
Si on a atteint la fin du nombre, on renvoie 1.

ismax()

int ismax	(	GRDNB	a,
		GRDNB	b
	)

Permet de savoir si a >= b.

Avertissement

Le bit de poids fort de a et de b doit toujours être différent de zéro. Ex : ismax("124","0025") = 0, car taille 3 et taille 4.
Les deux nombres doivent être dans la même base.

Paramètres

[in]	a	Un GRDNB positif à tester.
[in]	b	Un GRDNB positif à tester.

Renvoie

Un int: si a >= b sinon.

• Si la taille de a est plus grande que celle de b, on sait tout de suite que a >= b.
• Sinon on regarde pour chaque indice.
  • Si, pour un indice donné, une case de b est strictement plus grande que celle de a, alors on retourne 0.
  • Si, pour un indice donné, une case de a est strictement plus grande que celle de b, alors on retourne 1.
• Si on a parcouru tout le tableau sans apercevoir de différence, alors a = b donc a >= b donc on renvoie 1.

isMulDeux()

int isMulDeux

(

GRDNB

a

)

Permet de savoir si un nombre est divisible par 2.

Paramètres

[in]

a

Le GRDNB à tester.

Renvoie

1 si le nombre est divisible par 2, 0 sinon.

Il suffit de regarder le chiffre des unités. Si celui-ci est pair (son reste dans la division par 2 est 0), le nombre est divisible par deux, peu importe la base.

modulo()

GRDNB modulo	(	GRDNB	a,
		GRDNB	b,
		int	base
	)

Permet d'exprimer a sous la forme a = b * quotient + retour, avec retour < b

Paramètres

[in]	a	Un GRDNB positif
[in]	b	Un GRDNB positif différent de zéro.
[in]	base	La base dans laquelle a, b et le reste sont exprimés.

Renvoie

Le reste sous forme de GRDNB

Note

Si avoir le quotient et le reste vous intéresse, allez sur GRDNB diveuclide(GRDNB a, GRDNB b, int base, GRDNB *quotient)

On regarde si des cas simples se présentent, en effet :

• Si l'on veut a/1, on a a = 1*a + 0. (reste = 0)
• Si l'on veut a/a, on a a = a*1 + 0. (reste = 0)
• Si l'on veut a/b et b > a, on a a = b*0 + a. (reste = a).

Sinon on determine la taille maximale du quotient (taille de a - taille de b + 1).

On regarde ensuite combien de fois a peut contenir la puissance maximale du quotient dans la base correspondante.
Tant que a > b * puissancemax, on diminue a : a = a - b * puissancemax
On diminue la valeur de a autant que possible.
On décrémente la taille pour avoir la puissance inférieure et on recommence tant que a >= b.
Le reste, c'est le a restant quand on a a < b.

Exemple : 520 / 3
Le quotient sera au maximum 999 (donc de taille 3). En effet, on peut avoir (au pire), avec des nombres de cette taille, 999 / 1 (le quotient sera 999 donc bien de taille 3).

• On calcule 10^2 (la puissance de la case 0 du quotient) : 100. On multiplie par b donc on a 3*100 = 300.
  On ne peut soustraire qu'une seule fois 300 dans 520, donc a a = 520 - 1 * 300 = 220.
  On a toujours a >= b, on continue.
• On calcule 10^1 = 10. On multiplie par b : 3*10 = 30.
  On peut peut soustraire 7 fois 30 dans 220, donc on a a = 220 - 7*30 = 10.
  On a toujours a >= b, on continue.
• On calcule 10^0 = 1. On multiplie par b : 3 * 1 = 3.
  On peut peut soustraire 3 fois 3 dans 10, donc on a a = 10 - 3*3 = 1.
  On n'a plus a >= b, on s'arrête.
  Le reste vaut la valeur de a, c'est-à-dire 1.

On a bien 520 = 3 * X + 1

mulnaive()

GRDNB mulnaive	(	GRDNB	a,
		GRDNB	b,
		int	base
	)

Permet de faire la multiplication entre deux GRDNB dans une base donnée.

Paramètres

[in]	a	Un GRDNB
[in]	b	Un GRDNB

Renvoie

Un GRDNB : a * b

Algorithme de multiplication naive.

• Pour la base 2:
  111
  
  • 10
    = 0 * 111 + (1 * 111 << 1).
    Ce qui est pratique en base 2, c'est que l'on multiplie soit par zéro, soit par un. On ne fait donc pas de multiplication, mais juste des additions.
    Pour un indice donné de b, si cela vaut 1, on additionne a au résultat décalé par rapport à la position de b.
• Pour une autre base :
  On met les nombres à la même taille.
  
  • On fait varier l'indice de a et on fixe l'indice de b
  • Pour chaque indice de a on forme la multiplication unique de la case de a par celle de b.
    
  • On décale ce résultat en fonction de la position de l'indice de a et on l'ajoute à la ligne intermédiaire. On décale ligne en fonction de l'indice de b en cours la ligne intermédiaire. On ajoute cette ligne au résultat et on recommence jusqu'à avoir parcouru tout le tableau de b.

mulunique()

GRDNB mulunique	(	int	a,
		int	b,
		int	base
	)

Permet de multiplier deux entiers et de renvoyer le résultat sous forme de GRDNB.

Paramètres

[in]	a	Un entier a < base.
[in]	b	Un entier b < base.
[in]	base	base > 0. La base dans laquelle sont écrits a et b et sera écrit le résultat

Renvoie

Un GRDNB de taille au plus 2 comprenant le résultat de a*b dans la base spécifiée.

On fait a*b, si le résultat est supérieur à la base, alors on a besoin de deux cases.
La case 0 comprendra (a*b)/base et la case 1 (a*b)base.
En effet : (a*b) = (a*b)/ base * base^1 + (a*b)base * base^0.

PuissanceRapide()

GRDNB PuissanceRapide	(	GRDNB	a,
		GRDNB	puissance,
		int	base
	)

Calcule a^puissance dans la base spécifiée.

Paramètres

[in]	a	Le GRDNB positif que l'on veut multiplier.
[in]	puissance	L'exposant positif en base 10 ou 2 sous forme de GRDNB.
[in]	base	La base de a et du résultat (10 ou 2)

Renvoie

Un GRDNB valant a^puissance dans la base précisée

a^n = a * a * a * ... * a (n fois) : n multiplications

Le principe :

• a^(2k) = a^k * a^k = (a*a)^k. On a juste à calculer une seule fois a^k
  
• a^(2k+1) = a * a^(2k).

Exemple : a^5 = a * (a^4) = a * (a^2)^2 = a * (a*a)^2 = 3 multiplications au lieu de 5.

Le programme regarde si la puissance est égale à 1

• Si oui, il renvoie a.
• Sinon il regarde si la puissance est paire, si oui il renvoie (a*a)^(puissance/2)
• Si la puissance est impaire, il renvoie a * (a*a)^(puissance/2)

Bien que cette fonction soit récursive, une attention particulière a été apportée à la gestion de la mémoire.

shiftdroite()

int shiftdroite

(

GRDNB *

a

)

Permet d'ajouter une case valant 0 à gauche d'un GRDNB.

Paramètres

[in,out]

a

Un pointeur sur le GRDNB à modifier

Avertissement

Cette fonction N'EST PAS équivalente à a >> 1, voir int vraishiftdroite(GRDNB *a).

Renvoie

Le nouvel indicemax.

On ajoute une case à la fin du tableau, puis on fait descendre la dernière case à l'indice 0 par échanges successifs.

shiftgauche()

int shiftgauche

(

GRDNB *

a

)

Permet de supprimer la case la plus à gauche du tableau d'un GRDNB.

Paramètres

[in,out]

a

Un pointeur sur le GRDNB à modifier

Avertissement

Cette fonction N'EST PAS équivalente à a << 1, voir int vraishiftgauche(GRDNB *a).

Renvoie

Le nouvel indicemax.

On fait monter la première case tout à la fin du tableau par échanges successifs.
On réalloue le tableau pour supprimer la dernière case.

somme()

GRDNB somme	(	GRDNB	a,
		GRDNB	b,
		int	base
	)

Permet d'additionner deux GRDNB positifs.

Paramètres

[in]	a	Un GRDNB
[in]	b	Un GRDNB

Renvoie

Un GRDNB valant |a| + |b|

On met les nombres à la même taille, et la retenue à 0.

• Pour la base deux, on utilise un additionneur n bits :
  La retenue vaut ((acopie.tableau[i] XOR bcopie.tableau[i]) AND retenue) OR (acopie.tableau[i] AND bcopie.tableau[i])
  Le retour.tableau[i] vaut retenue XOR (acopie.tableau[i] XOR bcopie.tableau[i])
  
• Pour une autre base, on additionne case par case avec la retenue.
  Si le résultat de cette addition (case a + case b + retenue) est supérieur à la base,
  • la retenue vaudra le résultat / base
  • le retour.tableau[i] vaudra résultatbase (chiffre des unités)

S'il reste une retenue à la fin du calcul, on ajoute une case au début du retour et met la retenue dedans.

sous()

GRDNB sous	(	GRDNB	a,
		GRDNB	b,
		int	base
	)

Permet d'additionner deux GRDNB positifs avec a > b.

Paramètres

[in]	a	Un GRDNB
[in]	b	Un GRDNB tel que b < a

Renvoie

Un GRDNB valant |a| - |b|

On met les nombres à la même taille, et la retenue à 0.

• Pour la base deux, on on additionne a et le complément à 2 de b auquel on ajoute 1 puis on additionne (voir somme(GRDNB a, GRDNB b, int base)):
  La retenue vaut ((acopie.tableau[i] XOR bcopie.tableau[i]) AND retenue) OR (acopie.tableau[i] AND bcopie.tableau[i])
  Le retour.tableau[i] vaut retenue XOR (acopie.tableau[i] XOR bcopie.tableau[i])
  Cependant, s'il y a une retenue restante lors de l'addition, on l'oublie.
• Pour une autre base, on fait la soustraction naive, c'est-à-dire que l'on soustrait case par case avec la retenue.
  Si le résultat de cette soustraction (case a - (case b + retenue)) est négatif,
  • la retenue vaudra 1.
  • le retour.tableau[i] vaudra base + test. C'est-à-dire que l'on ajoute base et que l'on enlève base à la soustraction d'après en mettant retenue à 1.
    

sousnombre()

GRDNB sousnombre	(	GRDNB	a,
		int	debut,
		int	fin
	)

Recrée un autre nombre à partir d'un autre nombre et d'une position de début (inclue) et de fin (exclue)

Paramètres

[in]	a	Le GRDNB dont on va extraire le sous-nombre
[in]	debut	L'indice de début tel que debut < a.indicemax - 2.
[in]	fin	L'indice de fin tel que debut < fin < a.indicemax

Renvoie

Un GRDNB positif qui sera le nombre extrait de a de début à fin exclu.

Obsolète:

Anciennement utilisée pour implémenter l'algorithme de Karastuba pour une multiplication rapide.

Exemple : sousnombre("12345",1,3) = "23".

soustraction()

GRDNB soustraction	(	GRDNB	a,
		GRDNB	b,
		int	base
	)

Permet de faire a - b, peu importe leur signe et on peut avoir b > a.

Paramètres

[in]	a	Un GRDNB
[in]	b	Un GRDNB
[in]	base	La base de a, b et du GRDNB renvoyé.

Renvoie

Un GRDNB : a - b.

La fonction "sous(GRDNB a, GRDNB b, int base)" ne peut traiter que deux nombres positifs, avec a > b.
Il faut donc faire une fonction qui va adapter les appels selon tous les cas possibles.

• Si a et b positifs,
  • Si a > b, on renvoie directement |a| - |b|.
  • Si b > a, on renvoie -1 * (|b| - |a|).
• Si a positif, b négatif, on renvoie |a| + |b|
• Si a négatif, b positif, on renvoie -1 * (|a| + |b|)
• Si a et b négatifs, on recommence en les mettant positifs et on multiplie le résultat par -1.

str2grdnb()

GRDNB str2grdnb

(

char *

chaine

)

Convertit un nombre écrit dans une chaine de caractère en GRDNB.

Paramètres

[in]

chaine

Une chaine de caractère ne comprenant éventuellement au début le signe puis que des chiffres. La base doit être inférieure ou égale à 10.

Renvoie

Un GRDNB correspondant à la chaine et la base passées en paramètre'il y a une erreur, renvoie un GRDNB correspondant à -0.

On lit le premier caractère pour regarder le signe.
Si le signe n'est pas précisé, le nombre est positif.
Dans la table ASCII, '0' s'écrit 48, '1' s'écrit 49 ...
Il suffit de faire carac - 48 pour récupérer la valeur écrite dans le caractère.

supprimezero()

void supprimezero

(

GRDNB *

a

)

Permet de supprimer les zéros superflus au début d'un GRDNB.

Paramètres

[in,out]

a

L'adresse du GRDNB dont on va supprimer les zéros.

tailleBase2()

int tailleBase2

(

GRDNB

a

)

Permet de connaitre la taille en base 2 d'un GRDNB écrit en base 10.

Paramètres

[in]

a

Le GRDNB en base 10 dont on veut avoir la taille en base 2.

Renvoie

Un int : la taille en base 2 de a.

On compte le nombre de divisions entières par 2 que l'on peut faire à ce nombre.

tailleIdentique()

int tailleIdentique	(	GRDNB	a,
		GRDNB	b,
		GRDNB *	acopie,
		GRDNB *	bcopie
	)

Permet de mettre deux grands nombres à la même taille sans les modifier.

Paramètres

[in]	a	Un GRDNB.
[in]	b	Un GRDNB.
[out]	acopie	Un pointeur sur le GRDNB qui contiendra la copie de a de même taille que bcopie.
[out]	bcopie	Un pointeur sur le GRDNB qui contiendra la copie de b de même taille que acopie.

Renvoie

Un entier, la taille de acopie et bcopie, equivalente à max(a.indicemax,b.indicemax).

L'agorithme prend le plus grand des deux, et le copie directement case par case dans le pointeur sur le GRDNB correspondant.
Pour le plus petit, il va créer un GRDNB dans le pointeur correspondant avec un tableau de taille du plus grand.
Pour les cases de 0 à |a.indicemax - b.indicemax| exclu, on ne met que des zéros, puis ensuite on copie case par case du petit nombre vers ce tableau.
Si les deux nombres sont de taille identique, il copie (case par case) les deux nombres dans les pointeurs correspondants.

Initialement prévue pour implémenter l'algorithme de Karatsuba pour la multiplication, elle est utilisée dans de nombreuses autres fonctions pour faciliter leur implémentation.

un()

GRDNB un

(

)

Crée un grand nombre valant 1.

Renvoie

Un GRDNB de taille 1, de signe 1 et tableau[0] = 1.

vraishiftdroite()

int vraishiftdroite

(

GRDNB *

a

)

Permet de supprimer la dernière case du tableau de a.

Paramètres

[in,out]

a

Un pointeur sur le GRDNB à modifier, celui doit avoir une taille de 1 minimum

Renvoie

Le nouvel indicemax.

Note

Si a est en base b, faire vraishiftdroite(&a) <=> a = a/b.

vraishiftgauche()

int vraishiftgauche

(

GRDNB *

a

)

Permet d'ajouter une case à 0 à la fin du tableau de a.

Paramètres

[in,out]

a

Un pointeur sur le GRDNB à modifier.

Renvoie

Le nouvel indicemax.

Note

Si a est en base b, faire vraishiftgauche(&a) <=> a = a*b.