VARIABLES 1 BITS DANS UN CRILBE D'ÉRATOSTÈNE
essirc
Messages postés
48
Date d'inscription
vendredi 23 juillet 2004
Statut
Membre
Dernière intervention
26 juillet 2005
-
26 juil. 2004 à 11:41
Utilisateur anonyme - 31 juil. 2004 à 09:38
Utilisateur anonyme - 31 juil. 2004 à 09:38
Cette discussion concerne un article du site. Pour la consulter dans son contexte d'origine, cliquez sur le lien ci-dessous.
https://codes-sources.commentcamarche.net/source/24881-variables-1-bits-dans-un-crilbe-d-eratostene
https://codes-sources.commentcamarche.net/source/24881-variables-1-bits-dans-un-crilbe-d-eratostene
31 juil. 2004 à 09:38
http://perso.wanadoo.fr/therese.eveilleau/pages/truc_mat/textes/r_carree_anc.htm
Le problème c'est qu'il existe de nombreux algorithmes pour faire ca. Je ne sius pas sur qu'ils soient tous aussi performants. Puis en binaire ca doit être différent.
29 juil. 2004 à 17:09
Mais c'est pas ca que je disais au début.
28 juil. 2004 à 17:11
Ce que ne fonctionne pas avec des variables d'un seul bit, c'est :
n[0] corespond a 2
n[1] corespond a 3
n[2] corespond a 5
n[3] corespond a 7
n[4] corespond a 11
n[5] corespond a 13
n[6] corespond a 17
[...]
n[i] corespond a ne i ème nombre premier
etc
car on ne saura pas a quoi corespond cette variable si elle est codée sur 1 seul bit... on devra la coder sur 32 bits et donc, on perdra évidement un peu de place... car même si on récupère tout les premieres de 32 bits, je ne penses pas que l'on gagne vraiment en mémoire, et je ne penses pas que l'on gagne en temps...
28 juil. 2004 à 16:33
Ben si ca marche puisque je l'ai fait.
Nan je fais pas un big nombre, je fais un char[xxx]
Ensuite, le x-ieme bit de cette grande chaine est celui qui code la primalité de 2*x+3. Ce x-ième bit ce trouve dans le (x/8)-eme octet en (x%8)-eme position
Donc le 6-ieme bit de n[1] est le 1*8+6 bit de la chaine soit le nombre 27. Voila, pas plus dur que ca.
Pour les nombres parfaits je pensais à une autre solution. Je n'avais pas eu la même idée que toi (je suis une andouille) et c'est une très bonne idée.
De toute façon il n'en existe que 5 que l'on puisse coder sur un unsigned long int (32 bits).
27 juil. 2004 à 22:03
en effet, tu sais comment a quoi corespond le sixième bit de n[1] ?
en effet on ne saura pas quel bit de quel tableau corepond a quoi... donc pertr de mémoire énorme...
sinon, tu m'avais dis que tu ne savais pas comment je pourrais mettre ça pour les nombres parfaits... j'ai fait la source, j'ai plus l'adresse, mais elle est pas loin, recherche dans les dèrnières postés...
Ta solution est la meilleur, si tu veux optimiser mémoire, ta solution fonctionne facilement mais en déclarant
bignombre b[1]
car sur les unsigned int long, ça n'a aucun interet, je penses même que tu perdrais de la mémoire...
27 juil. 2004 à 18:31
J'en ai posé deux:
le premier un octet par valeur c'est un programme qui génère de l'HTML
Le second est bien plus performant et ne génère pas d'HTML. Il se trouve ici:
http://www.cppfrance.com/code.aspx?ID=18755
Sinon on peux l'optimiser plus même sur la mémoire (faire un tableau 3 5 7 9 11 13 ... au lieu de 1 2 3 4 5...)
Il faut normalement 1 octet pour 16 nombres.
27 juil. 2004 à 16:18
27 juil. 2004 à 15:55
Ensuite tu peux directement faire les opératoins sur les bits:
pour mettre un i-ème bit à 0 faire (le bit 1 est le premier à gauche):
unsigned char mask =1;
octet &= ~(mask << (8-i))
& et bit à bit, ~ opposition des bits, << décalage à gauche
Il existe un truc similaire pour mettre à 1
Une variable à un bit ca n'existe pas non plus en C++ (un bool ca fait un octet (quel gaspillage !!))
> Ce style de source a déja été posté, mais jamais en
> autant optimisé
Si le mien est plus optimisé
j'ai fais des comparaisons avec mon prog sur la même base de calcul (ftime pour le calcul du temps aec les millisecondes et les nombres premiers jusqu'à 40 million):
toi: 15.484 s
moi: 2.438 s
Pas pour me vanter juste pour dire que tu peux encore et encore optimiser.
Je pense d'ailleurs que le mien n'est pas complètement optimisé.
Je pense qu'on peux encore aller plus vite et je connais un méthode qui permette d'utiliser moins de memoire encore, mais ca devient du hard-programming et c'est very trop chaud pour mon niveau.
26 juil. 2004 à 12:02
Mais, même si les variables 1 bits n'existent pas en C (ce qui est discutable, puisqu'un bitfield pourrait s'y apparenter), tu pourrais toujours manipuler les bits d'un octet en utilisant un masque et la tu utiliserais vraiment 8 fois moins de mémoire.
Bonne continuation
26 juil. 2004 à 11:48
sinon, je pourais faire une classe, mais en c++ pas en C
En C les variables 1 bits n'existent pas, ici elles sont simulés dans le tableau nommé bits...
j'ai dis variables 1 bit car je prends le tableau n[] de 8 bits par cases pour transformer chaque élément en un tableau bits[] de 8 cases donc d'un bit...
26 juil. 2004 à 11:41
Mais passons, quelques petits commentaires sur ton code, tu gagnerais à utiliser des #define pour que ton code soit un peu plus clair, et qu'en cas de modifications de tes bornes de tableaux tu passes pas ton temps à fouiller ton code.
#define TAB_SIZE 5000000
....
char unsigned n[TAB_SIZE];
Sinon ta gestion des BITs me parait un peu suspecte, j'ai survolé ton code et tout ce que je vois c'est une manipulation d'un tableau de 8 caractères (8 octets = 64 bits).
Plutot que de recopier le code :
if (bit[7]>127){ bit[0]=1;bit[7]-=128;}else{ bit[0]=0;}
...
if (bit[7]>1){ bit[6]=1;bit[7]-=2;}else{ bit[6]=0;}
la création d'une fonction serait peut être apropriée, tu gagnerais encore en lisibilité de ton code.
Prends ces commentaires de manière constructive et ne te laisses surtout pas décourager. C'est déjà très bien de participer au développement de ce fabuleux site.
P.S : je suis passé voir ton site web, je crois qu'une petite relecture ne serait pas inutile.