Discussion :

[syrll]

Bonjour à tous !

Je suis en train de créer un programme pour trouver des possibilités des briques d'Euler (parallélépipède dont les arrêtes et les diagonales des faces sont des nombres entiers).

Malheureusement, je suis confronté à un problème, visiblement fréquemment posé sur le forums (mais je n'ai tout de même pas trouvé la solution)

Voici le 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
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
 
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>
 
#define MAX 100000000000000 //cent mille milliards
#define STRLEN_MAX 15 //taille (en nombre de caractères) du nombre MAX
 
int CalculerEtTester(unsigned long long nb1, unsigned long long nb2);
 
int main()
{
    //Ouverture d'un fichier servant à enrtegistrer là où le programme s'était arrêté la dernière fois
    FILE* fichier = NULL;
    unsigned long long valeur = 0; //valeur indiquant là où programme s'étati arrêté
    char str[STRLEN_MAX];
 
    fichier = fopen("position.txt", "r");
 
    if(fichier != NULL)
    {
        fgets(str, STRLEN_MAX, fichier);
        valeur = strtoull(str, (char **)NULL, 10); //convertir la valeur en unsigned long long
    }
    else
        valeur = 1;
 
    fclose(fichier);
 
    //trois valeurs correspondant aux arrêtes du parallelépipède
    unsigned long long A;
    unsigned long long B;
    unsigned long long C;
 
    for(A = valeur ; A < MAX ; A++)
    {
        //enregistrement d'où en est de programme dans le fichier
        FILE* fichier = NULL;
        char str[STRLEN_MAX];
 
        fichier = fopen("position.txt", "w+");
        sprintf(str, "%I64u", A);
        fputs(str, fichier);
 
        fclose(fichier);
 
        for(B = A ; B < MAX ; B++)
        {
            if(CalculerEtTester(A, B)) //Si √(A² + B²) est un entier...
            {
                for(C = B ; C < MAX ; C++)
                {
                    if(CalculerEtTester(B, C )&& CalculerEtTester(C, A))
                        printf("%I64u - %I64u - %I64u \n", A, B, C);
                }
            }
        }
    }
    return 0;
}
 
int CalculerEtTester(unsigned long long nb1, unsigned long long nb2)
{
    long double res = fabs(sqrt(pow(nb1, 2) + pow(nb2, 2)));
 
    if (fabs(res - floor(res)) == 0.0f) //si le nombre est enrier (en soustrayant au nombre sa partie entière, on obtient sa partie décimale)
        return 1;
    else
        return 0;
}

Voici le premier chiffre que me donne mon programme (après avoir mouliné quelques secondes) :

1 - 67108864 - 87728297

Mais, après avoir vérifié les calculs, je me suis rendu compte que sqrt(pow(1, 2) + pow(67108864, 2)) soit √(1² + 67108864²) vaut environ 67108864.000000007450580596923828, ce qui n'est pas une valeur entière...
Je pense que cela est dû aux long double qui ne sont peut-être pas si précis que cela, mais je ne suis pas sûr, et surtout, je ne sais pas comment résoudre cela.

Merci de m'aider,

Syrl

[the Hound]

Bonjour Syrll,

Effectivement, un long double n'est pas suffisamment précis pour stocker ce genre de valeur.
Le problème est qu'à part recoder à la main toutes les opérations (sqrt, fabs tout ça) et créer un type ayant potentiellement une "infinité" de chiffres après la virgule, aucun type de base ne peut être utilisé puisque tu auras toujours ce problème de précision.
Je pense que c'est l'algo qui est à revoir, parce qu'il fait des casts de flottants dans tous les sens (avec pertes de précision à la clé) et que même si il est mathématiquement valide, en pratique il ne couvre pas correctement tous les cas, comme tu as pu le constater.

[schonai]

Bonjour,
A titre personnel je ne l'ai jamais utilisé mais de ce que j'ai entendu, tu pourrais trouver ton bonheur avec la bibliothèque GMP. Elle est destinée aux calculs sur des très grand nombres, et aux calculs formels.

[syrll]

Merci beaucoup pour vos réponses
Oui, j'en étais également arrivé à cette bibliothèque, mais malheureusement, j'ai du mal à l'installer (j'ai toujours galéré à utiliser des bibliothèques...).
Pouvez-vous m'aider ? Plus précisément, j'aimerais savoir comment indiquer à Code::Blocks (IDE que j'utilise) où se trouve le fichier à inclure.

J'ai également trouvé une autre solution possible : Savoir si le nombre est un carré parfait sans calculer sa racine. On sait qu'un carré parfait :

• est multiple de 5 à une unité près ;
• est multiple de 8, à 0, 1 ou 4 près ;
• a un résidu (je n'ai pas encore bien saisi ce que c'est) différent de 2, 3, 5, 6 et 8 ;
• est divisible par 3 et 4 ou alors il l'est si on lui soustrait 1.

Ou alors, je pourrais trouver les facteurs premiers du nombre, et s'ils se regroupent par 2, c'est un carré parfait...

Syrl

[ternel]

En général, l'égalité est à tester comme "l'écart entre les nombres est assez petit", avec assez petit défini en fonction du type et de la valeur.

Généralement, on se base sur std::numeric_limits<double> (regarde la ref de <limits>)

On a une explication du principe dans la faq

[the Hound]

En général, l'égalité est à tester comme "l'écart entre les nombres est assez petit", avec assez petit défini en fonction du type et de la valeur.

L'égalité entre nombre flottants.

M'enfin, ici le problème est posé de telle manière qu'avec uniquement des types builtins c'est difficile...
Donc vaut mieux faire comme schonai suggérait, utiliser GMP ou alors faire des calculs sur des entiers.
A voir lequel est le plus rapide des deux.