Discussion :

[Invité]

Bonjour,

Je suis surpris d'une erreur d'addition dans le programme C ci dessous.

Le but du programme est de trouver le nombre de fibonnaci tel que F(x) mod 2^32 == 0.

Mon problème vient d'une addition de float particulière...

Code :

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

1
2
3
35 => 9227465 : mod = 9227465.0
36 => 14930352 : mod = 14930352.0
37 => 24157816 : mod = 24157816.0

normalement a la position 37 nous devrions avoir 24157817.

voici mon code :

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
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
int main (void)
{
    float f,x;
    float f1,f2;
    int stop = 0;
    float ans = pow(2,32);
    f1 = 0;
    f2 = 1;
    for(x=37;stop!=1;x++)
    {
        f = f1+f2;
        if (fmod(f,ans) == 0)
            stop =1;
 
        printf("%.0f => %.0f : mod = %.01f\n",x,f, fmod(f,ans));
        f2 = f1;
        f1 = f;
    }
    return 0;
 
}

[Pouet_forever]

Ce qu'il faut savoir avec les nombres flottants c'est qu'ils font une approximation

[Invité]

C'est dommage (pour mon cas, car sinon ça doit avoir une raison). Alors comment faire pour passer outre cette approximation ?

[estofilo]

Pour avoir une meilleure précision, tu peux utiliser le type double au lieu du float. D'autant plus que les fonctions pow() et modf() sont définies pour prendre en argument et renvoyer des double et pas des float.
D'autre part le code que tu montres commençe à x=37, donc on ne peut pas reproduire tel quel le résultat que tu montres.

[droggo]

Soa,

Même le type double posera des problèmes d'approximations, c'est intrinsèque à la représentation des réels.

Si tu veux des calculs exacts, il faut utiliser des entiers. Et comme les valeurs que tu cherches dépassent les limites des types standards, il faut utiliser une bibliothèque de calcul en multi-précision. Il y a entre autres GMP qui marche très bien.

[Invité]

Pour avoir une meilleure précision, tu peux utiliser le type double au lieu du float. D'autant plus que les fonctions pow() et modf() sont définies pour prendre en argument et renvoyer des double et pas des float.
D'autre part le code que tu montres commençe à x=37, donc on ne peut pas reproduire tel quel le résultat que tu montres.

Pour le départ à 37 c'est une erreur de ma part dans le collage du code sur le forum, on peut partir à 1 tout simplement en remplaçant x=37 par x=1 dans la boucle for.

Soa,

Même le type double posera des problèmes d'approximations, c'est intrinsèque à la représentation des réels.

Si tu veux des calculs exacts, il faut utiliser des entiers. Et comme les valeurs que tu cherches dépassent les limites des types standards, il faut utiliser une bibliothèque de calcul en multi-précision. Il y a entre autres GMP qui marche très bien.

Je pensais en effet à GMP mais je voulais voir s'il n'y avait pas d'autres solutions avant d'utiliser cela. Et bien tant pis. Merci à tous. Je vais tester GMP.

[diogene]

Le but du programme est de trouver le nombre de fibonnaci tel que F(x) mod 2^32 == 0.

Il n'y a pas besoin de calculer 2^32 pour cela, ni d'utiliser des float ou des double.

On a : F(x) = F(x-1) + F(x-2)
alors : F(x)mod(n) = ( F(x-1)mod(n) + F(x-2) mod(n) ) mod(n)
avec n = 2^32

Comme l'arithmétique des nombres entiers unsigned est une arithmétique mod 2^p, ou 2^p - 1 est la plus grande valeur représentable par ce type, il suffit de représenter F(x) par un nombre d'un type entier unsigned possédant 32 bits (ou plus), par exemple unsigned long, et d'ignorer purement et simplement pendant le calcul les dépassements de capacité au delà des 32 bits.

Pour illustrer, supposons que n = 16 = 2^4 et F(x) sur 4 bits :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
x      F(x)  F(x) mod 16
.....
 6      8      8   (1000)
 7     13     13   (1101)
 8     21      5 = (8+13) mod(16)  1000+1101 = (1)0101 
 9     34      2 = (5+13) mod(16)  1101+0101 = (1)0010
10     55      7 = (5+2)  mod(16)  0101+0010 =    0111
11     89      9 = (2+7)  mod(16)  0010+0111 =    1001
12    144      0 = (7+9)  mod(16)  0111+1001 = (1)0000
.....

F(3 221 225 472) == 0 mod(2^32)

[estofilo]

En suivant la méthode de diogene, il me semble que la solution de F(x) mod 2^32 == 0 est un x qui est de l'ordre de 3 milliards, ce qui doit donner un F(x) absolument gigantesque, qui dépasse ce qui est gérable par les types natifs du langage C.

Il doit être possible de recouper le résultat avec la méthode générique de calculer les vraies valeurs de F(x) et le reste de la division à chaque tour de boucle en utilisant GMP, mais ça risque de prendre un temps de calcul considérable.

[diogene]

La solution que j'ai obtenue était cachée dans mon message précédent

[Invité]

De retour de vacances j'ai pris note des messages.

J'avoue ne pas avoir encore compris la réponse de diogène mais je m'y penche.

Merci pour les explications.