# Nombre limite d'éléments dans un tableau en C



## Pedro (26 Janvier 2003)

Débutant total en langage C, je m'initie actuellement à la programmation en mode terminal. Je me suis heurté à une limite : impossible de dépasser la taille de 46348 éléments dans un tableau d'entiers ou de caractères sous peine de segmentation error à l'exécution. Je pensais pouvoir dépasser cette limite avec malloc(), mais cela ne semble pas régler le problème. Comment faire ?


----------



## plumber (26 Janvier 2003)

ca me rappel une histoire je vais regarder si je retrouve mon truc


----------



## Luc G (26 Janvier 2003)

Regarde si tu n'as pas des options de compilation qui te permettent de travailler sur des segments de data de grande taille : ça ressemble à un pb de ce type : il doit falloir que ton tableau rentre dans un segment, si les segments ne font que 64 ko par exemple, tu ne peux pas rentrer un tableau de taille supérieur à 64ko (je schématise).

Quand je programmais (pour l'heure, juste mumuse  
	

	
	
		
		

		
		
	


	




), j'avais eu ce genre de truc en pascal sur les 68xxx, pour des tableaux et pour des XCMD/XFCN pour hypercard (limite à 32ko). Ensuite, on avait une option, soit pour gérer du multisegments de façon transparente, soit pour avoir des segments plus grands, je ne sais plus.


----------



## Pedro (30 Janvier 2003)

Merci pour vos réponses, mais je n'ai pas trouvé d'infos claires sur la segmentation dans la doc des dev tools. Connaissez une base d'information accessible sur le développement en C ?


----------



## Fulvio (11 Février 2003)

Wouh ! Utiliser un tableau de plus 46000 éléments, faut vraiment vouloir le faire ! (46k de caractères, c'est de la folie)
Quel est ton but ? A mon avis, il doit certainement y avoir d'autres réponses à ton besoin que d'allouer un tableau aussi... hénaurme !


----------



## nicolas51 (25 Février 2003)

Cela me rappelle ma jeunesse (il y a une dizaine d'année). Des copains sur PC en pascal ne pouvait pas faire des grands tableaux et en basic sur mon Atari je faisais des tableaux de plus de 600Ko. Je m'en servais pour chercher des nombres premiers par la méthode du crible d'Erathostène.
Finalement, dix ans plus tard, cela n'a pas changé.
Désolé de ne pas apporter de réponse à la question.

Une idée quand même : en essayant C et C++ dans le project Builder ?


----------



## Bobbus (26 Février 2003)

<blockquote><font class="small">Post&eacute; &agrave; l'origine par lupus yonderboy:</font><hr /> * Wouh ! Utiliser un tableau de plus 46000 éléments, faut vraiment vouloir le faire ! (46k de caractères, c'est de la folie)
Quel est ton but ? A mon avis, il doit certainement y avoir d'autres réponses à ton besoin que d'allouer un tableau aussi... hénaurme !  * 

[/QUOTE]

Il existe des domaines dans lesquels ce n'est pas exagéré et où il y a bien une nécessité d'avoir des tableaux aussi grands. En cryptographie, par exemple, mais il y a beaucoup d'autres domaines assez pointus où c'est chose courante...

Bob


----------



## Pedro (27 Février 2003)

Il s'agit justement d'un programme de recherche de nombres premiers par la méthode du crible d'Eratosthène! Et effectivement le BASIC gère toujours plus facilement les gros tableaux que le C : Avec la version CARBON de Chipmunk BASIC, j'ai réussi à atteindre 71 999 989 en créant en dynamique un HENAURME tableau de réels d'environ 640 Mo ! (15 minutes de calcul sur un iMac DV 400 avec 640 Mo de RAM). A noter que cette application sous OS X voit son allocation en mémoire réelle et virtuelle évoluer en fonction des besoins de façon tout à fait transparente pour l'utilisateur et modeste programmeur que je suis.


----------



## nicolas51 (27 Février 2003)

<blockquote><font class="small">Post&eacute; &agrave; l'origine par Pedro:</font><hr /> * Il s'agit justement d'un programme de recherche de nombres premiers par la méthode du crible d'Eratosthène! Et effectivement le BASIC gère toujours plus facilement les gros tableaux que le C : Avec la version CARBON de Chipmunk BASIC, j'ai réussi à atteindre 71 999 989 en créant en dynamique un HENAURME tableau de réels d'environ 640 Mo ! (15 minutes de calcul sur un iMac DV 400 avec 640 Mo de RAM). A noter que cette application sous OS X voit son allocation en mémoire réelle et virtuelle évoluer en fonction des besoins de façon tout à fait transparente pour l'utilisateur et modeste programmeur que je suis.   * 

[/QUOTE]

As-tu essayé le Metal Basic, plus rapide que le chipmunk ?
Je codais les entiers (impairs uniquement) sur un bit dans un tableau d'entiers ce qui permettait d'aller 16 fois plus loin.


----------



## Bobbus (9 Mars 2003)

<blockquote><font class="small">Post&eacute; &agrave; l'origine par Pedro:</font><hr /> * Débutant total en langage C, je m'initie actuellement à la programmation en mode terminal. Je me suis heurté à une limite : impossible de dépasser la taille de 46348 éléments dans un tableau d'entiers ou de caractères sous peine de segmentation error à l'exécution. Je pensais pouvoir dépasser cette limite avec malloc(), mais cela ne semble pas régler le problème. Comment faire ?   * 

[/QUOTE]

ça m'étonne tout ça...
J'utilise justement en ce moment des tableaux gigantesques et je peux créer (et utiliser) un tableau d'exactement 1 000 001 flottants (je n'ai pas fait de tests au delà), tout ça avec le gcc d'Apple et le GNU gcc et sans rencontrer un seul problème. Quel est l'erreur retournée à la compilation ?

Bob

PS : Pour ceux qui se demandent ce qu'on peut faire avec un tableau pareil, c'est dans le cadre d'un algorithme d'attaque RSA (Google : MPQS)


----------



## Didier Guillion (14 Mars 2003)

Bonjour,

Ton tableau tu le prédeclare genre :

int myTab[46000];

ou tu l'alloue dans la heap:

myTag=(int *) malloc(46000*sizeof(int))


Cordialement


----------



## Luc G (14 Mars 2003)

Le message de Bobbus pourrait faire penser que les tableaux d'entiers ne sont pas gérés comme les tableaux de réels. Et celui de Didier que c'est un problème de zone mémoire utilisée pour ranger le tableau (dans le tas ou dans la pile). 

Ce serait alors peut-être lié à la gestion des entiers en C (cf passage de paramètres). Si je dis des bêtises, vous pouvez taper, je ne me vexerai pas


----------



## Didier Guillion (14 Mars 2003)

Bonsoir,

En quelque sorte.

Quand on déclare ou prédeclare une variable ou un tableau en C, il est logé dans le segment des donnés.
Quand on l'alloue dans le tas (ou Heap). le terme Pile est plutot reservé a la Pile du processeur (variables locales)

Les différences sont les suivantes :

- Le segment de donnée est préinitialisé à zero ce qui n'est pas le cas des allocation dynamiques.
Donc dans le segment de donné on fait :
int monTableau[46000]

dans le Heap :
int * monTableau;

monTableau=(int*)malloc(sizeof(int)*46000);
memset(monTableau,0,sizeof(int)*46000);

après l'acces est identique par exemple :

monTableau[125]=3;


La différence fondamentale est qu'un tableau allouée dynamiquement est 
- libérable, par
free(monTableau)
- non limité par la taille du segment de donnée. Certains compilateurs limitant la taille du segment de donnée a 64K (avec des options de compilation pour l'agrandir)


Cordialement


----------



## Pedro (18 Mars 2003)

Bonsoir,
J'ai appliqué la méthode de Didier pour créer le tableau et j'ai rencontré la même limitation à 46348 éléments à l'execution du programme... Au bout d'un long moment de réflexion, j'ai fini par comprendre pourquoi: en fait, j'utilise pour adresser le tableau n[p] une variable entière p qui est elle-même le produit de 2 entiers p et i, variant entre 1 et nmax. Ce qui arrive, c'est que quand nmax dépasse 46348, le produit q=p*i peut dépasser la valeur fatidique de 2^31-1 au delà de laquelle une variable entière signée sur 4 octets déborde. D'où un adressage hors des valeurs limites du tableau et segmentation fault... cqfd! Le genre d'erreur de programmation qui est très difficile à débusquer car le compilateur n'y voit que du feu et l'erreur à l'execution n'est pas très explicite.


----------



## Didier Guillion (18 Mars 2003)

Bonjour,

Problème ardu en effet. 
Mais normalement les compilateurs C s'en sortent il me semble.
Quel est ton compilateur ?

Si tu as un bout de code très simple qui genère l'erreur, j'aimerai bien l'avoir pour le décortiquer et l'essayer sur mon compilateur.

Cordialement


----------



## Pedro (19 Mars 2003)

Bonsoir,
j'ai rencontré cette erreur à l'éxecution avec GCC utilisé en mode terminal, ainsi qu'avec Project Builder. Voici le programme en question, après mise en place d'un garde-fou qui règle le problème. Si tu veux reproduire l'erreur, supprime les deux lignes suivantes :
qf=(float)p*(float)i;
if (qf&gt;2147483647) break; // évite débordement de q si&gt; 2^31-1.
-------------------------------------
/* Crible des nombres premiers */

#include &lt;stdlib.h&gt;
main()
{

char *n;
int nmax, i, p, q, c, t1, t2, lastprem;
float qf;

printf("valeur de n: \n");
scanf("%d",&amp;nmax);   /* instr pour entrer nmax */

n = (char*) malloc(sizeof(char)*nmax+1);
memset(n,1,sizeof(char)*nmax+1);

t1 = time(NULL);
for(p=2; p&lt;= nmax; p++)
	{
	if (n[p]==0) continue;
	for(i=p;i&lt;=nmax; i++)
		{
		qf=(float)p*(float)i;
		if (qf&gt;2147483647) break; // évite débordement de q si&gt; 2^31-1
		q=p*i;
		if (q&gt;nmax) break;
		n[q]=0;
		}
	} 
t2 = time(NULL);

c=0; // init nécessaire à cause du tableau dynamique
for (i=1; i&lt;=nmax; i++)
	{
	if (n_==1) 
		{
		c++;
		lastprem=i;
		}
	} 


printf("\n");
printf("%d nombres premiers trouves\n",c);
printf("Plus grand nombre premier trouve : %d\n",lastprem);
printf("temps: %d s\n",t2-t1);
return(0);
}
_


----------



## Didier Guillion (19 Mars 2003)

Bonjour,

En effet, il y a un débordement mais que tu peut éviter, il me semble, de manière plus simple et plus rapide.

Il suffit de déclarer la variable "q" comme un "long long" et de tester comme suit :

long long q;
...

		q=(long long )p*(long long )i; 
		if (q&gt;nmax) break; 

Au passage, évite le type "int" dont la précision peut varier d'un compilateur a l'autre.

A noter que la ligne :

	if (n ==1) 
ne se compile pas chez moi.

Je suppose que tu voulais écrire 	if (*n ==1) ?

Cordialement


----------



## Pedro (20 Mars 2003)

Bonsoir,
Merci pour tes conseils avisés de programmeur Pro.
En fait, je voulais écrire: if (n(i)==1) avec des crochets au lieu des parenthèses autour de i mais au copier-coller ça a mis la fin du message en italique... Encore une subtilité du code UBB!


----------

