l'addition en c

**rteuteu55** · 24/10/2007, 10h47

Bonjour,

je cherche à créer une fonction d'addition en c.
vous allez me dire que ça existe déjà

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

si ce n'ai l'addition bit à bit avec une retenu mais je ne vois pas comment créer une fonction avec.

**Sve@r** · 24/10/2007, 11h09

Envoyé par rteuteu55

Bonjour,

je cherche à créer une fonction d'addition en c.
vous allez me dire que ça existe déjà

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

**diogene** · 24/10/2007, 11h44

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

sizeof(a)+1

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

**rteuteu55** · 24/10/2007, 12h45

en effet pour le sizeof !

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**diogene** · 24/10/2007, 13h26

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

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

**Sve@r** · 24/10/2007, 16h28

Envoyé par diogene

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

  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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**Jean-Marc.Bourguet** · 24/10/2007, 16h56

1/ utilise des unsigned char, pas des char
2/ Ne travaille pas bit a bit: coeur de la boucle avec des unsigned char:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

**rteuteu55** · 24/10/2007, 19h53

en effet je pense travailler directement sur mes octets.

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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.

**rteuteu55** · 25/10/2007, 10h31

j'install cygwin pour tester ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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);
		}
	}
}

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

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

**rteuteu55** · 25/10/2007, 11h33

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

**rteuteu55** · 25/10/2007, 12h44

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

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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);
		}
	}
}

**Sve@r** · 25/10/2007, 13h34

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

l'addition en c

C

Discussions similaires

Partager

Partager