Curriculum and Labs for Engineering Education

cancel
Showing results for 
Search instead for 
Did you mean: 

Challenge mathématiques #4 : Multiplication de grands nombres

Bonjour à tous,

Voilà le 4ème sujet des challenges mathématiques. Cette fois on retourne jouer avec des chiffres.

Le sujet est relativement simple, il vous faudra lire un fichier texte qui contient 100 paires de nombres, vous devez alors multiplier chaque paire de nombre entre eux et calculer le résultat et placer les 100 résultats obtenus dans un fichier texte.

Le but est d’arriver à faire ces opérations le plus rapidement possible.

Cependant, il y a une contrainte, les nombres font 100 digits et le résultat de chaque multiplication fera donc 200 digits chacun.

Vous pouvez trouver un fichier texte d’exemple contenant les 200 nombres de départ. (fichier nombres.txt)

Les multiplications se font par paire, c'est-à-dire que chaque nombre n’est utilisé qu’une seule fois. La ligne 1 est multipliée par la ligne 2, puis ligne 3 avec 4, ligne 5 avec 6 etc.

Méthode d’évaluation :

Le code le plus rapide remportera se challenge. Le temps de lecture du fichier et d’écriture du fichier résultat ne sera pas pris en compte. Seul le temps de calcul des multiplications sera mesuré et permettra l’évaluation.

Les nombres utilisés le jour de l’évaluation sera différent de celui proposé ici mais possèdera les mêmes caractéristiques (nombre de lignes, longueurs des nombres).

Résultats attendus :

Les résultats doivent être placés dans un fichier texte nommé resultats_VotrePseudo.txt avec le résultat d’une multiplication par ligne. Le fichier doit être enregistré dans le dossier parent de votre dossier de base.

Envoyer son code :

La date limite de participation est fixée au 1 mai 2013.

Vous devez m’envoyer votre code directement par email (maxime.renaud@ni.com) sous forme de vi avec un vi principal facilement identifiable, le tout dans un dossier avec votre pseudonyme. Je n’accepte pas les exécutables, car je ne peux pas regarder le code si besoin et cela pose des problèmes avec certaines boîtes email avec les exécutables.

A noter :

Le vainqueur de ce concours gagnera une certification gratuite de son choix !

Les codes seront mis à disposition à la fin du challenge, alors pensez à moi et aux personnes qui regarderont votre code en mettant quelques commentaires.

Les tests seront faits sur mon PC avec une version française de LabVIEW 2012 (32 bits) à jour.

La configuration du PC est la suivante :

Dell Latitude E6410

8 Go de RAM

Windows 7 professionnel 64 bits en français et à jour

Processeur Intel Core i7 M640 @2,8 GHz (4 cœurs)

N’hésitez pas à poser des questions si tout n’est pas clair.

Bonnes chances à tous.

Edit du 03/06/2013 :

Bonjour à tous, ca y est les résultats sont la. Désolé pour le retard, mais je dois avouer que le mois de mai ne m'a pas beaucoup laissé de temps pour m'occuper des benchs.

Je ne fais pas durer le suspense plus longtemps, et je vous invite à féliciter avec moi NLU qui réalise ce challenge en moins d'1 ms.

Pour obtenir les résultats, j'ai fait faire 1000 fois le calcul en mesurant le total pour déterminer le temps moyen. 1000 étant un nombre suffisant pour que le temps d'exécution ne varie pas énormément d'un essai à un autre.

Vous retrouvez le classement dans le tableau suivant :


NomTemps Total (ms)Temps Moyen (ms)
1NLU6760,676
2ozimmer10301,03
3MaximeR15081,508
4Bjaout17091,709
5AntoinePa18751,875
6Didje00729522,952
7Mathieu36233,623
8Syx37473,747
9Callahan42004,2
10jihef50065,006
11yldieu735000735

Les codes de tous les participants vont arriver très vite. Il faut juste encore un peu de temps pour remettre le tout en forme et les enregistrer en version 2011 ou 2010 de LabVIEW.

MAJ du 02/07/2012 :

J'étais pas mal en déplacement et j'avais un peu oublié, mais les voila, les sources des VIs des participants. Vous trouverez également un doc écrit par NLU sur son code et un invité de dernière minute.

Merci à tous et bonne chance pour le prochain challenge qui arrivera très vite.

Maxime R.  

  CLA - Certified LabVIEW Architect / Architecte LabVIEW Certifié
  CTA - Certified TestStand Architect / Architecte TestStand Certifié

Download All
Comments
MaximeR
Active Participant
Active Participant
on

Bonjour à tous,

Le benchmark se fera certainement de la manière suivante :

Benchmark.png

Donc la lecture et l'écriture des fichiers ne sont pas prises en compte dans le temps d'exécution.

Plusieurs options sont dipos pour lire un fichier texte, dont une qui peut être bien utile pour ce challenge:

Lecture fichier texte.png

Bonne chance à tous.

PS: Vous pouvez poser vos questions ici sur le règlement. De plus si vous m'envoyez un code, pensez à poster un mesage ici également des fois que le code ne soit pas reçu, au moins je sais qui souhaite participer.

Maxime R.  

  CLA - Certified LabVIEW Architect / Architecte LabVIEW Certifié
  CTA - Certified TestStand Architect / Architecte TestStand Certifié

AntoinePa
Member
Member
on

Bonjour,

J'ai envoyé mon code ce matin. Moins de 10ms pour effectuer les 100 multiplications.

Je pense avoir pas mal optimisé et les bons résultats !

et vous ?

smi38
Member
Member
on

Hello,

Je n'ai pas encore fini de coder de mon côté, mais moins de 10 ms, chapeau.

Quelles sont les caractéristiques du pc en question ?

Callahan,

yledieu
Member
Member
on

Bonjour Maxime,

Est-ce que la méthode de lecture/écriture du fichier est imposée ?

Yohann L.
smi38
Member
Member
on

Bonjour Yledieu,

Je pense que la méthode de lecture écriture du fichier n'a aucune importance, car elle n'est pas prise en compte pour la mesure du temps de multiplication. Non ?

AntoinePa
Member
Member
on

Bonjour Callahan,

Les performances du PC sont proches de celle du PC final (Dell M4600).

smi38
Member
Member
on

Bonjour,

Je viens d'envoyer mon code à Maxime, mais je ne suis pas en dessous des 10 ms (sur mon pc).

smi38
Member
Member
on

Pour info, j'ai fais l'essai de la méthode de Karatsuba (algo récursif) pour voir.

Marie_Remondière
NI Employee (retired)
on

Et pour info, Maxime est en route pour Gardanne et Toulouse pour animer les journées techniques sur la mesure et le contrôle/commande. Quant à moi, je ne saurais vous répondre ! Donc soit on compte sur le fait qu'il aura le temps de regarder un soir dans la semaine, avec la connexion de l'hotel, soit il va falloir patienter jusqu'à vendredi au moins... allez courage !

Marie

AntoinePa
Member
Member
on

Ma solution est inspirée de cette méthode (sans récursivité !)

smi38
Member
Member
on

Ah ok..

Du coup j'ai laissé la méthode de Karatsuba de côté, mais ce n'était peut-être pas une bonne idée !

MaximeR
Active Participant
Active Participant
on

Bonjour,

Je vois que ce sujet intéresse, c'est cool. Pour la méthode de lecture, elle n'est pas imposée car elle n'est pas compté dans le bench comme la indiqué Callahan.

Bonne chance à tous.

PS: Comme Marie l'a fait remarqué, je suis en déplacement les 15 prochains jours, donc je serais pas toujours très réactif sur la communauté ou par email.

Maxime R.  

  CLA - Certified LabVIEW Architect / Architecte LabVIEW Certifié
  CTA - Certified TestStand Architect / Architecte TestStand Certifié

Mathieu.
Member
Member
on

Bonjour Maxime,

Je t'ai transmis mon code à l'instant.

Wait and see !

Cordialement,

Mathieu O.
Certified LabVIEW Architect - CLA (2013)
NLU
Member
Member
on

Bonjour Maxime,

Confirmez-vous que l'on peut choisir la méthode de lecture que l'on veut parmi les exemples que vous avez donnés?

(ça conditionne le format des données qui seront traitées par notre code)

Cordialement,

NLU

MaximeR
Active Participant
Active Participant
on

Bonjour,

Vous pouvez choisir une des deux méthodes proposées ou une autre si vous le voulez. La seule condition est que si vous manipulez les données, en dehors de la fonction de lecture, cela doit ^petre pris en compte dans le benchmark.

Cordialement.

Maxime R.  

  CLA - Certified LabVIEW Architect / Architecte LabVIEW Certifié
  CTA - Certified TestStand Architect / Architecte TestStand Certifié

Bjaout
Member
Member
on

Bonjour,

Voilà je transmets mon code aujourd'hui

Cordialement,

smi38
Member
Member
on

Bonjour Maxime,

Je t'ai également transmis aujourd'hui la dernière version de mon code.

On est 6 sur la brèche pour l'instant, ça promet

O. Zimmermann
Member
Member
on

Bonjour,

J'ai rendu ma copie !

Vive les vacances !

NLU
Member
Member
on

Bonjour,

Je viens d'envoyer mon code.

Cordialement,

   NLU

jihef
Member
Member
on

Bonjour,

J'ai envoyé ma contribution "par jalousies"...

L’algo est en O(n2) ça risque d’être moins bien que Karatsuba qui est en O(nlog2(3))… on verra bien.

L’important c’est de participer ! 

Cordialement

jihef
Member
Member
on

Bonjour,

Dans le fichier résultat, chaque ligne doit elle faire exactement 200 caractères (padding en tête avec des zéros) ou une longueur max de 200 caractères, la longueur dépendant de la valeur du résultat ?

Cordialement.

smi38
Member
Member
on

Perso j'ai 200 caracatères tout le temps.

De plus le fichier initial a toujours 100 caractères, avec du padding de zéros.

MaximeR
Active Participant
Active Participant
on

Bonjour,

Il est préférable que le résultat fasse 200 caractères. Cepedant, pour le test final je changerai les nombres, et je ferais en sorte que les nombres ne commencent pas par 0. De cette façon, on aura forcément des nombres de 200 caractères.

MaximeR

Maxime R.  

  CLA - Certified LabVIEW Architect / Architecte LabVIEW Certifié
  CTA - Certified TestStand Architect / Architecte TestStand Certifié

jihef
Member
Member
on

MaximeR a écrit:


                       

Bonjour,

Il est préférable que le résultat fasse 200 caractères. Cepedant, pour le test final je changerai les nombres, et je ferais en sorte que les nombres ne commencent pas par 0. De cette façon, on aura forcément des nombres de 200 caractères.

MaximeR


                   

... sous réserve de choisir des nombres ne commençant pas par 0, qui fasse 100 caractères... et qui soient suffisamment grands.

1099  *  1099    =    10198

Jihef

MaximeR
Active Participant
Active Participant
on

En effet, j'ai répondu peut être un peu vite. Cependant, dans l'énoncé, il est indiqué que la multiplication est un produit de deux nombres de 100 digits et que le résultats fait 200 digits, il faut donc remplir avec des 0 devant, d'ailleurs, dans le fichier exemple, il y a des nombres commençant par 0.

Cordialement.

Maxime R.  

  CLA - Certified LabVIEW Architect / Architecte LabVIEW Certifié
  CTA - Certified TestStand Architect / Architecte TestStand Certifié

smi38
Member
Member
on

Je vote pour les 200 digits (j'avoue ça m'arrange )

jihef
Member
Member
on

J'ai envoyé une version qui devrait être conforme aux exigences contractuelles en matière de format du fichier de sortie...

Cordialement.

Bjaout
Member
Member
on

Bonsoir,

J'envoie ma version 2 un peu plus rapide que la première maintenant.

Cordialement,

didje007
Active Participant
Active Participant
on

Bonsoir,

J'ai envoyé ma version.

Cdlt

yledieu
Member
Member
on

Bonjour,

Je viens d'envoyer mon code.

Yohann L.
Syx
Member
Member
on

Bonjour

J'ai envoyé mon code.

MaximeR
Active Participant
Active Participant
on

Bonjour à tous,

La possibilité de participer au concours est maintenant terminée. Je n'aurais pas le temps de faire les test aujourd'hui et la semaine prochaine je suis en congès (merci les jours fériés ). je reviendrais vers vous la semaine suivante, le temps de retoucher un peu aux codes de certains afin de respecter les formats de noms et d'emplacements de fichier et m'assurer que les résultats du benchmark récompense bien le meilleur temps d'exécution.

Cordialement.

Maxime R.  

  CLA - Certified LabVIEW Architect / Architecte LabVIEW Certifié
  CTA - Certified TestStand Architect / Architecte TestStand Certifié

Marie_Remondière
NI Employee (retired)
on

Bon bah moi j'attends le nom du vainqueur pour pouvoir le publier dans la NINews de juin

smi38
Member
Member
on

Comme quoi d'un pc à l'autre ça varie beaucoup, j'étais à 0.9 milliseconde de moyenne sur un Core i7 du bureau

En tout cas bravo à NLU, c'est un temps de folie quand on y pense ^^

MaximeR
Active Participant
Active Participant
on

Effectivement, ca peut beaucoup varier. Ce qui est sur, c'est que j'ai testé sous les mêmes conditions, et plusieurs fois pour m'assurer que les résultats sont corrects. Et dans tous les cas de figures NLU était le plus rapide.

Maxime R.  

  CLA - Certified LabVIEW Architect / Architecte LabVIEW Certifié
  CTA - Certified TestStand Architect / Architecte TestStand Certifié

Mathieu.
Member
Member
on

Beau classement ! et félicitations NLU : victoire nette et sans bavure => le seul sous la ms...

Nous verrons donc sous peu quelles "bottes secrètes" ont été utilisées dans les différentes façons de réaliser ces multiplications.

To be continued...

Cordialement,

Mathieu O.
Certified LabVIEW Architect - CLA (2013)
NLU
Member
Member
on

Je suis content d'avoir remporté ce challenge : une bonne nouvelle dans une période un peu chaotique!

J’ai passé la certification CLAD il y a quelques temps. Je vais pouvoir m’attaquer à la certification CLD. Ça devrait m’aider pour mon avenir…

Mon employeur a décidé de me jeter dans la grande poubelle des plans sociaux avec une centaine d’ingénieurs du site où je travaille.

Considérons que c’est une bonne opportunité pour rebondir et réaliser ses projets…

Je travaille depuis 6 ans avec une équipe basée à Bangalore (Inde). Je prévois de partir m’installer là-bas d’ici quelques mois.

Avis aux employeurs qui travaillent à l’international : si vous cherchez quelqu’un qui puisse vous aider à piloter et développer vos équipes techniques à Bangalore, je suis à vous !

NLU

http://nicolas.lurol.free.fr/

Mathieu.
Member
Member
on

Content de voir que ce résultat apporte un peu de soleil (et en ce moment c'est précieux...) du côté de chez NLU !

On va voir comment on peut aider pour ta situation actuelle (on sait jamais avec les réseaux )

To be continued...

Cordialement,

Mathieu O.
Certified LabVIEW Architect - CLA (2013)
O. Zimmermann
Member
Member
on

Félicitations en grands nombre, Nicolas !

J'ai hâte moi aussi de de découvrir les astuces de ton algorithme.

De mon côté, comme plusieurs autres concurrents, j'ai implémenté un calcul qui s'assimile à la multiplication par jalousies (ou à un changement de base numérique, qui revient un peu au même) et j'ai ensuite beaucoup affiné les options de compilation, d'exécution et de parallélisme. Du bon travail de fond mais... il me manquait la formule magique !! 😉

oz

NLU
Member
Member
on

Je ne pense pas que ma méthode de calcul soit révolutionnaire.

J'ai surtout travaillé sur les étapes de conversion de données qui sont très gourmandes en ressources.

Et j'ai essayé de mettre sous forme de constante tout ce qui peut être calculé à l'avance.

Ca m'intéresserait de savoir ce qui peut être encore amélioré en puisant des idées chez les autres...

jihef
Member
Member
on

Bravo Nicolas, impressionant !

... et aussi félicitations à Maxime pour le choix du sujet qui a rencontré un certain succès et a abouti à un classement plutôt serré avec un beau tir groupé des cinq premiers.

jihef

MaximeR
Active Participant
Active Participant
on

Bonjour,

Je vais publier rapidement les sources des codes, il faut juste que je trouve 1 ou 2 heures pour arriver à le faire. Merci NLU pour le doc, je le mettrais avec les sources, car oui, on ne peut pas joindre de fichier sur un commentaire.

Merci aussi pour les encouragements, je vais essayer de trouver aussi passionant pour le prochain.

Maxime R.  

  CLA - Certified LabVIEW Architect / Architecte LabVIEW Certifié
  CTA - Certified TestStand Architect / Architecte TestStand Certifié

smi38
Member
Member
on

Oui bravo aussi à Maxime pour le choix du sujet, et aussi son temps passé sur ce challenge.

PS : en plus NLU ressemble un peu à Jim Kring... moi je dis il y a un chromosone LabVIEW qui traine 

--> Je sors

didje007
Active Participant
Active Participant
on

Tout d'abord bravo à NLU.

J'attends de voir le code gagnant.

Et aussi comme Jihef je dis bravo à Maxime car le sujet était intéressant.

Contributors