Discussion :

[trax44]

bonsoir,
je viens tout juste de commencer le C.
j'essaye de fair un petit programme qui fait une multiplication de deux nombres de taille inférieur a 32bits. Pour la multiplication j'utilise l'algorithme de la division Russe (mais l'a n'est pas le problème).

Je décalle une variable de 64 bits (long long int) de 1 et quand je dépasse les 32bits il y a un truc qui foire !

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
 
int main () {
unsigned int a , t1 ,t2 ;
unsigned long long int  b , res;
 int unsigned *c=malloc(sizeof(int)*3) ; c[0]=0 ; c[1]=0 ; c[2]=0 ;
 
 
printf("\nEntrer vos deux nombres séparés d'un espace  : ") ;
scanf("%u%u" , &t1 , &t2 ) ;
 
a=t1 ; b=t2 ;
 
/* a=13 ; b=5 ; */
/* a=456789 ; b = 456123 ; */
 
 
printf("%u*%u==\n" , a , b) ;
 
do {
t1 = b>>32 ; t2 = b&0x0FFFFFFFF ;
printf("%u\t| %u%u"  , a , t1,t2) ;
 
if (a%2==1){printf(" * ");
res=c[0]+b ;  if (res>>32==0){c[0]=res ; }
else{c[1]=c[1]+(res>>32) ; c[0]=c[0] + (res & 0x0FFFFFFFF) ; } } printf("\n") ;
a=a>>1 ;
b=b<<1 ;
}while (a>0) ;
 
printf("\t%u%u\n" ,c[1],c[0] ) ;
return 0 ;
}/* main */

avec les nombres 456789 et 456123 çà donne cette liste :

Entrer vos deux nombres séparés d'un espace : 456789 456123
456789*456123==
456789 | 0456123 *
228394 | 0912246
114197 | 01824492 *
57098 | 03648984
28549 | 07297968 *
14274 | 014595936
7137 | 029191872 *
3568 | 058383744
1784 | 0116767488
892 | 0233534976
446 | 0467069952
223 | 0934139904 *
111 | 01868279808 *
55 | 03736559616 *
27 | 13178151936 * <=première erreure il est attendu 7473119232 au lieux de 13178151936
13 | 32061336576 *
6 | 64122673152
3 | 133950379008 *
1 | 273605790720 *
472606621408 <= résultat obtenu
208351969047 <= résultat attendu

Cordialement
trax

[Médinoc]

Euh...

1°) Compilo/plate-forme?
2°) Tu n'aurais pas la même chose affichée dans un format qui s'adapte un peu mieux aux décalages de bits... Au hasard, l'hexa ?

[trax44]

Suffit de demander

je suis sous une ubuntu et je compile avec gcc 4.0.2

Entrer vos deux nombres séparés d'un espace : 456789 456123
456789*456123==
6F855 | 06F5BB *
37C2A | 0DEB76
1BE15 | 01BD6EC *
DF0A | 037ADD8
6F85 | 06F5BB0 *
37C2 | 0DEB760
1BE1 | 01BD6EC0 *
DF0 | 037ADD80
6F8 | 06F5BB00
37C | 0DEB7600
1BE | 01BD6EC00
DF | 037ADD800 *
6F | 06F5BB000 *
37 | 0DEB76000 *
1B | 1BD6EC000 *
D | 37ADD8000 *
6 | 6F5BB0000
3 | DEB760000 *
1 | 1BD6EC0000 *
472606621408
208351969047

[Médinoc]

Dev-C++ (Win32, GCC 3.4.2):

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
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
#include <stdio.h>
#include <stdlib.h>
 
int main(void)
{
unsigned int a , t1 ,t2 ;
unsigned long long int  llb , llRes;
unsigned int *pt_c = malloc(sizeof(*pt_c)*3);
/* Ajouté */
if(pt_c == NULL)
	return EXIT_FAILURE;
pt_c[0] = 0;
pt_c[1] = 0;
pt_c[2] = 0 ;
 
 
/* J'ai pas l'habitude d'utiliser scanf, mais on va faire avec */
//printf("\nEntrer vos deux nombres séparés d'un espace  : ") ;
//scanf("%u%u" , &t1 , &t2 ) ;
 
a = t1;
llb = t2 ;
 
/* a=13 ; b=5 ; */
a=456789 ; llb = 456123 ; // */
 
/* Le printf() était erroné (manquait le préfixe "long long" */
 
/* Sous Win32, %llu est remplacé par %I64u */
//printf("\n%u * %llu == %08X * %016llX ==\n\n", a, llb, a, llb) ;
printf("\n%u * %I64u == %08X * %016I64X ==\n\n", a, llb, a, llb) ;
 
 
do	{
	/* Ça revient sans doute au même, mais je préfère mettre toute la largeur:
	C'est plus compréhensible. */
	t1 = llb>>32;
	t2 = llb & 0x00000000FFFFFFFF;
	/* Deux entiers décimaux affichés côte-à-côte, ça ne le fait pas. */
	printf("%08X\t| %08X:%08X", a, t1, t2) ;
 
	if(a%2 == 1) /* Ou if(a & 1) */
		{
		printf(" * ");
		llRes = pt_c[0] + llb;
		if(llRes>>32 == 0)
			{
			/* Ajout du cast */
			pt_c[0] = (unsigned int)llRes;
			}
		else
			{
			pt_c[1] = pt_c[1] + (llRes>>32); /* Ou avec l'opérateur += */
			pt_c[0] = pt_c[0] + (llRes & 0x00000000FFFFFFFF);
			}
		}
	printf("\n") ;
	/* Les opérateurs >>= et <<= ne sont pas mal non plus... */
	a = a>>1 ;
	llb = llb<<1 ;
} while(a>0);
 
	/* Deux entiers décimaux affichés côte-à-côte, ça ne le fait pas. */
printf("\t%08X:%08X\n", pt_c[1], pt_c[0] );
llRes = pt_c[1];
llRes <<= 32;
llRes |= pt_c[0];
 
//printf("\t%016llX == %llu\n", llRes, llRes);
printf("\t%016I64X == %I64u\n", llRes, llRes);
 
/* Dev-C++ */
system("pause");
return EXIT_SUCCESS;
}/* main */

Et en sortie:

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
456789 * 456123 == 0006F855 * 000000000006F5BB ==
 
0006F855        | 00000000:0006F5BB *
00037C2A        | 00000000:000DEB76
0001BE15        | 00000000:001BD6EC *
0000DF0A        | 00000000:0037ADD8
00006F85        | 00000000:006F5BB0 *
000037C2        | 00000000:00DEB760
00001BE1        | 00000000:01BD6EC0 *
00000DF0        | 00000000:037ADD80
000006F8        | 00000000:06F5BB00
0000037C        | 00000000:0DEB7600
000001BE        | 00000000:1BD6EC00
000000DF        | 00000000:37ADD800 *
0000006F        | 00000000:6F5BB000 *
00000037        | 00000000:DEB76000 *
0000001B        | 00000001:BD6EC000 *
0000000D        | 00000003:7ADD8000 *
00000006        | 00000006:F5BB0000
00000003        | 0000000D:EB760000 *
00000001        | 0000001B:D6EC0000 *
        0000002F:9B5DE2E0
        0000002F9B5DE2E0 == 204470084320
Appuyez sur une touche pour continuer...

Je n'obtiens ni ton "résultat obtenu", ni ton "résultat attendu"... Il faut dire aussi que tu avais une façon étrange de l'afficher... (coller deux nombres décimaux 32bits, ça ne donne PAS un nombre décimal 64bits... ça, ça ne marche qu'en hexadécimal ou en binaire...)

Mais dis-moi, c'est normal, ton "res = c[0]+b" sans toucher à c[1] ?
D'un coté, ça a l'air de marcher, mais d'un autre coté, ça fait suspect...

[trax44]

en fait j'utilise res = c[0]+b ; pour d'étecter le débordement de l'addition. Je sais pas le faire autrement normalement il devrait y avoir possibilité d'accéder au registrer processeur de débordement mais je ne sais pas comment faire.

Code :

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

1
2
3
 
if (res>>32==0){c[0]=res ; }
else{c[1]=c[1]+(res>>32) ; c[0]=c[0] + (res & 0x0FFFFFFFF) ; } } printf("\n") ;

et je touche bien a c[1] si il y a une "retenue" dans la partie haute de res.

Médinoc, ton code fonctionne je vais voir ce qui va pas avec le mieux (peut etre juste l'affichage). J'ai commencé le C deux jour avant mon poste :s

Cordialement
TRAX

[trax44]

Bon voici le code revu est corrigé. Ici le test se fait avec
A=D91097D725BC9C2C ; B=2E4376409371327 ;
A*B ;
A sur 64 bits et B sur 58bits => résultat sur 122 bits

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
50
51
52
53
 
#include <malloc.h>
 
 
int main () {
 
 int a , b , n , i , ii, r; 
 
a= 1 ; b = 1 ; /* longeur du tableau */
unsigned int *A = malloc (sizeof(int)*(a+1)) ; 
unsigned int *B = malloc (sizeof(int)*(a+b+2)) ; 
unsigned int *res = malloc (sizeof(int)*(a+b+2)) ; 
unsigned long long int c; 
 
/* A=D91097D725BC9C2C ; B=2E4376409371327 ; */
A[0]=0x025BC9C2C ; B[0]=0x009371327 ; 
A[1]=0x0D91097D7 ; B[1]=0x02E43764 ;  
 
do {
if (A[0]%2==1) {
 
/*addition */
for (i=0 ; i<=b ; i++) {
 
c=(long long int)res[i]+(long long int)B[i] ; res[i]=(c&0x0FFFFFFFF) ; 
 
n=i ; 
while(c>>32!=0){
n++ ; c=(long long int)res[n]+(long long int)1 ; 
if(c>>32==0){res[n]++ ;}else{res[n]=0;}
}
 
}/*   for 	*/
}/*   if%2	*/
 
 
/* décallage vers la droite */
r=0 ; 
for (ii=0 ; ii<a ; ii++) {
r=(A[ii+1]&1)<<31 ; A[ii]=A[ii]>>1 ; A[ii]=A[ii]|r ;}
A[a]=A[a]>>1 ; if(A[a]==0){a--;}
 
/* décallage vers la gauche*/ 
if ((B[b]&0x0EFFFFFFF)!=0) {b++ ; }
for(ii=b ; ii>=0 ; ii--) {r=(B[ii]&0x0EFFFFFFF)>>31 ; B[ii+1]=B[ii+1]|r ; B[ii]=B[ii]<<1; }
}while(a>-1) ;  
 
 
printf("\n                    %X%X%X%X%X" ,res[4] , res[3] , res[2] , res[1] ,res[0]) ;
/* résultat attendu */ 
printf("\n                     273A2EE4CD3E67E2EC34BC6D8C70EB4\n") ; 
return 0 ; 
} /* main */

Cordialement
trax

PS c'est mon premier programme digne de se nom en C

[Emmanuel Delahaye]

Bon voici le code revu est corrigé. Ici le test se fait avec
A=D91097D725BC9C2C ; B=2E4376409371327 ;
A*B ;
A sur 64 bits et B sur 58bits => résultat sur 122 bits

<malloc.h> ça n'existe pas en C standard.
Il manque <stdlib.h>
Il manque <stdio.h>
Fuite mémoire :

Code :

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

1
2
3
4
5
6
7
 
 
                    2C467316BD5FA8A5B61619BC001003FE000C000
                     273A2EE4CD3E67E2EC34BC6D8C70EB4
SYSALLOC Bloc 003D2478 (8 bytes) malloc'ed at line 10 of 'main.c' not freed
SYSALLOC Bloc 003D24E8 (16 bytes) malloc'ed at line 11 of 'main.c' not freed
SYSALLOC Bloc 003D2500 (16 bytes) malloc'ed at line 12 of 'main.c' not freed

[trax44]

Pour le stdio.h je savais j'ai mal recopié mon code (c'étais la première ligne).
Mais <stdlib.h> c'est quoi ?
et la fuite mémoire c'est du au fait que je n'ai pas mis de free ou c'est autre chose ??

Sinon C standar c'est quoi pour vous ? ansi, C90, C99 ... ?

Cordialement
TRAX

[Emmanuel Delahaye]

Mais <stdlib.h> c'est quoi ?

Pour malloc() free()

et la fuite mémoire c'est du au fait que je n'ai pas mis de free

Oui.

Sinon C standard c'est quoi pour vous ? ansi, C90, C99 ... ?

J'avoue que c'est discutable. Néanmoins, si on s'en tient à la réalité des implémentations, c'est C90 (Le terme ANSI est dénué de sens précis, et de plus, ne concerne en théorie que les USA).

Quand à C99, il n'y a pas vraiment d'implémentation (libre) satisfaisante actuellement.

Mais il y en a des payantes comme Intel, Comeau etc.

Et ça ne semble intéresser ni Microsoft ni Borland qui doivent considérer (AMA à tord) que le C est dépassé...

[trax44]

Emmanuel Delahaye, merci bien pour tes éclaircissements