4**25 c'est faisable sur PC ?
flex_fan
-
Char Snipeur Messages postés 10112 Date d'inscription Statut Contributeur Dernière intervention -
Char Snipeur Messages postés 10112 Date d'inscription Statut Contributeur Dernière intervention -
Bonjour,
je suis confronté avec un problème de de type: il faut mettre en place dans une application un compteur en base 4 avec 25 rangs, donc le nombre total d'états de ce compteur sera de 4**25. ce qui fait approx.282E+12 états.
Sur un PC, même haut de gamme, est il envisagéable de calculer les 282 TeraPossibilités, ou il faut 282 ans pour faire ça ?
Merci en avance pour tout eclaircissement ou pour toute suggestion de consultation des sites traitant le sujet
flex_fan
je suis confronté avec un problème de de type: il faut mettre en place dans une application un compteur en base 4 avec 25 rangs, donc le nombre total d'états de ce compteur sera de 4**25. ce qui fait approx.282E+12 états.
Sur un PC, même haut de gamme, est il envisagéable de calculer les 282 TeraPossibilités, ou il faut 282 ans pour faire ça ?
Merci en avance pour tout eclaircissement ou pour toute suggestion de consultation des sites traitant le sujet
flex_fan
A voir également:
- 4**25 c'est faisable sur PC ?
- Mon pc est lent - Guide
- Télécharger musique gratuitement sur pc - Télécharger - Conversion & Extraction
- Reinitialiser pc - Guide
- Downloader for pc - Télécharger - Téléchargement & Transfert
- Lire epub sur pc - Guide
13 réponses
Et en brainf*ck :
+[+]
sans test d'arrêt, bien sûr, je ne maîtrise pas assez ; )
merci à flex_fan qui a fourni un joli sujet à délire.
+[+]
sans test d'arrêt, bien sûr, je ne maîtrise pas assez ; )
merci à flex_fan qui a fourni un joli sujet à délire.
Bonjour
Je crois que tu t'es trompé dans ton calcul, tu as calculé 4**24, mais on n'est plus à ça près...
Pour la faisabilité, tout dépend de ce que tu fais dans chaque boucle. Fais tourner pendant 10 minutes, puis fais la division...
Je crois que tu t'es trompé dans ton calcul, tu as calculé 4**24, mais on n'est plus à ça près...
Pour la faisabilité, tout dépend de ce que tu fais dans chaque boucle. Fais tourner pendant 10 minutes, puis fais la division...
Salut !
Je trouve pas pareil, ou j'ai rien compris ou je suis nul en math ! lol Mais...
Béh si je comprends bien il y a 4 états possibles par digit et il a 25 digits ...
Béh théoriquement ça fait 4^25 possibilités ! Soit 1.12 x 10^15 !
Calculer les 282 TeraPossibilités !!???
Tu veux dire les énumérer !?
Si c'est le cas, je vois 2 limites :
- Le temps.
- La limite de stockage (en RAM ou mémoire de masse).
Pour le temps c'est facile comme l'a dit 'le père', suffit de créer l'algo et d'en générer un bon milliers, voir millions de possibilité pour estimer combien qu'il met de temps pour trouver une possibilité... Apres il suffit d'utiliser cette estimation en le comparant au nombre de possibilités à trouver....
Pour l'espace, 4 états différents peuvent être stockée sur 2 bits logiquement, donc 2 x 25 = 50 bits permet de stocker un état complet du compteur.
Reste plus qu'a faire 50 bits x 1.12 x 10^15 pour trouver quelle taille de stockage avons nous besoin...
50 x 1.12 x 10^15 bits ou 50 / 8 x 1.12 x 10^15 octets soit environ 7 x 10^15 octets... Ça donne environ 7000 TeraOctets (en utilisant la base de 1000 octets pour faire un Ko, et non pas 1024 comme cela devrait etre le cas !)....
Bref pour moi pas possible, car il faudrait 4 disque dur de 2To chacun.... ce qui évidement ne se trouve pas au carrouf du coin !.... Repose ta question l'année prochaine, je te répondrait certainement oui !
Étant donné que je suis peu sur d'avoir compris la question, je suis certainement hors concours...
Mais bon l'essentiel... c'est de vouloir aider ! N'est-ce pas !
Amicalement,
S@M...
http://kryoportail.ath.cx
Je trouve pas pareil, ou j'ai rien compris ou je suis nul en math ! lol Mais...
Béh si je comprends bien il y a 4 états possibles par digit et il a 25 digits ...
Béh théoriquement ça fait 4^25 possibilités ! Soit 1.12 x 10^15 !
Calculer les 282 TeraPossibilités !!???
Tu veux dire les énumérer !?
Si c'est le cas, je vois 2 limites :
- Le temps.
- La limite de stockage (en RAM ou mémoire de masse).
Pour le temps c'est facile comme l'a dit 'le père', suffit de créer l'algo et d'en générer un bon milliers, voir millions de possibilité pour estimer combien qu'il met de temps pour trouver une possibilité... Apres il suffit d'utiliser cette estimation en le comparant au nombre de possibilités à trouver....
Pour l'espace, 4 états différents peuvent être stockée sur 2 bits logiquement, donc 2 x 25 = 50 bits permet de stocker un état complet du compteur.
Reste plus qu'a faire 50 bits x 1.12 x 10^15 pour trouver quelle taille de stockage avons nous besoin...
50 x 1.12 x 10^15 bits ou 50 / 8 x 1.12 x 10^15 octets soit environ 7 x 10^15 octets... Ça donne environ 7000 TeraOctets (en utilisant la base de 1000 octets pour faire un Ko, et non pas 1024 comme cela devrait etre le cas !)....
Bref pour moi pas possible, car il faudrait 4 disque dur de 2To chacun.... ce qui évidement ne se trouve pas au carrouf du coin !.... Repose ta question l'année prochaine, je te répondrait certainement oui !
Étant donné que je suis peu sur d'avoir compris la question, je suis certainement hors concours...
Mais bon l'essentiel... c'est de vouloir aider ! N'est-ce pas !
Amicalement,
S@M...
http://kryoportail.ath.cx
Les calculer et non les stocker, je pense que c'est faisable.
Mais je ne comprends pas ce que tu veux dire par calculer. Il suffit d'incrémenté un entier de 1 à environ 10^15...
Si tu fait une centaine d'itération par seconde (ce qui me paraît peu pour un PC moderne) il te faut 10^13 s ! soit 317 millénaires. Bon courage.
Mais je ne comprends pas ce que tu veux dire par calculer. Il suffit d'incrémenté un entier de 1 à environ 10^15...
Si tu fait une centaine d'itération par seconde (ce qui me paraît peu pour un PC moderne) il te faut 10^13 s ! soit 317 millénaires. Bon courage.
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Salut,
en fait, j'ai pas tout compris l'intérêt de ce compteur...
S'il est à incrémenter par une action manuelle ou automatique, pas de souci, une variable de type entier long suffira.
Par contre, je ne vois pas pourquoi on devrait compter et énumérer les valeurs possibles.
en fait, j'ai pas tout compris l'intérêt de ce compteur...
S'il est à incrémenter par une action manuelle ou automatique, pas de souci, une variable de type entier long suffira.
Par contre, je ne vois pas pourquoi on devrait compter et énumérer les valeurs possibles.
Re !
En réaction à 'Char Snipeur'
Vi le problème exposé est difficilement compréhensible...
Par contre, je dirais qu'un ordi classique est capable de faire des millions de boucles par secondes (en assembleur par exemple)....
1.12 x 10^15 / 10^6 = 1.12 x 10^9 secondes ! Il y a 3.15 x 10^7 dans une année donc:
1.12 x 10^9 secondes / 3.15 x 10^7 s/an = 35 ans...
Si on optimise le code, on peut aussi paralléliser l'exécution en utilisant plusieurs cœurs... Chaque thread commençant à énumérer les possibilités à des endroits judicieusement choisi sur l'ensemble des possibilités...
En prenant un QuadCore on pourrait faire baisser encore le temps d'exécution mais pas par 4 ! La parallélisation nécessite aussi un traitement machine...
Disons que la durée du traitement est divisé par 3 !
ca fait plus que 11 / 12 ans !
Tout dépend de ce qu'il y a dans la boucle !
Amicalement,
S@M...
En réaction à 'Char Snipeur'
Vi le problème exposé est difficilement compréhensible...
Par contre, je dirais qu'un ordi classique est capable de faire des millions de boucles par secondes (en assembleur par exemple)....
1.12 x 10^15 / 10^6 = 1.12 x 10^9 secondes ! Il y a 3.15 x 10^7 dans une année donc:
1.12 x 10^9 secondes / 3.15 x 10^7 s/an = 35 ans...
Si on optimise le code, on peut aussi paralléliser l'exécution en utilisant plusieurs cœurs... Chaque thread commençant à énumérer les possibilités à des endroits judicieusement choisi sur l'ensemble des possibilités...
En prenant un QuadCore on pourrait faire baisser encore le temps d'exécution mais pas par 4 ! La parallélisation nécessite aussi un traitement machine...
Disons que la durée du traitement est divisé par 3 !
ca fait plus que 11 / 12 ans !
Tout dépend de ce qu'il y a dans la boucle !
Amicalement,
S@M...
En perl, un simple comptage jusqu'à 10^8 dure 48 sec (bi-proc power PC (Power 4) avec 4 Go de RAM sous AIX).
Je viens de lancer une boucle jusqu'à 10^9 pour voir si c'est linéaire ou exponentiel, résultat : 481 sec...
Donc un 10^12 devrait aller autour des 480000 sec, soit environ 133 heures, ou 5,5 jours.
Je viens de lancer une boucle jusqu'à 10^9 pour voir si c'est linéaire ou exponentiel, résultat : 481 sec...
Donc un 10^12 devrait aller autour des 480000 sec, soit environ 133 heures, ou 5,5 jours.
Re...
Blux... Tu fais plus que confirmer ce que je disais !... lol
10^8 / 48 s = 2 083 333 de possibilités /s.... soit très proche des 1 millions de possibilités que j'avais proposé...
Le perl est un langage de script de haut niveau.... il y a de fortes chances d'améliorer encore en faisant la même chose en assembleur...
Par contre, je reste persuadé qu'on a pas bien compris le problème à résoudre l... lol
Du moins pour ma part !
Amicalement,
S@M...
Blux... Tu fais plus que confirmer ce que je disais !... lol
10^8 / 48 s = 2 083 333 de possibilités /s.... soit très proche des 1 millions de possibilités que j'avais proposé...
Le perl est un langage de script de haut niveau.... il y a de fortes chances d'améliorer encore en faisant la même chose en assembleur...
Par contre, je reste persuadé qu'on a pas bien compris le problème à résoudre l... lol
Du moins pour ma part !
Amicalement,
S@M...
#include <stdio.h>
//---------------------------------------
int main(int argc, char *argv[])
{
unsigned long long cpt=0;
const unsigned long long sor=1L<<30;
printf("masque : %ld\n",sor);
while(cpt<1.0e15)
{
if(++cpt % sor) ;else printf("%ld\n",cpt);
}
return 0;
}
50 s pour 10^9 avec une brêle mono proc de pentium 4 2.8 GHz :P mieux vaut du C.
Chacun y va de son language! Je tente en php ou c'est pas la pein? ;)
De toute façon, tout le monde est d'accord (j'ose espérer), le seul langage qui pourrait éventuellement convenir, c'est l'assembleur.. On aura rien de bien concret avant d'avoir des chiffres en assembleur
On pourrait même essayer de déterminer une loi de croissance a partir de plusieurs valeurs..
J'adore ces questions à la con =)
...mais je code pas en assembleur.
De toute façon, tout le monde est d'accord (j'ose espérer), le seul langage qui pourrait éventuellement convenir, c'est l'assembleur.. On aura rien de bien concret avant d'avoir des chiffres en assembleur
On pourrait même essayer de déterminer une loi de croissance a partir de plusieurs valeurs..
J'adore ces questions à la con =)
...mais je code pas en assembleur.
Re !
J'ai un Q6600 et 4 Go de Ram à disposition vous voulez que j'essaye !!? lol !
Plus sérieusement j'étais sur : https://en.wikipedia.org/wiki/X86-64
64-bit integer capability: All general-purpose registers (GPRs) are expanded from 32 bits to 64 bits, and all arithmetic and logical operations, memory-to-register and register-to-memory operations, etc. can now operate directly on 64-bit integers. Pushes and pops on the stack are always in 8-byte strides, and pointers are 8 bytes wide.
Théoriquement un processeur 64bits peut incrémenter des nombres entiers de 64bits en un seul cycle donc suffisant pour nos 50 bits contenant une possibilité.
Pour le stockage : J'avais pas pensé, mais on est obligé de passer par la RAM pour stocker le résultat après incrémentation.... Et les temps d'accès seront beaucoup plus long que ceux nécessaire au processeur pour calculer une possibilité !
Sans compter que pour décharger la RAM pendant le calcul il faudra faire appel à un stockage de masse.... qui sera lui aussi encore plus long ! lol....
Pour faire le test, vous pouvez créer un gros tableau permettant de stocker le résultat de chaque itération...
A mon avis le temps par boucle va bondir !....
Bref, c'est carrément plus possible la ! Je suis décu ! lol
Amicalement,
S@M...
J'ai un Q6600 et 4 Go de Ram à disposition vous voulez que j'essaye !!? lol !
Plus sérieusement j'étais sur : https://en.wikipedia.org/wiki/X86-64
64-bit integer capability: All general-purpose registers (GPRs) are expanded from 32 bits to 64 bits, and all arithmetic and logical operations, memory-to-register and register-to-memory operations, etc. can now operate directly on 64-bit integers. Pushes and pops on the stack are always in 8-byte strides, and pointers are 8 bytes wide.
Théoriquement un processeur 64bits peut incrémenter des nombres entiers de 64bits en un seul cycle donc suffisant pour nos 50 bits contenant une possibilité.
Pour le stockage : J'avais pas pensé, mais on est obligé de passer par la RAM pour stocker le résultat après incrémentation.... Et les temps d'accès seront beaucoup plus long que ceux nécessaire au processeur pour calculer une possibilité !
Sans compter que pour décharger la RAM pendant le calcul il faudra faire appel à un stockage de masse.... qui sera lui aussi encore plus long ! lol....
Pour faire le test, vous pouvez créer un gros tableau permettant de stocker le résultat de chaque itération...
A mon avis le temps par boucle va bondir !....
Bref, c'est carrément plus possible la ! Je suis décu ! lol
Amicalement,
S@M...
Sans compter que pour décharger la RAM pendant le calcul il faudra faire appel à un stockage de masse.... qui sera lui aussi encore plus long
Non, si on fait un simple comptage, alors tout tient en RAM, puisque ce n'est qu'une itération, il y a même fort à parier que l'on ne va même pas quitter la cache du proc (L2 ou L3 selon les archi).
Non, si on fait un simple comptage, alors tout tient en RAM, puisque ce n'est qu'une itération, il y a même fort à parier que l'on ne va même pas quitter la cache du proc (L2 ou L3 selon les archi).
Re !
Pour moi il dit calculer, donc à quoi bon faire un calcul si on ne le stocke pas (pour usage ultérieur par exemple) !?
Si on ne cherche pas à stocker les résultats des incrémentations tu as certainement raison, code de la boucle reste sur le processeur et donc pas d'accès nécessaire à la rame...
Par contre si il faut stocker le résultat des itérations (pour une raison que l'on ignore !)... On passera obligatoirement par la RAM...
Toutefois Erratum : le débit d'un disque dur actuelle est de l'ordre de 80 Mo/s soit 640Mbits/s...
Or si on génére comme on l'a supposé 1 000 000 d'itérations / s et que chacune fait 50 bits ca donne un débit moyen de 50 Mbits /s.... alors disons 10Mo/s pour 2 000 000 itérations / s.... La RAM et un DD normal suivent...
Amicalement,
S@M...
Sur un PC, même haut de gamme, est il envisagéable de calculer les 282 TeraPossibilités, ou il faut 282 ans pour faire ça ?
Pour moi il dit calculer, donc à quoi bon faire un calcul si on ne le stocke pas (pour usage ultérieur par exemple) !?
Si on ne cherche pas à stocker les résultats des incrémentations tu as certainement raison, code de la boucle reste sur le processeur et donc pas d'accès nécessaire à la rame...
Par contre si il faut stocker le résultat des itérations (pour une raison que l'on ignore !)... On passera obligatoirement par la RAM...
Toutefois Erratum : le débit d'un disque dur actuelle est de l'ordre de 80 Mo/s soit 640Mbits/s...
Or si on génére comme on l'a supposé 1 000 000 d'itérations / s et que chacune fait 50 bits ca donne un débit moyen de 50 Mbits /s.... alors disons 10Mo/s pour 2 000 000 itérations / s.... La RAM et un DD normal suivent...
Amicalement,
S@M...
Toutefois Erratum : le débit d'un disque dur actuelle est de l'ordre de 80 Mo/s soit 640Mbits/s...
Or si on génére comme on l'a supposé 1 000 000 d'itérations / s et que chacune fait 50 bits ca donne un débit moyen de 50 Mbits /s.... alors disons 10Mo/s pour 2 000 000 itérations / s.... La RAM et un DD normal suivent...
Bof... les 80 Mo/sec ne sont que sur des secteurs (qui sont la plus petite entité accessible). Donc pour écrire un seul bit, on sera obligé d'écrire un bloc ('cluster' sous windows) de 2, 4 ou 8Ko (voire plus) représentant plusieurs secteurs physiques (certainements non contigus, en fonction du facteur d'entrelacement défini au formatage), donc ça va forcément coincer...
Or si on génére comme on l'a supposé 1 000 000 d'itérations / s et que chacune fait 50 bits ca donne un débit moyen de 50 Mbits /s.... alors disons 10Mo/s pour 2 000 000 itérations / s.... La RAM et un DD normal suivent...
Bof... les 80 Mo/sec ne sont que sur des secteurs (qui sont la plus petite entité accessible). Donc pour écrire un seul bit, on sera obligé d'écrire un bloc ('cluster' sous windows) de 2, 4 ou 8Ko (voire plus) représentant plusieurs secteurs physiques (certainements non contigus, en fonction du facteur d'entrelacement défini au formatage), donc ça va forcément coincer...
Re !
Alors puisqu'on est dans le délire... lol
Il faudrait prévoir un système de reprise à chaud (je propose un RAID 5) car un disque dur même pro, n'est pas fait pour durer éternellement .... encore moins lorsqu'il est continuellement en train d'écrire pendant des années ! lol
De même, l'algo devrait aussi proposer une reprise sur panne ! (sinon une simple panne d'alim, ou une micro-coupure nécessiterait de recommencer le calcul ! lol
Amicalement,
S@M...
Alors puisqu'on est dans le délire... lol
Il faudrait prévoir un système de reprise à chaud (je propose un RAID 5) car un disque dur même pro, n'est pas fait pour durer éternellement .... encore moins lorsqu'il est continuellement en train d'écrire pendant des années ! lol
De même, l'algo devrait aussi proposer une reprise sur panne ! (sinon une simple panne d'alim, ou une micro-coupure nécessiterait de recommencer le calcul ! lol
Amicalement,
S@M...
Il faudrait prévoir un système de reprise à chaud (je propose un RAID 5) car un disque dur même pro, n'est pas fait pour durer éternellement ...
J'en ai certains qui bossent 24/24h avec 24h de coupure annuelle planifiée.
De plus, la reprise des traitements n'est possible que si l'on a une image mémoire stable de l'exécution du processus, il faut donc prévoir à intervalles réguliers des checkpoint de process et des checkpoints de données disque (avec journalisation obligatoire) -> encore du temps de perdu.
Mais on s'éloigne du but : compter jusqu'à beaucoup...
J'en ai certains qui bossent 24/24h avec 24h de coupure annuelle planifiée.
De plus, la reprise des traitements n'est possible que si l'on a une image mémoire stable de l'exécution du processus, il faut donc prévoir à intervalles réguliers des checkpoint de process et des checkpoints de données disque (avec journalisation obligatoire) -> encore du temps de perdu.
Mais on s'éloigne du but : compter jusqu'à beaucoup...
Je pense que le problème était plutôt de chercher une valeur particulière inconnue codée entre 0 et 4^25-1 (qui vous en conviendrez, est identique à chercher un nombre entre 0 et 2^50-1)
En mémoire ça prendra donc 50 bits ce que toute RAM doit pouvoir faire ;)
Et il y aurait alors une incrémentation, un test d'égalité, et on recommence si faux...
En Caml, il m'a fallu environ 10 secondes (sur une machine tout ce qu'il y a de plus classique) pour exécuter ce code :
En mémoire ça prendra donc 50 bits ce que toute RAM doit pouvoir faire ;)
Et il y aurait alors une incrémentation, un test d'égalité, et on recommence si faux...
En Caml, il m'a fallu environ 10 secondes (sur une machine tout ce qu'il y a de plus classique) pour exécuter ce code :
let rec boucle i x = if i=x then x else boucle (i+1) x;; sys__time ();; boucle 0 33554432;; (* 2^25 *) sys__time ();;Donc pour aller jusqu'à 2^50, je dirai qu'il faudrait 2^25*10 secondes (au pire cas
Je pense que le problème était plutôt de chercher une valeur particulière inconnue codée entre 0 et 4^25-1 (qui vous en conviendrez, est identique à chercher un nombre entre 0 et 2^50-1)
Ben dans ce cas, c'est soit un index de tableau 'standard' et l'accès est direct (ou via un hash quelconque), soit un truc à la con, trié (->algo de dichotomie), soit un truc à la con pas trié, et dans ce cas, c'est parti pour l'aventure...
Ben dans ce cas, c'est soit un index de tableau 'standard' et l'accès est direct (ou via un hash quelconque), soit un truc à la con, trié (->algo de dichotomie), soit un truc à la con pas trié, et dans ce cas, c'est parti pour l'aventure...
Et le code en Malboge, ça donnerai quoi ???