Forum de mathématiques - Bibm@th.net

Ok , pas de souci. merci

Oui c'est ce que m'a confirmé le collègue qui s'occupe de mon PC , lorsque j'ai un souci pour charger une application ... donc je verrai par la suite pour le télécharger sur le site Hasquell ...

HASKELL

Bonjour:
Re;
Pour installer Haskell, deux options s'offrent à vous, le télécharger depuis le site du projet ou l'installer depuis le gestionnaire de paquet de votre système d'exploitation préféré :

# Pour Ubuntu
$ apt-get install haskell-platform

J'ai vérifié sur mon système ; je suis allé dans gestionnaire de paquets synaptiques ; ce paquet ne figure pas , il y a uniquement : @ apt

Donc je suppose qu'il me faudra aller sur la plateforme Haskell pour télécharger cette application ...?

Juste avant de partir en cours, j'ai refait le benchmark avec arithmoi… résultat : 18 ms en moyenne pour générer la liste des premiers qui nous intéressent ! 15 fois plus rapide que la version naïve et 2 fois plus rapide que la version Python et sans autre tips and tricks.

Sur ce, je vais en cours !

Ok , j'ai lu ... mais je ne comprend pas tout ..., effectivement je comprend le but de tes explications, mais  pour quelqu'un qui fait ou veut modifier le programme .

En python j'ai su le faire (sur certaine partie) mais surement pas en C++ ...

Je pense que Yoshi serra à même de voire la différence ...

Moi je ne peux que tester , comme tu l'as très bien fait d'ailleurs ...

Je vais me comporter comme la tortue et non comme le renard...

Bonjour
@rareStrophe.
ok pour tes explications afin de rendre le programme plus rapide ...(je n'y connais strictement rien en programmation) mais je comprends tes explications...

Ceci dit : gagner du temps sur cette première partie du programme de la  def eratostene(n): qui énumère les nombres premiers $P\leqslant\sqrt(n)$
permettra de gagner du temps, dans la deuxième et troisième partie ...

Mais pourquoi avoir extrait tous les nombres premiers < 3000 , pour comparer les vitesses (éfficacité) des deux langages de programmation je suppose suite à  tes explications....
N'oublies pas que pour $n = 999 999 999$ , c'est la racine carrée de $n$ qui est à prendre en compte pour extraire les nombres premiers Ératosthène dans cette première partie...

Premiers Ératosthène que l'on va ensuite utiliser, dans la deuxième et troisième partie, afin de cribler : la liste "ou tableau " de 1,1,1......< n//30 .

Exemple :

Donnez N: 3000
[7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73] premiers Ératosthène < racine de 3000

crible Ératosthène : [1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0]
Nombre premiers criblés famille 7 : 55 ----- 0.0

crible É ET G: [0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0]
Nombres P' non congru 2n[pi] ou couple P'+q = 2N, de (i) à 3000 famille 7 : 18 ----- 0.0

Partie A : un monde à découvrir

Un langage de programmation tout en un

Le langage de programmation Haskell est en quelque sorte une plateforme toute en un. Une fois celui-ci installé, nous retrouverons sur notre ordinateur les quelques outils suivants :

• GHC : The Glasgow Haskell Compiler ;

• GHCi : L'interpreteur interactif ;

• Les paquets Haskell les plus utiles ;

• Un gestionnaire de projet.

Pour installer Haskell, deux options s'offrent à vous, le télécharger depuis le site du projet ou l'installer depuis le gestionnaire de paquet de votre système d'exploitation préféré :

Pour s'assurer que tout fonctionne, demandons à ghc, le compilateur d'Haskell, de nous afficher son numéro de version. Ceci se réalise à l'aide de la commande qui suit :

Le numéro de version pouvant évidemment varier selon votre installation.

Étant donné qu'à ce stade tout devrait fonctionner, créons d’emblée notre premier programme : le bien connu "hello, world!". Pour ce faire, ouvrons notre éditeur de texte préféré afin d'y écrire le code suivant :

que nous allons enregistrer dans un fichier main.hs.

Afin d’exécuter ce programme, nous allons devoir le compiler. La compilation consiste à transformer un programme textuel adapté à la compréhension des humains, du moins ceux formés pour ça, en un programme exécutable composé de 0 et de 1, adapté à la compréhension de l'ordinateur afin que ce dernier sache quelles opérations utiliser pour réaliser les tâches qui lui sont demandées.
Pour ce faire, ouvrez votre terminal et placez-vous dans le dossier contenant le fichier main.hs que vous venez de créer. Lorsque vous y êtes, lancez la commande suivante

Bravo ! Vous venez d'obtenir votre premier programme en Haskell ! Vous voyez, ce n'était pas bien difficile ! À présent, il ne nous reste plus qu'à l'exécuter. Pour ce faire, tout en restant dans le même dossier, lancez la commande suivante :

Il nous est déjà possible de remarquer deux trois faits intéressants.

• La ligne

  -- Mon premier programme

  n'a pas été exécuté. Ceci est dû au fait que -- est la marque démarrant un commentaire qui sera ignoré par le compilateur.

• Comme en C, C++, Java, Rust, ou encore Python, la fonction main est le point d'entré disant au compilateur où démarrer le programme.

• La fonction print affiche les guillemets autour de notre chaine de caractères. Nous expliquerons ce dernier fait plus loin.

Vous vous demandez peut-être s'il est possible de demander au compilateur d'enregistrer l'exécutable dans un fichier au nom spécifique. Sachez que c'est effectivement possible avec -o. Pour ce faire, procédez ainsi :

Vous pouvez alors exécuter le programme comme suit :

Intéressons-nous à présent au deuxième outil que nous utiliserons dans ce premier post : ghci. Comme indiqué dans l'introduction, ghci est un interpréteur intéractif, c'est-à-dire qu'il exécutera chacune de nos lignes de code au fur et à mesure que nous lui donnerons. Pour lancer ghci rien de plus simple :

Comme pour n'importe quel interpréteur, nous pouvons donc donner du code à ghci afin qu'il l'exécute. Voici quelques exemples :

Comme nous pouvons le voir, ghci exécute nos lignes de codes sans se poser de question tant que celles-ci sont valides et font sens pour lui. Les deux premiers exemples montrent qu'il est possible d'ajouter ou omettre les espaces non significatifs. Le troisième exemple montre un fait surprenant pour une personne venant d'un autre langage de programmation. Haskell est capable de gérer de nombres extrêmement grands ! En effet, nous pouvons même aller plus loin, par exemple :

Bien évidement, vous pouvez mettre le nombre arbitrairement élevé de votre choix. En réalité, là où d'autres langages de programmation considèrent les nombres comme étant des entités vivantes dans un espace délimité en mémoire, int8 pour des entiers sur 8 bits, int16 pour des entiers sur 16 bits, int32 pour des entiers sur 32 bits, etc… Haskell, dispose d'une entité Integer qui se rapproche de la définition mathématique de nombre entier : n'importe quelle suite de chiffre de n'importe quelle longueur. Nous expliquerons dans le prochain post les différences avec les entiers que l'on retrouve dans d'autres langages de programmation.

Bien entendu, ghci gère les variables et les fonctions où, à nouveau, il est possible d'ajouter ou omettre des espaces non significatifs.

ghci est de plus un formidable outil en mesure d'importer les fonctions de vos fichiers afin de les utiliser. Pour ce faire rendez-vous dans le dossier contenant un de vos fichiers Haskell. Nous supposerons ici que nous voulons importer le fichier main.hs. Lancez alors ghci et effectuez les manipulations suivantes

Maintenant que tout a été chargé, il est possible d'exécuter la fonction main que nous avons écrite plus tôt

Petit exercice : Modifier la fonction main dans main.hs de sorte que vous puissiez afficher "Bonjour [votre pseudo]" dans ghci.
Comme nous ne savons toujours pas composer des chaines de caractères avec des variables, nous devons nous contenter d'écrire une fonction à usage unique :

puis nous chargeons et lançons le tout dans ghci

Finalement, pour quitter ghci, tapez ce qui suit

Les bases de la programmation fonctionnelle et d'Haskell

Nous savons à présent utiliser les outils de base d'Haskell, il est donc grand temps d'apprendre à programmer avec celui-ci. Toute fois, avant de s’aventurer plus loin, il va nous falloir nous poser une question primordiale : qu'est-ce qu'une application ?

Si vous avez fait quelques maths, vous savez connaissez alors la définition suivante:

qu'il est possible réécrire de manière plus digeste comme cela :

Mais alors pourquoi parler d'application ? Cela est dû au fait que la programmation fonctionnelle fait en réalité plus référence à ce qu'on appelle application en français. Ainsi, les langages de programmations fonctionnels et a fortiori Haskell, suivent tous cette définition que l'on peut aussi désigner à l'aide des règles suivantes :

• Toute application doit prendre un argument ;

• Toute application doit retourner une valeur ;

• Toute valeur retournée par une application doit être unique.

Cette dernière règle est connue sous le doux nom de principe de transparence référentielle.

Néanmoins, afin de ne pas être trop perdu avec les différentes ressources disponibles,
admettons à présent que le mot fonction correspond à une application.

Commençons avec l'exemple le plus simple qui soit, la fonction identité. Pour ce faire, lancez ghci et entrez le code suivant :

Cette fonction identity accepte un argument x et nous le retourne sans rien y faire.

Nous remarquons ici une des premières forces du langage Haskell : l'inférence de types. En effet, comme nous pouvons le voir, il nous est possible de donner à la fonction identity n'importe quel argument, qu'il soit un nombre, une chaine de caractères ou encore une liste. Le compilateur sera en mesure de déterminer le bon type à appliquer le moment venu sans que l'on ait besoin de l'expliciter nous-même.

Dirigeons nous à présent vers l'utilisation de variables. Pour cela, écrivons les lignes suivantes dans le fichier main.hs :

que nous compilons ensuite de la manière suivante :

Horreur, cela ne compile pas ! Au vue de ce que l'on sait déjà, saurez-vous expliquer pourquoi ?
Il faut savoir que les variables en Haskell ne sont en rien… variable ! Si celles-ci l'étaient, cela violerait le principe d'unicité. Visualisez donc une variable Haskell comme une définition d'une valeur donnée. Un peu comme on définit $\pi = 3.1415...$. Il ne viendrait à l'idée de personne de modifier la valeur de $\pi$. C'est en quelque sorte ce qu'il se passe en Haskell.

Petite note subsidiaire:
Comme il est assez pénible de relancer l'interpréteur ghci
à chaque fois que l'on veut faire des testes quelconques,
celui-ci permet de redéfinir les variables.
Ainsi, le code précédent fonctionne dans ghci.

À la conquête des nombres premiers !

Mettons à présent à profit tout ce que nous avons vu plus haut afin de générer la liste des nombres premiers jusqu'à $\lfloor\sqrt{2\times n}\rfloor$.

Premièrement, commençons par mettre à profit le côté lazy d'Haskell afin de ne pas nous soucier des ressources. Ainsi donc, créons une liste infinie de nombre premier.

Afin de tester ce bout de code, il nous faut charger le fichier dans ghci et lancer appeler la fonction. Pour ce faire, enregistrez le code précédant dans un fichier primes.hs puis lancez ghci. Une fois ceci fait, charger le contenu de ce fichier primes.hs dans ghci de la manière suivante :

Mais que se passe-t-il ? Pourquoi une erreur s'affiche-t-elle ? Eh bien cela est dû au fait que notre fonction sieve s'attend à recevoir une liste en paramètre. Nous expliquerons pourquoi juste après. Pour l'heure, écrivons une nouvelle fonction qui appelle sieve et lui passe en paramètre la liste infinie [2..] de la façon suivante :

Nous pouvons à présent utiliser la fonction primeNumbers comme suit:

Comme nous pouvons le voir, nous obtenons bel et bien une liste infinie ne contenant que les nombres premiers. C'est très bien, mais vous vous retrouvez sans doute pantois avec votre terminal inaccessible. Pour interrompre cette interminable liste, faites ctrl-c.

Afin de ne pas attendre indéfiniment la liste infinie de nombre premiers, choissons de n'en garder que quelques-un. Pour ce faire, utilisons la fonction Haskell take :

Avant d'aller plus loin, essayons de comprendre comment fonctionne la fonction sieve :

Haskell applique le pattern matching x:xs à cette liste : ainsi pour la liste [2..], x=2 et xs=[3,4,5,...]; avant d'évaluer ce qu'il reste de xs de la façon suivante

Petite subtilité ici, xp `mod` x > 0 est ce qu'on appelle un filtre.
C'est à dire que l'on filtre les éléments de sorte à ne garder que ceux
qui répondent à la condition $xp > 0 [x]$.

On évalue donc xs qui commence avec xp=3 or xp=3 passe le filtre. On se retrouve à présent à passer récursivement la liste [3..] à sieve.

x:xs avec x=3 et xs=[4,5,6,...].

Rebelote

et ainsi de suite. Finalement, on trouve tous les nombres premiers par récursion.

Intéressons-nous à présent à récuperer les nombres premiers qui nous intéressent, ceux qui sont inférieurs ou égaux à $\lfloor\sqrt{2\times n}\rfloor$. Pour ce faire, utilisons cette fois-ci la fonction Haskell takeWhile au sein de la fonction suivante :

Cette fonction eratosthenes s'utilise alors comme suit :

À quoi ressemble donc notre code jusqu'à maintenant ? Eh bien, il est composé des trois lignes suivantes :

Comment cela peut aussi bien fonctionner ? Pour cela il nous faut expliquer takeWhile. takeWhile est une fonction bien utile qui retourne une liste composer de tout les éléments correspondant au filtre passé en paramètre. Ce filtre est, ici, <= floor . sqrt $ 2*n, ce que l'on peut lire

Arrêtons-nous un instant et demandons-nous si ce programme s'effectue rapidement. Pour ce faire, compilons le programme suivant à l'aide de ghc :

À présent, testons !

18 ms pour générer les nombres premiers jusqu'à $\lfloor\sqrt{2\times 3000}\rfloor$...

404 ms pour générer les nombres premiers jusqu'à $\lfloor\sqrt{2\times 999999999}\rfloor$ ! Ça va pas du tout ! C'est beaucoup trop lent ! Peut-on rendre tout ceci plus rapide ? Oui, c'est possible ! Nous allons voir comment dans le post suivant.

Ave,

Correction faite.
Moi non plus, je n'aime pas qu'on écorche les noms...

@+