Discussion :

[drogeek]

Bonjour,
Ceci est mon premier message, j'espère qu'il correspondra aux normes.
Je cherche à calculer le nième terme de la suite de Fibonacci au-delà de la taille d'un long long (64bits).
J'utilise ainsi des tableaux d'entiers.
Après avoir réussi à faire fonctionner le programme sur un tableau d'entier d'une taille fixée, j'essaie maintenant d'allouer/réallouer la bonne taille au cours du programme.
Cependant j'obtiens un problème à partir d'un certain n de fib(n) ( 31 pour être exact ).

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int AddNbr (int* nbr1, int* nbr2, int base, int taille); 
void InitNbr (int* nbr, int taille);
void AffichNbr (int* nbr, int* taille);
void CopyTab (int* nbr1, int* nbr2, int taille);
int* FibGdNbr(int* nbr1, int* nbr2, int n, int* taille);
int NbrChiffre (int n);
 
int main(int argv, char* argc[])
{
    int *nbr1, *nbr2;
    int n=atoi(argc[1]);
    int taille=1;
    nbr1=malloc(sizeof(int));
    nbr2=malloc(sizeof(int));
    nbr1[0]=1;
    nbr2[0]=1;
    //InitNbr(nbr1,taille);
    //InitNbr(nbr2,taille);
    AffichNbr(FibGdNbr(nbr1,nbr2,n,&taille), &taille);
    free(nbr1);
    free(nbr2);
    return EXIT_SUCCESS;
}
 
/*int NbrChiffre (int n) // fonction bte qui essaie de dterminer  l'avance le nombre de chiffres dans fib(n) (le problme tant qu'on ne peut pas le dterminer aprs fib(92) car impossible de stocker la valeur dans une variable)
 
{
    int cpt=0;
    long long int nbr;
    nbr=1/sqrt(5)*((int)pow( (1+sqrt(5))/2, n) );
    while (nbr>=1)
    {
        nbr/=10;
        cpt++;
    }
    return cpt;
}
*/
 
int AddNbr (int* nbr1, int* nbr2, int base, int taille) // renvoie 1 si depassement
{
    int i, ret=0;
    for (i=0; i<taille; i++)
    {
        ret=nbr1[i]+nbr2[i]+ret;
        if (ret>=base)
        {
            nbr1[i]=ret-base;
            ret=1;
        }
        else
        {
            nbr1[i]=ret;
            ret=0;
        }
    }
    return ret;
}
 
/*void InitNbr (int* nbr, int taille) //inutile si ma taille de tableau est de 1 seule case au dpart
{
    int i;
    nbr[0]=1;
    for (i=1; i<taille; i++)
        nbr[i]=0;
}
*/
 
void AffichNbr (int* nbr, int* taille) // je passe un pointeur pour tre sr que la valeur de taille soit la mme que celle du main
{
    int i;
    for (i=0; i<*taille; i++)
        printf("%d", nbr[(*taille)-1-i]);
    printf("\n");
}
 
void CopyTab (int* nbr1, int* nbr2, int taille)
{
    int i;
    for (i=0; i<taille; i++)
        nbr1[i]=nbr2[i];
}
 
int* FibGdNbr(int* nbr1, int* nbr2, int n, int *taille)
{
    int i=0;
    int* tmp=malloc((*taille)*sizeof(int));
    if(n==0 || n==1)
        return nbr1;
    else
        while(i<n-2)
        {
            CopyTab(tmp,nbr2, *taille);
            if( AddNbr(nbr2,nbr1,10,*taille) == 1 ) // si le nombre de chiffres de la somme de nbr1 et nbr2 (avec nbr2>nbr1) dpasse le nombre de cases du tableau alors
            {
                nbr2=realloc(nbr2,*(taille)+1); // on agrandit la taille de nbr2 d'une case
                nbr2[*taille]=1; // on applique le reste non appliqu prcdement,  cette nouvelle case
                CopyTab(nbr1,tmp,*taille); // on copie les lments avant d'augmenter la taille de nbr1 
                nbr1=realloc(nbr1,(*taille)+1);
                nbr1[*taille]=0; // on met  0 la nouvelle case pour ne pas affecter la somme au prochain tour de boucle
                tmp=realloc(tmp,(*taille)+1); // et on ajoute une case  tmp qui recevra nbr2 
                (*taille)++;
            }
 
            else
                CopyTab(nbr1,tmp,*taille);
            i++;
        }
        free(tmp);
        return nbr2;
}

et l'erreur renvoyée ( je n'ai jamais eu d'erreur de ce type auparavant, je ne saurais trop comment la régler )

1.*** glibc detected *** ./nombre.exe: realloc(): invalid pointer: 0x00000000024b3050 ***
2.======= Backtrace: =========
3./lib/x86_64-linux-gnu/libc.so.6(+0x78a96)[0x7f1966f9ca96]
4./lib/x86_64-linux-gnu/libc.so.6(realloc+0x2e6)[0x7f1966fa10d6]
5../nombre.exe[0x400973]
6../nombre.exe[0x4006d7]
7./lib/x86_64-linux-gnu/libc.so.6(__libc_start_main+0xed)[0x7f1966f4530d]
8../nombre.exe[0x4005a9]
.......

Tout commentaire ou critique est la bienvenue.
Merci.

[Neckara]

Au lieu d'un tableau, utilise plutôt une file, ça évitera de faire des realloc en boucle et tu aura beaucoup plus d'espace mémoire
(un tableau est un bloc de mémoire contigu)

Ensuite rien ne vaut le précalcul.
A chaque f(n) si le f(n) n'existe pas, enregistre la solution dans ou plusieurs fichiers
Ainsi quand tu devrait faire un f(n+k) tu pourra repartir de f(n). Tu gagnera ainsi pas mal de temps.

[drogeek]

Au lieu d'un tableau, utilise plutôt une file, ça évitera de faire des realloc en boucle et tu aura beaucoup plus d'espace mémoire
(un tableau est un bloc de mémoire contigu)

Le problème serait donc que le realloc essaie d'ajouter au tableau une case mémoire déjà allouée? Du coup le problème ne se manifesterait pas forcément à la 31ième itération de Fibonacci si je redémarrais.

Ensuite rien ne vaut le précalcul.
A chaque f(n) si le f(n) n'existe pas, enregistre la solution dans ou plusieurs fichiers
Ainsi quand tu devrait faire un f(n+k) tu pourra repartir de f(n). Tu gagnera ainsi pas mal de temps.

L'accès à une fichier est plus lent qu'un accès mémoire. Cela serait compensé par la boucle qu'il faudrait faire pour atteindre le dernier élément de la liste chainée?
N'existe-t'il donc aucun moyen d'augmenter la taille d'un tableau à l'aide d'un realloc si la case suivant la dernière case d'un tableau est déjà allouée?

[valefor]

N'existe-t'il donc aucun moyen d'augmenter la taille d'un tableau à l'aide d'un realloc si la case suivant la dernière case d'un tableau est déjà allouée?

Mon opinion est de finir dans la voie que tu as ouvert. Accéder à un fichier et faire des listes chaînées complexifierai ton code... Et comme il n'est déjà pas clean en version "simple" ...

[drogeek]

Mon opinion est de finir dans la voie que tu as ouvert. Accéder à un fichier et faire des listes chaînées complexifierai ton code... Et comme il n'est déjà pas clean en version "simple" ...

Merci, le problème était évidement cela, l'oublie de sizeof(int) dans mes realloc. (je peux monter jusqu'à plus de f(1000) maintenant).
Cependant votre remarque sur la propreté de mon code m'intéresse. Il faudrait que je teste la valeur renvoyée ( si elle est égale à NULL ) pour chaque *alloc.
D'autres choses clochent?

[diogene]

Une chose me chagrine :

- FibGdNbr() peut modifier les variables locales nbr1 et nbr2 à cause des realloc().

- AffichNbr(FibGdNbr(nbr1,nbr2,n,&taille), &taille); utilise la valeur retounée par FibGdNbr() qui est la nouvelle valeur prise par nbr1 ou nbr2 dans la fonction, donc à priori pas de problèmes.

- Par contre, les valeurs de nbr1 et nbr2 dans main() sont inchangées et lorsqu'on fait free(nbr1); free(nbr2) on a affaire à des adresses qui sont possiblement invalides si une reallocation a déplacé les données.

[valefor]

C'est une erreur au niveau d'un realloc. Tu n'en as que deux dans ton programme. Donc c'est autour de ces points qu'il faut chercher. Je suppose que tu dois aller modifier un pointeur en écrivant où il ne faut pas...

J'ai aussi un truc qui me semble louche (mais c'est juste une impression, je n'ai pas regardé en détail), c'est que parfois tu fais des

Code :

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

alloc((*taille)*sizeof(int))

et parfois des

Code :

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

alloc((*taille))

. Tu n'oublie pas le sizeof(int) parfois ?

Dernière remarque, tu devrais systématiquement vérifier ce que te retourne *alloc() (bien que ton problème ne semble pas être un problème de pointeur null).