Segmentation fault

Programmation
#1

Bonsoir voici un programme qui calcule une valeur approchée de pi, et qui fonctionne (enfin presque)
Lorsque je lis la valeur 180000, celui-ci plante avec une erreur de segmentation

#include <stdio.h>

double MoinsUnPuissanceN (int n)
{
        if (n%2 == 0) return 1 ;
        else return -1 ;
}

double pi (int n)
{
        if (n == 0) return 4 ;
        else {
        return pi(n-1) + (MoinsUnPuissanceN (n)*4) / (2*n+1) ;
        }
}
void main()
{
        int rang ;
        double p ;
        while (scanf ("%d",&rang) == 0) getchar () ;
        p = pi (rang) ;
        printf("valeur approchée de pi au rang %d : %.10f\n",rang, pi (rang)) ;

}

Merci pour votre aide

#2

Aucun problème de mon côté, va falloir que tu détailles un peu plus ton souci, ton environnement etc.

Le seul truc auquel je pense c’est une question de taille de la pile (vu que c’est un algo récursif). Tu es sur quelle architecture ?
Sinon, lance-le sous gdb pour avoir une idée un peu plus précise de la cause.

Edit : cherche pas, c’est bien un souci de taille de pile. Chez moi (amd64) ça claque vers les 260-275000 par défaut (ulimit -s = 8192) et vers les 500-525000 avec un ulimit -s 16384.
T’as plus qu’à transformer cet algo récursif en itératif. :smiley:

#3

Je ne connais pas précisémment l’architecture de la machine que j’utilise, ça doit être un i386
Je suis sous debian squeeze,
quelle est la commande à utiliser pour avoir des info précises sur l’architecture ?
J’ai utilisé la commande ulimit mais ça ne change rien à mon problème. (j’ai fait ulimit -s 16384 sous root)
Je crois en effet qu’il ne me reste qu’à rendre le programme itératif.
Merci

#4

ulimit ne change la limite que pour la session en cours (autrement dit, pour les programmes lancés dans le même shell après avoir effectué le ulimit). Pas étonnant que ça ne marche pas si tu as fait un ulimit en root et testé ton programme en utilisateur.
Cela dit, ulimit n’est qu’un pis-aller, il déplace le problème sans le résoudre. La solution est effectivement un algo itératif (et puis bon c’est facile à convertir, c’est juste un accumulateur).

Concernant ton archi : uname -a pour savoir quel kernel est installé (i386 ou amd64), c’est de ça que va dépendre la taille de pile par défaut.

#5

[quote=“syam”]Edit : cherche pas, c’est bien un souci de taille de pile. Chez moi (amd64) ça claque vers les 260-275000 par défaut (ulimit -s = 8192) et vers les 500-525000 avec un ulimit -s 16384.
T’as plus qu’à transformer cet algo récursif en itératif. :smiley:[/quote]
Ou utiliser le tas plutôt que la pile.

#6

Tu veux mettre quoi sur le tas précisément, dans le cas présent ? :mrgreen:
Toute l’utilisation de la pile provient des appels de fonction.

#7

Tu as raison, du coup je me sus amusé à le faire et j’en ai profité pour modifier la fonction MoinsUnPuissanceN que j’ai écrite ainsi :

[code]double MoinsUnPuissanceN(const int n);

inline double MoinsUnPuissanceN(const int n)
{
return (n&1) ? -1 : 1;
}[/code]
Pour le reste je laisse zerimbak s’amuser :slightly_smiling:

#8

Je m’adresse à Mister Freeze,
Est-ce que ta solution permet de conserver la version récursive tout en résolvant le problème ?
Parce qu’à mon avis le problème ne vient pas de la fonction MoinUnPuissanceN qui n’est pas récursive.

#9

Cette fonction est totalement annexe. Il faut sérialiser l’algorithme pour pouvoir augmenter le niveau de précision. Je l’ai fait et ça marche bien. Je l’ai pas publié au cas où tu voulais le faire toi.

#10

ta solution m’intéresse

#11

[code]#include <stdio.h>

double MoinsUnPuissanceN(const int n);

inline double MoinsUnPuissanceN(const int n)
{
return (n&1) ? -1 : 1;
}

void main()
{
int rang;
double p = 4;
while (scanf ("%d",&rang) == 0) getchar ();

for(int i = 1; i <= rang; ++i)
{
p += (double)(MoinsUnPuissanceN(i) * 4) / (double)(2 * i + 1);
}
printf(“valeur approchée de pi au rang %d : %.10f\n”, rang, p);
}[/code]

Voila, j’ai pas testé la limite (mais il accepte déjà beaucoup plus).

Si ta besoin de performance supplémentaire, il doit pas être bien compliqué de paralléliser ça avec openmp (en fait ça devrait prendre une ligne (en faisant gaffe que p doit être protégé)).

#12

Quel est l’intérêt du inline (A quoi sert-il ?)

#13

Le compilateur (s’il pense que c’est utile) va remplacer l’appel de la fonction par son code du coup ça permet d’économiser l’appel de fonction et tu gagne en performance. On pourrait utiliser une macro à la place, mais à ce moment là tu perd les informations de type.

Edit : un peu moins de transtypage :

[code]#include <stdio.h>

double MoinsUnPuissanceN(const int n);

inline double MoinsUnPuissanceN(const int n)
{
return (n&1) ? -1. : 1.;
}

void main()
{
int rang;
double p = 4;
while (scanf ("%d",&rang) == 0) getchar ();

for(int i = 1; i <= rang; ++i)
{
p += (MoinsUnPuissanceN(i) * 4.) / (2. * i + 1);
}
printf(“valeur approchée de pi au rang %d : %.10f\n”, rang, p);
}[/code]

#14

Ok , merci.
Au passage j’ai compilé ton source avec g++, avec gcc ça ne marche pas mais g++ n’aime pas le void main, il génère une erreur et il faut donc utiliser int main
Sinon tout baigne !!

#15

J’ai procédé à une comparaison : ta solution avec inline : 16s pour traiter avec 1000000000
Ma solution sans inline 31s pour la même valeur : il n’y a pas photo !!

Au passage : j’ai supprimé la ligne : double MoinsUnPuissanceN(const int n);
Et ça marche quand même
Alors pourquoi déclarer ce prototype juste avant la définition ?

#16

Ça marche très bien, faut juste suivre les indications :

[code]$ gcc -O2 -o pi pi.c
pi.c: In function ‘main’:
pi.c:16:3: error: ‘for’ loop initial declarations are only allowed in C99 mode
pi.c:16:3: note: use option -std=c99 or -std=gnu99 to compile your code
$ gcc -O2 -o pi pi.c -std=c99
$ time ./pi
valeur approchée de pi au rang 1000000000 : 3.1415926546

real 0m6.759s
user 0m6.748s
sys 0m0.008s[/code]
:wink:

Difficile de parler à sa place, mais je dirais que c’est probablement un réflexe. :mrgreen:

Et accessoirement en -O2 grâce au inline il fait aussi le constant-folding de MoinsUnPuissanceN() * 4.0 ce qui permet d’économiser en plus une multiplication flottante par itération (par contre en -O0 –edit: je voulais dire avec le niveau d’optimisation par défaut– il n’inline pas du tout, j’ai vérifié, donc le gain de performance dont parle zerimbak n’est probablement dû qu’au passage en itératif car je pense pas qu’il ait compilé en -O2).

#17

Il me semble que le c99 demande de déclarer les fonctions inline avant de les cécrire (mais je suis pas sûr).

Le -O0 compile en optimisant la taille du binaire c’est pour ça qu’il fait aucun inlining. Je ne crois pas que ce soit l’optimisation par défaut.

Tu as tout a fait raison pour ce qui est du constant folding, ça permet de limiter l’usage de calcul sur flottant (les calcul sur les flottants posent de gros problèmes de précision même pour les calcul simple).

Ca peut être rigolo de voir ce qu’OpenMP donne sur cette boucle, sur un multi-core on doit gagner encore pas mal.

#18

Hmm dans ce cas là je me suis planté, je parlais bien de l’optimisation par défaut sans aucun argument -O (bête réflexe, apparemment erroné : pas d’optimisation => -O0 :mrgreen:).

Ça dépend comment il cumule les résultats : accumulation séparément dans chaque thread puis accumulation des différents threads, ou bien accumulation synchronisée “au fil de l’eau” (forcément beaucoup moins efficace que l’autre alternative). Vu que j’ai jamais bossé avec OpenMP, je sais pas ce qu’il en est, mais j’imagine qu’il doit laisser le choix ?

#19

Au moins un bug :
avec la valeur 2147483647

ça ne s’arrête pas :slightly_smiling:

#20

Hmm dans ce cas là je me suis planté, je parlais bien de l’optimisation par défaut sans aucun argument -O (bête réflexe, apparemment erroné : pas d’optimisation => -O0 :mrgreen:).[/quote]
En fait O0 est une optimisation :slightly_smiling:

Ça dépend comment il cumule les résultats : accumulation séparément dans chaque thread puis accumulation des différents threads, ou bien accumulation synchronisée “au fil de l’eau” (forcément beaucoup moins efficace que l’autre alternative). Vu que j’ai jamais bossé avec OpenMP, je sais pas ce qu’il en est, mais j’imagine qu’il doit laisser le choix ?[/quote]
Ça n’a pas vraiment d’importance, tu lui demande de créer un thread de plus que ton nombre d’unité de calcul et chaque thread va incrémenter la variable quand il pourra. D’une certaine façon les calculs se feront de manière asynchrones.

Pour le bug, je pense que c’est un problème de dépassement de capacité des int donc, il suffit de mettre un unsigned lon pour arriver à 4294967296-1 comme limite (après ça deviens moins agréable à faire d’en gérer plus) :

[code]#include <stdio.h>

double MoinsUnPuissanceN(const int n);

inline double MoinsUnPuissanceN(const int n)
{
return (n&1) ? -1. : 1.;
}

void main()
{
unsigned long rang;
double p = 4;
while (scanf ("%d",&rang) == 0) getchar ();

for(unsigned long i = 1; i <= rang; ++i)
{
p += (MoinsUnPuissanceN(i) * 4.) / (2. * i + 1);
}
printf(“valeur approchée de pi au rang %d : %.10f\n”, rang, p);
}[/code]