Discussion :

[bogoss91]

Salut à tous!

J'essaie de faire un programme pour trouver des nombres premiers, mais je suis confronté à un problème : comment faire pour stocker des nombres entier supérieurs à 2^64 - 1 (unsigned long long int)?

Merci.

[droggo]

Hio,

Il y a des librairies pour ça.

Une des plus connues est GMP.

[koala01]

Salut,

Sauf erreur, il n'y a pas vraiment moyen

A moins que je ne dise une erreur, il n'est en effet pas prévu dans l'immédiat de rajouter un type plus grand que unsigned long long ...

Tu peux toujours envisager de travailler avec un bitset, qui devrait te permettre de gérer de nombres de n'importe quelle ordre de grandeur, mais, tu restera fortement embêté pour arriver à le représenter en base décimale , et ce, sans même parler des soucis pour arriver à gérer les divisions

Ceci dit, j'ai récemment (enfin, cela date d'il y a un mois ou deux) fait l'expérience avec un simple entier chez moi...

Mon "vieux clou" (un "antique" Athlon 1700 XP) a mouliné pendant plus de 7 heures pour me trouver les nombres premiers entre 0 et UINT_MAX... puis j'ai abandonné

Il parrait aussi que, avec 64 bits, on pourrait donner un numéro unique à chaque grain de sable présent sur terre... dés lors, estimes-tu réellement utile de vouloir aller plus loin

[zais_ethael]

Sauf erreur, il n'y a pas vraiment moyen

Tu fais erreur, beaucoup de langages, comme le Python ou le Java, proposent des entiers et des flottants codés sur un nombre indéfini de bytes. Ce serait certainement très simple à implémenter en C++, mais je ne connais pas de biblio qui le fait.

[bogoss91]

De toute façon, c'est complètement inutile de trouver les nombres premiers, alors un truc inutile de plus...

En fait je fais ça avec un pote, parce qu'on s'amuse à trouver les nombres entiers les plus grands possibles (hilarant... ) et là on en a trouvé un qui se rapproche de la valeur maximale que peut contenir un unsigned long long int et donc, il nous faut quelque chose qui peut stocker de plus grands nombres.

[koala01]

Tu fais erreur, beaucoup de langages, comme le Python ou le Java, proposent des entiers et des flottants codés sur un nombre indéfini de bytes. Ce serait certainement très simple à implémenter en C++, mais je ne connais pas de biblio qui le fait.

Comme le l'ai indiqué, le fait est qu'il n'y ait aucun type prévu pour supporter plus de 64 bits dans la norme...

Comme je l'ai indiqué aussi, il ne reste, à ma connaissance, que le bitset qui devrait permettre de faire coexister deux long long plus ou moins efficacement (car je crains qu'un tableau de deux entier long long ne vienne pas à ton secours sur ce coup)

Le fait que certains langages puissent le permettre ne signifie nullement que tous les langages doivent le faire

De toute façon, c'est complètement inutile de trouver les nombres premiers, alors un truc inutile de plus...

En fait je fais ça avec un pote, parce qu'on s'amuse à trouver les nombres entiers les plus grands possibles (hilarant... ) et là on en a trouvé un qui se rapproche de la valeur maximale que peut contenir un unsigned long long int et donc, il nous faut quelque chose qui peut stocker de plus grands nombres.

A la réflexion, il est vrai que tu devrais pouvoir arriver à tester des valeurs allant jusqu'à 128 bits, étant donné que seules les valeurs inférieures à la racine carrée du nombre sont à tester...

Mais tu en resterais de toutes façons confronté au problème de la représentation en décimale du nombre trouvé... Seul l'hexadécimal aurait une chance de représenter quelque chose de plus ou moins compréhensible (et t'obligeant encore à te "palucher" la conversion hexa->decimal )

[zais_ethael]

Le fait que certains langages puissent le permettre ne signifie nullement que tous les langages doivent le faire

Ce n'est pas forcément intégré au langage, en Java c'est une simple classe. Alors en C++, avec la rédéfinition d'opérateurs et les transtypages implicites, ce serait on ne peut plus simple à utiliser. Et oui, je sais très bien que ce n'est pas intégré à la biblio standard , pour ce qu'elle contient de toutes façons...

[droggo]

Dio,

De toute façon, c'est complètement inutile de trouver les nombres premiers, alors un truc inutile de plus...

En fait je fais ça avec un pote, parce qu'on s'amuse à trouver les nombres entiers les plus grands possibles (hilarant... ) et là on en a trouvé un qui se rapproche de la valeur maximale que peut contenir un unsigned long long int et donc, il nous faut quelque chose qui peut stocker de plus grands nombres.

Si ça ne sert à rien, pourquoi tant de personnes se fatiguent à chercher de nouveaux algorithmes pour ça ?

Je peux comprendre que ça ne te serve pas, mais ne fait pas de ton cas une généralité.

Pour aller plus loin, il faut une librairie de calcul multi-précision, soit existante, comme GMP, déjà citée, soit faite maison (un assez gros travail si on veut qu'elle soit performante).

Comme le l'ai indiqué, le fait est qu'il n'y ait aucun type prévu pour supporter plus de 64 bits dans la norme...

Comme je l'ai indiqué aussi, il ne reste, à ma connaissance, que le bitset qui devrait permettre de faire coexister deux long long plus ou moins efficacement (car je crains qu'un tableau de deux entier long long ne vienne pas à ton secours sur ce coup)

Le fait que certains langages puissent le permettre ne signifie nullement que tous les langages doivent le faire

A la réflexion, il est vrai que tu devrais pouvoir arriver à tester des valeurs allant jusqu'à 128 bits, étant donné que seules les valeurs inférieures à la racine carrée du nombre sont à tester...

Mais tu en resterais de toutes façons confronté au problème de la représentation en décimale du nombre trouvé... Seul l'hexadécimal aurait une chance de représenter quelque chose de plus ou moins compréhensible (et t'obligeant encore à te "palucher" la conversion hexa->decimal )

Tu as tout faux en l'occurrence.

Le bitset est sans le moindre doute une des pires solutions pour résoudre ce genre de problème.

[bogoss91]

J'ai téléchargé GMP mais j'ai pas du tout compris comment l'installer

[koala01]

<snip>
Tu as tout faux en l'occurrence.

Le bitset est sans le moindre doute une des pires solutions pour résoudre ce genre de problème.

J'ai peu etre tord en parlant de bitset, je l'accorde, mais dans ce cas, quelle solution proposerais tu toi

Par contre, je ne vois pas où, dans la citation que tu fais, j'ai tord en rappelant que l'on peut se contenter de tester les nombres plus petits que la racine carrée d'un nombre à tester, ni dans le fait que tu risque de toutes façons d'avoir des problème de représentation en base dix...

En deux mots, je te serait gré d'être attentif à tes citations

[koala01]

J'ai téléchargé GMP mais j'ai pas du tout compris comment l'installer

Si tu travailles avec Gcc (mingw ou similaire), tu peux installer MSYS et te baser sur les explications que je fournis dans mon Guide de la Compilation de Gcc sous windows (en particulier compiler GMPlib)...

Si tu travailles avec VC++, désolé, je ne suis pas assez habitué avec ce compilo pour pouvoir t'aider

[droggo]

Kio,

J'ai peu etre tord en parlant de bitset, je l'accorde, mais dans ce cas, quelle solution proposerais tu toi

Par contre, je ne vois pas où, dans la citation que tu fais, j'ai tord en rappelant que l'on peut se contenter de tester les nombres plus petits que la racine carrée d'un nombre à tester, ni dans le fait que tu risque de toutes façons d'avoir des problème de représentation en base dix...

En deux mots, je te serait gré d'être attentif à tes citations

A part le coup de la racine carrée, que j'ai oublié de couper, tu as tout faux, je me répète.

La représentation décimale de grands nombres n'est pas plus difficile que celle des nombres plus habituels, c'est exactement le même algorithme qu'on utilise.

Et il ne s'agit surtout pas de faire une représentation en base 10 dans les données stockées, rien de tel pour faire un programme qui rame.

La solution est de faire un tableau d'un type unsigned (le plus grand supporté par le matériel, pas seulement par le compilateur), et de traiter les morceaux successivement, exactement comme on traite à la main notre représentation décimale.
Il faut bien entendu ajouter un champ donnant la taille effectivement utilisée, et un autre donnant le signe.
A partir de là, tu fais ce que tu veux.

[xs4all]

C'est pas très difficile de stocker un entier de grandeur aléatoire, il suffit de faire une liste chainée ou chaque noeud contient un short/int/long dépendant du nombre de digits qu'on veut par noeud, ensuite il te reste un sale boulot au niveau des algo d'addition/soustraction/multiplication/division/mod/etc. Mais sinon ça reste dans le monde du très possible!

[droggo]

Gio,

C'est pas très difficile de stocker un entier de grandeur aléatoire, il suffit de faire une liste chainée ou chaque noeud contient un short/int/long dépendant du nombre de digits qu'on veut par noeud, ensuite il te reste un sale boulot au niveau des algo d'addition/soustraction/multiplication/division/mod/etc. Mais sinon ça reste dans le monde du très possible!

Une liste chaînée est une solution, mais un tableau est bien préférable dans ce cas, pour une question de temps d'accès aux données.

Dans les calculs multi-précisions, le temps de calcul augmente vite si on utilise des nombres assez grands, et il faut rapidement faire une version suffisamment optimisée en vitesse, sinon on risque d'attendre les résultats un peu trop longtemps.

[xs4all]

Ouais j'ai eu des mauvaise surprises avec les mutliplications... j'addtionnais n fois un nombre m... c'était vraiment trop long! Mais bon la mon algo semble faire le tout en O(lognlogn) (En fait, j'ai vraiment des doutes sur ma façon de calculer la complexité de mon algo étant donnée que la fft se fait en O(nlogn)...).

Je vais revoir ma structure de donnée pour mettre le tout dans un tableau, je n'avais pas du tout pensé à ça! Ce serait beaucoup plus simple, je crois et plus rapide!

[Jean-Marc.Bourguet]

Ouais j'ai eu des mauvaise surprises avec les mutliplications... j'addtionnais n fois un nombre m... c'était vraiment trop long! Mais bon la mon algo semble faire le tout en O(lognlogn) (En fait, j'ai vraiment des doutes sur ma façon de calculer la complexité de mon algo étant donnée que la fft se fait en O(nlogn)...).

Utiliser des fft pour la multiplication n'est rentable que pour des très grands nombres. Il y a d'autres algo qui sont d'une complexité calculatoire intermédiaire entre le n carré de l'algo naïf et le N log N de l'utilisation des FFT mais avec en pratique des constantes telles qu'ils sont meilleurs dans la plupart des cas.

[xs4all]

J'ai une question aussi naïve que l'algo en n^2 au sujet des complexités. J'ai calculé mon algo en O(lognlogN) pour le calcul n*N où n et N sont les nombres, mais j'ai O(X*x) où X et x sont respectivement les longueurs de n et N. Si je veux comparer avec Karatsuba, fft ou autre, il utilise n comme étant le nombre ou le nombre de chiffre composant le nombre?

[Jean-Marc.Bourguet]

J'ai une question aussi naïve que l'algo en n^2 au sujet des complexités. J'ai calculé mon algo en O(lognlogN) pour le calcul n*N où n et N sont les nombres, mais j'ai O(X*x) où X et x sont respectivement les longueurs de n et N. Si je veux comparer avec Karatsuba, fft ou autre, il utilise n comme étant le nombre ou le nombre de chiffre composant le nombre?

Nombre de chiffres.