Questions et remarques d'ordre gnral sur le second problme

Questions et remarques d'ordre gnral sur le second problme

En prvision du second sujet, j'ouvre ce topic histoire que l'on rassemble ici nos diverses remarques et claircissements sur l'nonc...

48 posts / 0 nouveau(x)
Dernière contribution
Reportez-vous à notre Notice d'optimisation pour plus d'informations sur les choix et l'optimisation des performances dans les produits logiciels Intel.

Merci Vincent pour l'ouverture de ce topic, je pense que rassembler les questions dans un topic est une bonne chose pour la visibilit.

Pour information nous sommes en train de mettre jour le problme pour qu'il soit le plus adapt possible.
Nos ingnieurs tant actuellement en train de travailler dessus, nous aurons donc quelques heures de retard.
Le problme sera en ligne avant la fin de l'aprs midi.

Cordialement,

Anthony, Intel Software Network.

Voil, le 2ime problme est live :

http://software.intel.com/fr-fr/contests/Acceler8-developpement-parallel...

Amusez vous bien ! :)

Merci beaucoup :)
Ca a l'air encore plus mathmatique que le prcdent.

Avons nous le droit d'entrer la liste de tous les nombres premiers dans le code (ou les faire gnrer par le compilateur) ou faut il les calculer l'excution (ca me parait la rponse la plus plausible) ?

Bonne chance tous
Fabien

Oula ! C'est puissamment tordu !

Premire question pour tre sr d'avoir tout compris :

La quatrime valeur c'est bien le maximum de diffrence autoris entre le produit et la somme de chaque paire ?

Si les 3 premiers input sont constants, alors par exemple un quatrime input gal 2 ressortira galement les rsultats associs un quatrime input gal 1 et gal 0 ?

De plus pour un quatrime input tendant vers l'infini, on devrait ressortir l'intgralit des nombres premiers ?

chaque paire

On ne parle pas de paire ... mais de clique de "K lments" ... K est le 3e argument.

"Si les 3 premiers input sont constants"

Je ne suis pas sr qu'on puisse donner autre chose que des constantes.

Si les 3 premiers input sont constants, alors par exemple un quatrime input gal 2 ressortira galement les rsultats associs un quatrime input gal 1 et gal 0 ?

Ohlalaaaaaa ... rien voir.ARG 1: Borne infrieure de l'espace de rechercheARG 2: Borne suprieure ... les deux brones appartiennent l'espace de rechercheARG 3: Quantit d'lments qui font la clique des nombres premiers conscutifsARG 4: la diffrence maximale autoris pour la relation "CLOSE" (proche en Franais)On dit que deux cliques, C1, C2, de K nombres premiers conscutifs sont "proches" si:|PRODUIT(C1) - SOMME(C2)| <= ARG4ou|SOMME(C1)-PRODUIT(C2)|<= ARG4PRODUIT(Clique) = produit des lments de la clique.SOMME(Clique) = somme des lments de la clique.Il n'est pas dit que les nombres premiers sont calculer ... mais je pense que cela sera le fond du problme, car sinon, il devient trop simpliste.

Bah si justement, si tu gardes les mme ARG1,2 et 3 et que tu fais 2 computations pour ARG4_1 et ARG4_2 avec ARG4_1

Absolument, car si une entit est borne par un N elle le sera pour M >=N.Sinon, mon problme tait la nature des rsultats ... on parle bien d'une liste "d'un ensemble de nombre premiers" et pas une liste de nombres premiers.

Etant donn l'exemple d'output, je dirai que c'est bien une liste de "k-squences" de nombres premiers qu'on attend.

Moi j'ai une question qui mon avis est importante : est-ce que l'on fait commencer k 1 ou a 2 ?

A mon avis, l'usage rgulier est partir de k=2. Mme si le cask=1, n'est pas totalement exclu.
Autre question importante ... Quelle est la borne max de l'intervale de recherche?

Quoting farcellier
Merci beaucoup :)
Ca a l'air encore plus mathmatique que le prcdent.

Avons nous le droit d'entrer la liste de tous les nombres premiers dans le code (ou les faire gnrer par le compilateur) ou faut il les calculer l'excution (ca me parait la rponse la plus plausible) ?

Bonne chance tous
Fabien

Je pense que mme si ils sont OK pour que l'on charge tous les nombres en mmoire ce n'est pas viable, les nombre premiers sont beaucoup moins rare que les smallbrain numbers du premier exo... fais une recherche rapide sur le net, les 50000 premiers nombre premiers s'arrte vers ~10^5 (je te laisse imaginer la taille du tableau gnrer et la taille du binaire qui s'en suit).

Hello everyone!

I hate to spoil the fun and I hope I'm mistaken but I think the example is wrong.
If you look at the third line of the output, which reads:
[5 7] 35 [15 17] 36
we have 5*7 = 35. That is correct. However, 15+17 = 32 which is not only different from 36 but also too far away from 35, thus not respecting the condition that |sum-prod| <= argv[4]
Can someone please confirm whether I'm mistaken or the example is wrong?

Regards.

Oui, le volume de donnes pour stocker tous les nombres premiers serait exagr.

Aucune consigne n'est donne concernant la recherche des nombres premiers en eux mmes. Pour le moment, nous avons considr comme tout le monde je pense que la recherche des nombres fait partie du challenge.

J'aurai du poser la question de manire plus gnrale. Avons nous le droit d'embarquer des informations pr-calcules dans notre binaire ?

=====================================Hello everyone!

I hate to spoil the fun and I hope I'm mistaken but I think the example is wrong.
If you look at the third line of the output, which reads:
[5 7] 35 [15 17] 36
we have 5*7 = 35. That is correct. However, 15+17 = 32 which is not only different from 36 but also too far away from 35, thus not respecting the condition that |sum-prod| <= argv[4]
Can someone please confirm whether I'm mistaken or the example is wrong?

Regards.=====================================hahahaaaa ... what an eagle eyes ... bravo!This output line seems to be incorrect ... pretty strange for an illustrative example. Another copy/paste big fail!

The same example works with 17 & 19 => 17+19 = 36. Just a small mistake.

Bonjour tous,

Dsol pour le retard, je n'tais pas au bureau.
Je transmets vos questions ds maintenant notre spcialiste, je vous tiendrais au courant ds que j'en saurais plus.
merci encore pour ces retours.

Anthony, Intel Software Network.

On peut borner les nombres premiers calculer dans la somme comme suit :

int min;  //premier argument
int max;  //deuxime argument
int num;  //nombre d'lments dans les p-uplets
int diff; //maximum de la diffrence

int max_prime = (pow(max, num) + diff) / num;
//max_prime majore les nombres premiers "utiles" 

Pour tous,

voici la premire rponse que je peux vous apporter.
Comme certains me l'ont demand : K=2 minimum. ( je vais l'ajouter sur la home du concours )

On se penche sur le reste des questions en ce moment mme.

Anthony, Intel Software Network.

  1. intmax_prime=(pow(max,num)+diff)/num;

Je ne vois pas pourquoi "max_prime" est utile comme major avec l'existence d'un major trivial et beaucoup plus petit que lui "max" ... ou alors, quelque chose m'chappe?!!

Pas pour les nombres premiers membres de l'addition.
Dans l'exemple on a :./cprimes 2 50 2 1
et en sortie :[41 43] 1763 [881 883] 1764
Or, 881 est plus grand que 50! (mais plus petit que (50^2 + 1) / 2) Dsol, je pensais que c'tait a ta question dans le post #9.

Avec toute la panoplie des mthodes que j'avais trouv sur le net ... je ne suis pas certain de vouloir aller jusqu' cette borne par une sieve.Cela exigera des synchros dans tous les sens.Sinon, ma question tait par rapport du type supporter (pour valuer la quantit mmoire qui sera utilise en fonction de mes choix). J'ai en ma rponse dans ton code! MerciCela va tre chaud,

D'aprs ce que j'ai pu lire dans le sujet, il est indiqu que : "The product of any k-consecutive primes within the range can be represented by a 64-bit integer.". Donc a laisse penser qu'on doit travailler avec des entiers sur 64 bits, comme pour le problme prcdent.

Je n'ai pas trop compris quoi correspond la borne suprieure, dans l'example elle vaut 50 et la sortie de l'example contient plusieurs nombres premiers suprieurs 50. Est-ce que quelqu'un peut m'expliquer ?

Merci !

The idea of consecutive primes can be extended to any number k, in which there are only k primes between and including the smallest and largest primes of the ordered set.
The input to the program will be four positive integers on the application's command line. The first two integers are the lower and upper bounds (inclusive) of the range to search for consecutive prime sets that will be multiplied together.

C'est la borne superieure pour les nombres premiers de la premiere sequence (la ou on multiplie).
Cheers,
Mihai ;D

Le troisime paramtre (k) a pour valeur minimale 2, y a t'il aussi une valeure maximale (j'imagine que la rponse est non mais bon on peut toujours rver) ?

I would suggest reading the problem statement carefully one more time [wink] ;D

I couldn't agree more with @Mihai :-) .

Anthony.

Avec un peu de logique, tu verras que kmax n'est en aucun cas un problme. Ce qui me pose conceptuellement beaucoup plus de problme c'est en fait le dernier paramtre, ie la tolrance que l'on se donne. En effet, si on se donne une tolrance "non raisonnable" (genre 2^63-1) a devient du grand grand n'importe quoi : tu fais exploser le nombre de cas tester et le nombre de squences retourner puisqu'il faut en fait retourner toutes les squences de nombres premiers existantes entre 1 et 2^63-1 et cela pour chaque squence du ct produit : soit des milliards de milliards de milliards de squences afficher l'cran (d'o le "non raisonnable")....

Par exemple avec les paramtres d'entre 1 2^63-1 2 2^63-1 c'est du grand dlire (en fait limiter les 2 derniers paramtres des "entiers 8 ou 16" (char/unsigned char/short int/unsigned short int) aurait viter de faire exploser le nombre de squences retourner, surtout que conceptuellement a n'a pas normment d'intrt de se donner une tolrance "infinie")

Je dirais mme plus que le fait de pouvoir reprsent un entier sur 64 bits est "non raisonnable".

Je n'ose mme pas imaginer la quantit de nombre premier. Et surtout la mmoire ncessaire pour tous les stocker.

PS : Si vous pouviez viter de parler en anglais sans raison particulire.

Je n'ai pas de problme avec le fait d'avoir un k qui puisse tre potentiellement infini, a m'aurait juste t utile pour viter certaines allocations dynamique et faire des allocations sur la pile si k n'tait pas trop grand...

Autre question (juste pour tre sur).

Il ne faut pas trier les rsultats (l'exemple semble montrer que non... ) ?

C'est simplement que je maitrise beaucoup mieux l'anglais. J'avais peur d'ecrire avec des fautes, mais je constate que meme les Francais font des erreurs assez severes. C'est vrai que le concours est organise en France. Cependant, le simple fait que l'enonce du probleme est en anglais montre que les organisateurs ciblent un publique plus large.
Desole si j'ai influence les autres a me repondre en anglais.

Mihai

Si une personne parle anglais a ne me drange pas vraiment. Mais j'avais peur que tout le monde commence crire en anglais.

Pour les fautes d'orthographe ce forum propose un correcteur orthographique franais mais galre avec les accents donc a ne te sera pas trs utile.

Bonjour tous,

un petit post pour vous signaler la mise jour du problme ( aprs beaucoup de demandes )avec 2 arguments qui vous serviront peut srement. Les 2 modifications sont en gras sur le site.

voir ici : page du concours

Anthony.

Merci, je pense que a rsout pas mal de problmes.
On pourra tre sr que son programme fonctionne pour les diffrentes valeurs critiques.

Bonjour,

des retours concernant la mise jour de l'ennonc ? Vous trouvez a plus clair ?

Anthony, Intel Software Network.

Bonjour,

Oui, c'est mieux avec des limites !

Suite une question que nous avons pos par email concernant la possibilit d'obtenir les nombres premiers grace un algorithme probabiliste aussi fiable soit il, je met en copie la rponse :

Bonjour tous les deux,

Je
ne pense pas vous apporter une bonne nouvelle mais lalgorithme ne
devra pas tre probabiliste et rpondre chaque fois correctement.

Comme pour le premier problme, lingnieur en charge des notations va en effet vrifier le code la main .

Nhsitez pas poser vos questions directement sur le forum pour en faire profiter tout le mondeJ.

Cordialement,

L'algorithme de dtection des nombres premiers doit donc etre mathmatiquement prouv pour pouvoir etre employ.

Merci d'avoir partag la rponse , tout le monde pourra en profiter !

Merci outlook pour le "J"... ;-)

Merci d'avoir partag tbastiani, mme si j'avais de mon ct considr a comme acquis.

Note ceux qui utiliseraient la Maht Kernel Libraries/GMP : les algos de la MKL/GMP sont PROBABILISTES !
Eh oui...

Je trouve a bien plus intressant comme a ;-)

EDIT : Ca implique donc qu'on ne peut pas utiliser l'hypothse de Riemann gnralise ... moins de la dmontrer (a doit faire partie des problmes du millnaire je crois)

C'est aussi le retour que j'ai eu de la part de l'ingnieur qui a choisit le problme, cela complique un peu les choses, mais a le rend aussi plus intressant.
Le but du concours est toujours l'apprentissage, donc cela ne peut tre que bnfique pour les participants :)

Anthony, Intel Software Network.

PS : merci @tbastiani et ses 2 partenaires qui sont venus chercher leur lots ce midi autour d'un caf :)

Ca me parrait tres exagere d'imposer de telles contraintes qui, a mon avis, ne sont pas fondees.
Les tests de primalite probabilistes sont utilise a large echele meme dans des applications sensibles, ex la RSA.

Le NIST a meme publie une methodologie d'applications de ces algorithmes pour des nombres premier beaucoup plus grands que ce qu'on utilise dans ce probleme (2048 bits par exemple):
http://csrc.nist.gov/publications/fips/fips186-3/fips_186-3.pdf
Voir l'annexe C.3

Avec les donnees de
http://www.goes-r.gov/procurement/flight_documents/MIL-HDBK-217F.pdf
on peut calculer l'ordre de grandeur de la probabilite qu'un transisteur echoue.

En faisant l'hypothese que les transisteurs d'Intel sont les meilleurs sur la planete et qu'il sont avec plusieurs ordres de grandeur moins susceptibles a des defaillances que les transisteurs presentes dans le document anterieur, on peut toujours jouer sur les parametres/iterations des tests probabilistes pour arriver a une probabilite d'erreur aussi basse que l'on veut.

Oui c'est embtant il faut refaire l'algo (j'imagine que beaucoup d'entre nous avait opt pour un algo probabiliste puisqu'ils sont souvent plus rapide que les algo dterministe).

Cependant les rgles sont les rgles, quand tu travailles en entreprise tu te retrouves toujours avec des contraintes techniques ou technologiques que tu trouves inacceptable et pourtant tu dois faire avec... Si les ingnieurs disent on veut un algo dterministe alors on doit faire un algo dterministe, qui sait peut-tre que quelques matheux parmis nous auront une ide gniale et inventerons un algo meilleurs que ceux existant (le dernier, AKS prime testing, date de 2002... comme quoi il y a toujours des choses dcouvrir).

Le problme tant de nature mathmatique (et non de nature "pratique"), il ne me parait pas du tout exagr de demander un algorithme dterministe et non probabiliste dont la philosophie est diffrente, et ce mme si la probabilit qu'un algo probabiliste renvoie un nombre non premier est infinitsimale...

La philosophie est diffrente en effet, mais lorsque tu as plus de chance que tes calculs ratent cause d'une erreur au niveau des transistors qu' cause d'une erreur au niveau de ton algorithme, il me semble que le calcul peut tre considr comme exact :)

En effet ce que veux dire Mihai est qu'avec un algorithme probabiliste, si tu choisit bien tes paramtre, tu peux obtenir un pourcentage d'erreur infrieur au pourcentage d'erreur du hardware, ce qui semble suffisant, non ?

J'ai quelques soucis l'utilisation de la MTL, je suis les instructions pour avoir disposition TBB pour compiler mon programme, tout fonctionne parfaitement et je peux le lancer via la ligne de commande.

Cependant lorsque j'essaye de crer une tche pour lancer mon programme de faon indpendante il y a une erreur l'execution m'indiquant que la lib TBB n'a pas pu tre trouve.

Est-ce qu'il y a un moyen d'y remdier (j'aurais bien aim faire quelques tests, sinon tan pis je me firai mon programme).

Essaye d'indiquer a ld.so ou il faut chercher les bibliotheques, genre:
export LD_LIBRARY_PATH=/path/to/lib
Met ceci dans le script qui lance la tache, avant d'executer ton programme.

Mihai

Laisser un commentaire

Veuillez ouvrir une session pour ajouter un commentaire. Pas encore membre ? Rejoignez-nous dès aujourd’hui