|
Alpha & Oméga
|
Histoire de réveiller les instincts de compétition des scripteurs du forum je vous propose un petit concours avec un grand classique du genre, performance de calcul de nombres premiers.
Prix: 2500l$ (peut etre plus si certains veulent ajouter au pot) Objectif: Calculer les 10000 premiers nombre premier avec la meilleur performance de temps Contraintes: - Un seul événement, tout se passe dans le state entry (on peut faire des fonctions) - On affiche le temps d'exécution du script à la fin du traitement - Les nombres ne seront pas intégralement stocké en dur dans le script, toutes fois on peut en mettre quelques uns pour amorcer la pompe - Utilisation de un seul et unique script, pas de parallélisme Vous avez 15 jours soit le 21/09 comme date butoir pour m'envoyer vos script en MP et pour le fun postez ici votre temps d'exécution |
06/09/2010, 15h43
|
[concours] qui sera premier ?
| Suivre |
|
|
Partager | Rechercher |
|
Bagnard
|
-
|
|
06/09/2010, 18h54
|
|
Alpha & Oméga
|
Je crois que le ton est donné
|
|
06/09/2010, 19h32
|
|
Empereur
|
hooo, ca me tente bien ce petit concours ^^
au fait, histoire de mettre tout le monde d'accord : 1 n'est pas premier. de plus, même si on peut "amorcer la pompe" avec quelques nombres premiers, il faudrait limiter à 2 ou 3, sinon on simplifie énormément la duree en stockant en dur les nombres premiers jusqu'a racine(1000), soit jusqu'à 31. 1000 devrait être un paramètre modifiable, histoire de se concentrer sur l'algo et l'optimisation... C'est juste une remarque, Magic verra bien les algos qui trichent ou pas. A vue de nez, les temps d'exécution de Mingyar m'ont l'air excellents. |
|
06/09/2010, 20h02
|
|
Alpha & Oméga
|
@Mingyar
Puis je avoir un TP sur la sim vide pour comparer mes perfs? J'en ai pas a dispo 
|
|
06/09/2010, 20h30
|
|
Alpha & Oméga
|
Pour le moment sur une sandbox pas vide avec des scripts autour et des builds :
Citation :
Citation :
|
|
06/09/2010, 20h37
|
|
Alpha & Oméga
|
barbidule, pas de soucis, je pense que la plus part des personnes ici ont très bien comprit ma limitation à quelques uns.
Parcontre si je peux te reprendre sur ton raisonnement... c'est pas les nombres premier jusqu'a mille, mais les mille premier nombres premier. Ce qui implique d'en stocké 89 et non pas 31. Mais 31 comme 89 et on est largement au dessus des quelques uns  Sinon good news, une bonne fée a rajouté 1000L$. Merci à elle 
|
|
06/09/2010, 20h50
|
|
Alpha & Oméga
|
 Compte tenu des performances déjà vu, je vais remonter la barre au calcul des 10000 premier nombres premier |
|
06/09/2010, 20h55
|
|
Roi / Reine
|
Salut
Apprenti scripteur, je ne suis pas encore capable de faire cela ... Mais j'ai envie de voir jusqu'où vous êtes capable de faire ^^ et bang 500l$ en plus eu faut faire un script pour calculer combien ça fait ? |
|
06/09/2010, 21h06
|
|
Alpha & Oméga
|
Merci à toi Ecarys et merci à Kira qui viennent de rajouter chacun 500L$
Soit un pot de 2500L$
|
|
06/09/2010, 21h11
|
|
Alpha & Oméga
|
Rajouter des valeurs ne fera que creuser l'écart car la complexité d'un algorithme suit une tendance approximative ... cela peut etre polynomial, logarithmique, exponentiel voir un mix de ces tendances .....
Allons pour 10 000 mais je ne pourrai faire mes tests que après demain. |
|
06/09/2010, 21h19
|
|
Empereur
|
Citation :
)tout a fait d'accord pour passer à 10000, ca compensera les problèmes de lags, pas se départager au 100ème de seconde, toussa... |
|
06/09/2010, 21h33
|
|
Alpha & Oméga
|
Citation :
|
|
06/09/2010, 21h37
|
|
Empereur
|
Citation :
de toute faççon, en montant à 10000 on verra facilement les algos se départager, et à algo identique, on regardera l'optimisation. Le lag ne devrait pas trop intervenir en fait |
|
06/09/2010, 21h45
|
|
Bagnard
|
-
|
|
06/09/2010, 22h05
|
|
Alpha & Oméga
|
Félicitation mingyar
Citation :
Citation :
|
|
06/09/2010, 22h21
|
|
Bagnard
|
-
|
|
06/09/2010, 22h28
|
|
Alpha & Oméga
|
J'ai hate de voir vos versions de code ... il y a tellement de manières de calculer ca ....
Au fait si le state_entry fait un llHTTPRequest vers un serveur relié aux supercalculateurs du CEA ca compte ???? |
|
06/09/2010, 23h11
|
|
Empereur
|
grmblblbl, je savais bien que j'arriverai à me ridiculiser d'une autre façon...
Avec l'algo basique (le crible, erasthotène ou un nom approchant je crois...) sans stockage ni affichage, tout 1er essai pour voir, j'arrive à 73 secondes  même si j'optimise, je doute que mon terrain laggy explique cette durée à lui tout seul. Je soupçonne un peu de RL la dedans, genre cours de crypto ou boulot, avec un algo pas classique, en fouillant un peu il y a pleins d'algos assez délirants (probabilistes, algo KAS très récent...). J'espère ne pas avoir à implémenter une de ces méthodes. D'autre part - judicieuse remarque du sus-surnommé le poilu ^^, la mémoire empêche de tout stocker. On peut alors optimiser (le crible standard du grec) en s'arretant de stocker les nombres premiers des qu'on dépasse la racine du 10000ème; mais cela suppose un peu de connaitre déjà la réponse à la question non? (c.a.d que l'on ne divise que par les nombres premiers < 324 et qu'on n'en stocke que 66 du coup, c'est un peu tricher non?) Même en faisant cela, je n'ose pas vous dire combien de temps ca met tellement j'ai honte! (50sec...) ca doit pas être le crible votre truc, je crains l'algo ébouriffant... edit : ouf! en allant ailleurs (moins laggy), je descend à 16 secondes, ca me rassure un peu ^^ apluka optimiser edit2 : l'horreur dans tout ça, c'est que chez moi c'est aussi laggy que le bac a sable de france3d (55 secondes la bas), mes voisins doivent m'adorer! (promis je ferai du ménage, j'ai envie de tout refaire, pas taper gentils voisins ^^...) Citation :
|
|
07/09/2010, 00h38
|
|
Bagnard
|
-
|
|
07/09/2010, 01h23
|
|
Empereur
|
ca me rassure, avec 16 secondes non optimisées je reste dans la course
Pour les puristes (ou plutôt extrémistes!), il y a une implémentation de l'algo AKS en c++ sur le net. Ca m'a l'air traduisible en lsl sans grosses modifs (on n'a pas besoin de bibliothèque de grand nombres entiers ici), mais piocher ce genre d'algo incompréhensible pour le commun des mortels ne doit pas être l'objet du concours. j'avais un lien pdf, pour ceux qui aiment la poésie des maths même si c'est incompréhensible, http://www.cse.iitk.ac.in/news/primality.pdf, pour la démonstration de l'algo AKS qui semble être le seul "prouvé", mais la page bloque... On pourra toujours regarder http://en.wikipedia.org/wiki/AKS_primality_test (il paraitrait qu'un algo ECPP serait plus rapide, cf http://www.lix.polytechnique.fr/Labo...rain/aks-f.pdf qui est très jolie avec tous ces symboles mathématiques partout mais bon, ces trucs là c'est pour les très grands nombres premiers, pas pour nos 10000 petits premiers)Il y a d'autres algos, mais qui ne sont pas complètement corrects, certains sont probabilistes, ils disent qu'un nombre a de très grande chance d'être premier (utilisés RL pour le cryptage, c'est flippant!), ou alors utilisent des conjectures mathématiques acceptées mais non démontrées encore. Bref, il est pas si mal finalement le "petit" crible d'Erastothène ^^ |
|
07/09/2010, 02h22
|
|
Alpha & Oméga
|
Citation :
Tu peux sans aucun soucis, mais j'attends de voir la ruse de sioux que tu va utiliser pour récupérer les donnée sans HTTP_response Citation :
|
|
07/09/2010, 09h16
|
|
Alpha & Oméga
|
Coucou les fous d'algo
Je me suis penché sur cette histoire ce matin. J'ai un peu fouillé le web pour piocher des idées (comme tout le monde je pense) et j'ai fait ma petite sauce. Il y a des algos sympas mais traduits en LSL c'est une catastrophe. J'ai aussi laissé tomber les trucs probabilistes, on veut du sûr . Finalement j'ai opté pour un truc simple mais efficace apparemment.Voici mes premiers résultats sur une sim tranquille : Citation :
 .Nota : avec mono au premier lancement le temps est un peu long, mais ensuite on gagne facilement 2s, le temps sans doute de compilation des routines. |
|
07/09/2010, 10h26
|
|
Empereur
|
Ca y est Bestmomo commence à exploser tout le monde avec des temps records!
Je te soupçonne de calculer tes nombres premiers avec des rotations
|
|
07/09/2010, 11h05
|
|
Alpha & Oméga
|
Citation :
J'ai continué mon optimisation, je gagne plus que des bricoles... Citation :
Citation :
|
|
07/09/2010, 12h40
|
| Suivre |
Connectés sur ce fil1 connecté (0 membre et 1 invité)
Afficher la liste détaillée des connectés
|