l'addition en c

Version imprimable

24/10/2007, 10h47
rteuteu55

l'addition en c
Bonjour,

je cherche à créer une fonction d'addition en c.
vous allez me dire que ça existe déjà :roll: mais je veux la créer pour de grands nombres sans utiliser la librairie BigNum ou autre grosse librairie.

pour faire simple mes nombres son sous la forme de tableau d'octet de taille différente.

exemple :
Code:

1 2 3 4 5 6 char a[5]={0x23,0x45,0X67,0x89,0x01}; char b[2]={0x14,0x59}; char c[sizeof(a+1)]; // sizeof à définir ... c = addition(a,b);
le probléme est que je ne vois pas du tout comment structurer ma fonction.
si j'utilise des pointeurs ...

Ma contrainte et d'utiliser des nombres sous la forme de tableau car je suis sur un microcontroleur 8bit.

je n'ai pas trouvé grand chose sur :google2: si ce n'ai l'addition bit à bit avec une retenu mais je ne vois pas comment créer une fonction avec.
24/10/2007, 11h09
Sve@r
Citation:
Envoyé par rteuteu55

Bonjour,

je cherche à créer une fonction d'addition en c.
vous allez me dire que ça existe déjà :roll: mais je veux la créer pour de grands nombres sans utiliser la librairie BigNum ou autre grosse librairie.

pour faire simple mes nombres son sous la forme de tableau d'octet de taille différente.

exemple :

Code:

1 2 3 4 5 6 char a[5]={0x23,0x45,0X67,0x89,0x01}; char b[2]={0x14,0x59}; char c[sizeof(a+1)]; // sizeof à définir ... c = addition(a,b);

le probléme est que je ne vois pas du tout comment structurer ma fonction.
si j'utilise des pointeurs ...

Ma contrainte et d'utiliser des nombres sous la forme de tableau car je suis sur un microcontroleur 8bit.

je n'ai pas trouvé grand chose sur :google2: si ce n'ai l'addition bit à bit avec une retenu mais je ne vois pas comment créer une fonction avec.
Faut faire comme au primaire
1) tu traites tes 2 tableaux "a" et "b" en partant de la fin pour revenur au début
2) chaque élément du tableau est additionné et tronqué à un chiffre et stocké dans le tableau c. S'il y a une retenue issue de l'élément précédent tu l'additionnes aussi

Intuitivement moi je stockerais mes nombres dans l'autre sens pour pouvoir traiter le tableau en partant du début vers la fin (mais j'ai pas vraiment réfléchi aux avantages et inconvénients)...
24/10/2007, 11h44
diogene
Code:

1 2 3 char a[5]={0x23,0x45,0X67,0x89,0x01}; char b[2]={0x14,0x59}; char c[sizeof(a+1)]; // sizeof à définir ...
Il y a un problème sur ce sizeof : a+1 est une expression du type adresse et sizeof(a+1) renvoie la taille de ce type donc la taille d'un pointeur. sans doute voulais-tu écrire

Code:

sizeof(a)+1

qui est le (nombre de bytes du tableau a) + 1;

en effet pour le sizeof !

sinon voila où j'en suis ... ce n'est pas joli à voir ... !

Code:

1
2
3
4
5
char a[5]={0x23,0x45,0X67,0x89,0x01};
char b[2]={0x14,0x59};
char c[sizeof(a)+1]; 
 
addition(a,b,c);

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
 
addition (char* a, char* b,char* c)
{
  int tailleA=sizeof(&a);
  int tailleB=sizeof(&a);
  int nbIteration=0;
  int i=0;
 
  bool x,y,z,r,rOld; //=0 
 
  if (tailleA>=tailleB) nbIteration=tailleB;
  else nbIteration=tailleA;
 
  while (i<=tailleA || i<=tailleB)
  {
    rOld=r;
    if (i<=nbIteration)
    {
      x=bit i de a; //comment le récuperer?
      y=bit i de b; //comment le récuperer?
      z=rOld^x^y; // z= bit résultant de la somme
      r= // a retrouver ... r= retenu.
    } else {
      x=bit de a ou b suivant le nombre le plus grand.
      z=rOld^x;
      r=rOld&x;
    }
    i++
    c[]= // intégrer z sur le bon bite
  }
}

24/10/2007, 13h26
diogene

Décidemment, tu as des problèmes avec sizeof :

Code:

int tailleA=sizeof(&a);

ces sizeof vont donner la taille d'une adresse, soit la taille d'un pointeur, pas du tout la taille des tableaux passés en arguments.

Code:

x=bit i de a; //comment le récuperer?

Par exemple, avec un masque en utilisant un ET bit à bit (opérateur &)
24/10/2007, 16h28
Sve@r

Citation:

Envoyé par diogene

Décidemment, tu as des problèmes avec sizeof :

Code:

int tailleA=sizeof(&a);

ces sizeof vont donner la taille d'une adresse, soit la taille d'un pointeur, pas du tout la taille des tableaux passés en arguments.

Code:

x=bit i de a; //comment le récuperer?

Par exemple, avec un masque en utilisant un ET bit à bit (opérateur &)

Tu décales a vers la droite de "i - 1" bits. Le bit "i" devient donc le dernier que tu récupères via un masque sur l'octet 00000001
x=(a >> (i - 1)) & 0x01
24/10/2007, 16h56
Jean-Marc.Bourguet
1/ utilise des unsigned char, pas des char
2/ Ne travaille pas bit a bit: coeur de la boucle avec des unsigned char:
Code:

1 2 3 4 sum = a[i] + b[i] + carry; res[i] = sum % (UCHAR_MAX+1); carry = sum / (UCHAR_MAX+1);
Tu peux utiliser plus grand qu'unsigned char pour les chiffres tant que tu as un type pour sum capable de representer exactement la somme de deux chiffres. Generalement, on veut la multiplication aussi donc on prend le type qui a la taille moitie du plus grand unsigned. Si on n'a que l'addition a faire, on peut faire:
Code:

1 2 3 res[i] = a[i] + b[i] + carry; carry = (DIGIT_MAX-a[i] < b[i]) || (DIGIT_MAX-carry < a[i]+b[i]);
mais il faudrait mesurer pour voir si c'est reellement plus efficace. Attention, mon expression pour carry est ecrite pour ternir compte des cas limites; il y a peut-etre moyen de la simplifier, mais c'est pas immediat (en particulier supprimer la premiere partie du test
n'est pas une simplification valide).
24/10/2007, 19h53
rteuteu55
en effet je pense travailler directement sur mes octets.

par contre j'ai du mal à comprendre ces 2 lignes :
Code:

1 2 res[i] = sum % (UCHAR_MAX+1); carry = sum / (UCHAR_MAX+1);
edit : autant pour moi j'avais mal compris UCHAR_MAX mais je viens de comprendre : dans le cas d'un uchar, UCHAR_MAX = 0xFF si j'ai bien compris.

j'install cygwin pour tester ça :

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
42
43
44
45
46
47
48
49
#include <stdio.h>
 
#define UCHAR_MAX 0xFF
 
typedef unsigned char uchar;
 
int main (void)
{
	//
	uchar a[8]={0x71,0x05,0x48,0x12,0x38,0x05,0x97,0x94}?
	uchar b[5]={0x83,0x12,0x53,0x90,0x87};
	uchar c[8];
 
	somme (a,b,c);
 
	for (int i=0,i<sizeof(c);i++)
	{
		printf("%c",c[i]);
	}
	printf ("\n");
}
 
void somme (uchar* a,uchar* b,uchar* c)
{
	int resultat=0;
	int retenu=0;
 
	int tailleA=sizeof(a);
	int tailleB=sizeof(b);
 
	if (tailleA>=tailleB)
	{
		for (int i=0;i<tailleA;i++)
		{
			if (i<=tailleB) resultat = a[i] + b[i] + retenu;
			else resultat = a[i] + retenu;
			c[i] = resultat % (UCHAR_MAX+1);
			retenu = resultat / (UCHAR_MAX+1);
		}
	} else {
		for (int i=0;i<tailleB;i++)
		{
			if (i<=tailleA) resultat = a[i] + b[i] + retenu;
			else resultat = b[i] + retenu;
			c[i] = resultat % (UCHAR_MAX+1);
			retenu = resultat / (UCHAR_MAX+1);
		}
	}
}

25/10/2007, 10h34
Jean-Marc.Bourguet

Je n'ai fait que parcourir. La plus grosse remarque que j'ai a faire est que sizeof ne fonctionne pas comme tu le penses (confusion tableau/pointeur).
25/10/2007, 11h33
rteuteu55

en effet, mes tailleA et tailleB valent 4 ...

je vais donc utiliser des variables (voir faire une structure) puisque la taille de mes tableaux est statique.

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
void somme (uchar* a,int tailleA,uchar* b,int tailleB,uchar* c)
{
	int resultat=0;
	int retenu=0;
	int i;
 
	//int tailleA=sizeof(a);
	//int tailleB=sizeof(b);
 
	printf(" tailleA = %i \n tailleB = %i \n",tailleA,tailleB);
 
	if (tailleA>=tailleB)
	{
		for (i=0;i<tailleA;i++)
		{
			if (i<=tailleB) resultat = a[i] + b[i] + retenu;
			else resultat = a[i] + retenu;
			c[i] = resultat % (UCHAR_MAX+1);
			retenu = resultat / (UCHAR_MAX+1);
			printf("\n i : %i \n resultat : %i \n retenu : %i \n",i,resultat,retenu);
		}
	} else {
		for (i=0;i<tailleB;i++)
		{
			if (i<=tailleA) resultat = a[i] + b[i] + retenu;
			else resultat = b[i] + retenu;
			c[i] = resultat % (UCHAR_MAX+1);
			retenu = resultat / (UCHAR_MAX+1);
			printf("\n i : %i \n resultat : %i \n retenu : %i \n",i,resultat,retenu);
		}
	}
}

Citation:

Envoyé par rteuteu55

en effet, mes tailleA et tailleB valent 4 ...

Normal. Les adresses de tes tableaux sont stockés dans des pointeurs. Et la taille d'un pointeur est de 4 octets !!!

Exemple
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 int main() { char tab[100]; printf("taille tab: %lu\n", sizeof(tab)); fct(tab); } int fct(char* pt) { printf("taille pt: %lu\n", sizeof(pt)); return 0; }
C'est pour ça que ta structure "bignum" doit contenir
- le nombre
- la taille réservée pour ce nombre

Toute fonction recevant un pointeur sur bignum saura utiliser cette taille...