Je suis nouveau ici donc j'ignore si je suis dans la bonne section, c'est, vu les titres, celle qui me semblait le plus appropriée!
Voilà, je suis pas trop doué en programmation mais j'aime bien les défis/énigmes et, dans le genre, celles du " Défi Turing " sont vraiment chouettes (j'y passe mes soirées depuis 2-3 jours). Je ne joue pas vraiment la carte de l'optimisation parce que j'sais pas trop comment m'y prendre...donc je passe globalement en force brute je pense.
Bon, il y a cette question:
La somme des nombres premiers entre 1 et 10 vaut 2 + 3 + 5 + 7 = 17.
Trouver la somme des nombres premiers compris entre 1 et 10'000'000.
Qui n'a rien de bien méchant...seulement voilà, mon code (qui est très lent) trouve la somme correcte pour les premiers entre 1 et 100 et semble tout à fait cohérent pour les premiers de 1 à 900 000 mais renvoie des résultats négatifs (?!) lorsqu'il passe la barre du 1 000 000...Or, comme il prend 4h pour trouver la somme des premiers <= 10 000 000...je suis assez frustré!
Si vous aviez des conseils à propos de mon code que j'inscris ci-dessous ou encore sur des "méthodes" d'optimisation (faut-il une imagination délirante pour trouver des méthodes optimisées ou y-a-t-il des disciplines qui se penchent spécifiquement sur la réduction de la complexité?), je suis totalement preneur!
Merci à tous!
NB: langage C :-)
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
void main()
{
int f=2;
int s=0;
while(f<=100)
{
printf("%i\n",f);
s+=f;
int k=0;
while (k!=f)
{
k=2;
f++;
while(f%k!=0)
{
k++;
}
}
}
printf(" %i\n",s);
}
Langage C, soit espace mémoire limité pour stocker tes entiers, donc dépassement des bornes et retour dans les négatifs (puisque tu utilises des types signés).
Il te faudrait donc utiliser des types à précision arbitraire (voir du codé de GMP en C), et pourquoi pas passer à des types non signés puisque tu travailles sur des entiers naturels.
Je pense que le fait qu'il te renvoie un nombre négatif est du au fait que tu ais dépassé la limite de la variable. Je m'explique, un type tel que les entiers (int | Integer), si codé sur 4 octets (4 * 8bits) a une valeur maximum de 4 294 967 295 si non signé (sinon, il faut diviser par deux je crois). Or si le type est signé, alors le minimum est un négatif (ici 2 147 483 647 je crois).
En gros, ta variable atteint le maximum (2 147 483 647 dans mon exemple) et continu d'augmenter mais en repassant par la valeur minimale (ici -2 147 483 647). En gros, c'est un peu comme un cercle.
EDIT : Trop lent... Ou alors entwanne trop rapide
- Edité par Alexandre Gérault 20 février 2016 à 19:08:45
On pourrait s'attendre à recevoir un NaN ou un +infini dans le cas ou on passe la limite...je découvre ce comportement « circulaire »...
Il semble que les int en C soient codés sur 16 bits, pourtant, leur limite chez moi est bien celle que vous soupçonniez Alexan14 (2^31-1)! C'est assez étrange...et, si selon les conseils de Entwanne, j'utilise des unsigned long long...ça ne change rien !
Même résultat négatif...comme si je n'avais pas changé le type...Je vois que le .exe résultant de la compilation est en 32bits, cela forcerait-t-il la variable a être codée sur 32bits??
C'est drôle mais la limite que je donnais était purement aléatoire (je n'avais pas de convertisseur autre que la calculatrice windows donc j'ai seulement converti 4 octets ).
Sinon, en effet, c'est assez drôle que tu ais un résultat négatif avec des unsigned... Tu as gardé le même code j'imagine ?
EDIT : Tu dis que les int semblent codés sur 16bits (soit 2*1 octet) mais il me semble que cela change selon les machines sur laquelle le programme est compilé (ce qui nous oblige à passer par des types à taille fixe quand on programme en réseau si je ne me trompe pas). Essaye de voir dans un autre programme la limite de chaque type, signé et non-signé.
- Edité par Alexandre Gérault 21 février 2016 à 12:01:21
Seulement remplacé les int par unsigned long long (je suppose que ça suffit...)
Mais, c'est vraiment pas normal que les int qui sont supposés être en 16bits (32767 au max) aillent jusque 2^(31)-1...Je comprends pas.
EDIT: Je viens de lire votre EDIT, je vais chercher oui...Dans le pire des cas il y a toujours moyen de convertir les entiers en tableaux et de les additionner ainsi...mais c'est pas super et puis c'est ennuyeux à faire et ce serait commode de pouvoir changer le type!
Seulement remplacé les int par unsigned long long (je suppose que ça suffit...)
Il faut aussi changer le flag du printf, remplacer %i par %u.
La taille d'un int n'est pas fixée par la norme, et peut donc varier selon les compilateurs et les architectures, de même pour celle d'un long. Par contre tu es sûr que sizeof(int) <= sizeof(long) <= sizeof(long long).
Encore une fois, il va te falloir des nombres à précision « infinie ». Et la bibliothèque GNU MP répond très bien à cette problématique.
Au passage, l'infini et les NaN existent pour les nombres flottants, mais pas pour les int.
Du coup j'ai porté le code sur Matlab me disant que celui-ci travaillait d'office en double...c'était horriblement lent! Donc je suis reparti sur le code en c en changeant les flags et là, c'est pas mal, ça ne va plus dans les négatifs en tout cas (!) par contre la réponse fournie n'est pas correcte sans que je comprenne pourquoi...elle me semble petite (de l'ordre de 3*10^9) et je me demande pourquoi il faudrait recourir à une précision "infinie" via cette bibliothèque GNU?
En principe la somme des nbres premiers <= 10000000 peut grossièrement être majorée par 10^14 ce qui est dans le cadre d'un unsigned long long int. Donc je ne comprends vraiment pas le problème. (à moins qu'encore une fois la taille n'étant pas fixée par la norme, je ne dispose pas de 2^64...)
Bonne journée!
EDIT: petit test rapide sur la somme, effectivement, ça "boucle" encore...donc le type long long ne suffit pas, je me renseignerai dés que possible sur la fameuse bibliothèque. Une source en particulier de renseignement à propos de GMP?
Tu peux connaître la taille en octets du long long en affichant sizeof(long long), et tu seras fixé. Si tu observes que ça fait 8 et que pourtant tes calculs restent faux, assure-toi d'utiliser des unsigned long long partout où tu es amené à manipuler d'aussi grands nombres.
Pour GMP, je te propose le site officiel, qui comprend un lien vers la documentation : https://gmplib.org/
Yop, la somme des entiers (non premierrs) entre 1 et 10000000 c'est n(n+1)/2 avec n valant 10M donc ~ 5e13. Le type "uint64_t" va jusqu'à 1.85e19. Donc ça doit largement rentrer. Donc c'est que tu dois faire des temporaires qui n'ont pas le bon type quelque part ...
Testé en C++ avec un code qui commence par faire un crible puis accumule les résultats, pour 1M, ça prend 19 secondes. Donc il doit y avoir d'autres astuces mathématiques à trouver pour gagner du temps. Une astuce programmatique consiste à générer tout ça par méta-programmation mais c'est ignoblement bourrin.
Oui Ksass`Peuk, j'essaierais bien un crible pour optimiser :-)
Je ne m'attendais pas à ce que cette question pose problème en fait (d'où la méthode brutale et intuitive), mais c'est bien, je découvre comment manipuler des grands nombres!
Avec un size of il s'avère que le nombre est bien codé sur 8octets mais il se comporte de façon étrange, déjà sa valeur maximale n'est pas 2^(64)-1 et si je demande d'afficher cette valeur en théorie maximale (18 446 744 073 709 551 615), alors la machine renvoie un message d'erreur assez explicite genre "integer constant is so large that it is unsigned" et "only in iso C90" ... bref, elle n'en veut pas.
Et en coupant dans le nombre pour chercher sa limite "effective", par exemple en demandant d'afficher 18446744073, le programme affiche 1266874889...Bref, ne comprenant pas la logique, j'irai voir cette bibliothèque dés que j'aurai le temps!
Oui Ksass`Peuk, j'essaierais bien un crible pour optimiser :-)
Le crible d'eratosthène marche. Mais ce n'est pas suffisant, il faut d'autres astuces.
Luxien a écrit:
Avec un size of il s'avère que le nombre est bien codé sur 8octets mais il se comporte de façon étrange, déjà sa valeur maximale n'est pas 2^(64)-1 et si je demande d'afficher cette valeur en théorie maximale (18 446 744 073 709 551 615), alors la machine renvoie un message d'erreur assez explicite genre "integer constant is so large that it is unsigned" et "only in iso C90" ... bref, elle n'en veut pas.
C'est juste une histoire de literal. Quand tu mets un fichier tel que 12345, son type immédiat et "int". Pour avoir un unsigned, il faut suffixer avec "u". Pour avoir un unsigned long, avec "ul" (12345ul) etc.
Dites, je sue des petits pois pour installer gmp...
Il y a bien ce tuto (il y en a d'autre...)...J'utilise bien MinGW mais je rencontre un problème dans les premiers instants de l'installation de MSYS (image).
J'avais repéré qu'il y avait déjà un MSYS dans MinGW, je l'ai donc supprimé...comme un MSYS est tout de même présent dans C:/ malgré cette erreur dans le terminal, je poursuis avec les éléments à ma disposition...le ./configure je le fais sans rajouter de chemin vers un IDE (je n'en utilise pas)...mais au final, lorsque je tente de compiler le code d'essai proposé le terminal affiche un message disant qu'il ne trouve pas gmpxx.h...
En fait, comme j'ai été contraint de sauter certaines étapes je me dis qu'il n'y a aucune raison pour qu'un lien existe entre les actions dans C:/MSYS et C:/MinGW...Finalement, pas de gmp.h ni de gmpxx.h dans le C:/MinGW/include.
Une aide serait la bienvenue encore une fois...merci à vous!
Bon, pour répondre à la question du 22 février, quand on joue avec des unsigned long long en C le printf doit être du type printf("%llu")...
Coté GMP, je ne m'en sors vmt pas, pas du tout inspiré par ce problème d'installation de MSYS...
Sinon, j'ai un peu cherché sur le crible d’Ératosthène, codé quelque chose de pas très bon qui plantait assez vite...J'ai trouvé cette version sur le net, que j'ai un peu adaptée, qui est très lisible et, à mon gout, très classe:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
const int MAX = 10000000;
int main()
{
unsigned long long somme=0;
bool tab[MAX];
for (int i = 0; i < MAX; i++)
{
tab[i] = true;
}
tab[0] = false;
tab[1] = false;
for (int i = 2; i < MAX; i++)
{
if (tab[i]) // n’a pas été rayé
{
for (int j = i*2; j < MAX; j += i)// on raye le reste (poser int j=i*i serait fait planter plus vite)
{
tab[j] = false;
}
}
}
for (int i = 0; i < MAX; i++)
{
if (tab[i])
{
somme+=i;
}
}
printf("\n");
printf("La somme vaut: %llu\n",somme);
}
Problème...je peux lui faire sommer les premiers de 1 à 1 000 000 en quelques millisecondes...mais à 10 000 000 ça plante ><
× Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
× Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique
Blog - GitHub
Blog - GitHub
Blog - GitHub
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique
entwanne — @entwanne — Un zeste de Python — La POO en Python — Notions de Python avancées — Les secrets d'un code pythonique
Posez vos questions ou discutez informatique, sur le Discord NaN | Tuto : Preuve de programmes C
Posez vos questions ou discutez informatique, sur le Discord NaN | Tuto : Preuve de programmes C
Posez vos questions ou discutez informatique, sur le Discord NaN | Tuto : Preuve de programmes C