Le C, un langage de bas niveau ?

Voilà une question étrange. Selon Alan Perlis , « un langage de programmation est bas niveau lorsqu’il nécessite de faire attention aux choses qui ne sont pas pertinentes »

Il y a de nombreuses façons d’interpréter le « pas pertinentes ». Prenons un exemple un peu technique mais révélateur. Les réels en machine sont stockés sous la forme d’approximations flottantes. Sur 64 bits, un flottant est constitué d’un bit de signe s, puis de 11 bits pour stocker son exposant e en base 2 et enfin de 52 bits pour sa mantisse m. L’interprétation se fait grâce à la formule

    \[(-1)^s * 2^{e - 1023} \left(1 + \frac{m}{2^{52}}\right)\]

Si on souhaite, à partir d’un flottant récupérer les trois champs s, e et m, comment s’y prendre ? Chaque langage proposant des fonctionnalités bien particulières je propose dans la vidéo qui suit un comparatif en langage C et en langage Ada qui permet de mieux saisir la phrase d’Alan Perlis et d’aborder des aspects souvent ignorés des néophytes de ces langages.

Voyons comment on fait en C :

Et en Ada:

Compléments en LyX

Dans ces vidéos, quelques astuces et informations pour rédiger de beaux documents avec LyX.

Commenter des formules avec des accolades inférieures ou supérieures

Utilisation plus approfondie de Minted

Télécharger le fichier de couleurs proposé dans la vidéo et le copier dans votre home en créant les répertoires indiqués. Il est possible de recopier dans un terminal fraîchement ouvert

mkdir texmf/tex/latex/couleurs

puis de copier le fichier téléchargé dans ce dossier

Interaction LyX et LaTeX

Mes sélections du moment

Comme je ne voulais pas créer un article pour chacun, je vous transmets quelques liens, classés par thèmes, que je recommande chaudement.

Une magnifique présentation de la mécanique quantique par Julien Bobroff :

Restons quantique, mais pas seulement, avec monsieur Alain Connes. Beaucoup moins accessible, mais parfaitement délicieux pour qui a déjà un bon bagage en maths :

Alexandre Astier, « quanticomique » :

En plus terre à terre, plus technophile, mais très clair et très sympathique, Adrien D et son site https://www.linuxtricks.fr et sa chaîne https://www.youtube.com/channel/UCDKPGD9T00eS_l–D_DRTUQ

Côté maths, ça ne changera pas, la référence (surtout pour son forum incroyable) : http://www.les-mathematiques.net/phorum/ Bon, certes, c’est un poil austère, mais alors, quel contenu !

Il y a aussi ce jeune homme qui produit des vidéos que je trouve très intéressantes sans pour autant choisir des thématiques mathématiques faciles. https://www.youtube.com/channel/UC0NCbj8CxzeCGIF6sODJ-7A

Et pour finir en musique, l’incontournable David Louapre sur sa chaîne Science Étonnante:

Petit guide d’installation (lyx / latex, sage, fpc, geany …)

La distribution Linux qui va bien

Dans ces vidéos, j’imagine que vous avez déjà installé une distribution Linux de base Debian (ce qui inclut Ubuntu ou Linux Mint). Le net regorge de vidéos expliquant pas à pas la démarche (si vous avez déjà un autre système, comme windows par exemple, l’installation proposera un double démarrage, pas d’inquiétude). Il est aussi possible, pour les moins téméraires, d’installer une machine virtuelle (par exemple avec Virtualbox). Je ne traite pas des installations sur les autres distributions car, d’après mon expérience, le public concerné saurait déjà faire ce que je dis (exceptée peut-être l’astuce pour utiliser minted dans LyX qui requière l’installation de pip3)

Les paquets logiciels nécessaires

Une fois la distribution installée, on peut faire ses courses et aller chercher quelques applications fort utiles quand on fait des maths ou de l’info. Je vous montre comment installer mes favorites, résultat d’un certain nombre d’années d’expériences de tous ces outils et d’autres que j’ai éliminés (mais qui peuvent très bien convenir à certains utilisateurs je n’en doute pas).

De quoi écrire des maths et insérer du code dans des documents efficacement

Voilà c’est parti pour installer tout ce qu’il vous faut en une (voire deux) ligne(s) de commande :

On configure LyX et on fait ses premiers pas avec des raccourcis efficaces

Et maintenant, on configure LyX (avec la petite astuce pour colorer la syntaxe via le paclage Minted) et rédiger de jolis documents :

Comme promis, un petit guide pour taper des maths efficacement en LyX (attention ce n’est pas suffisant, mais bon, il faut déjà bien commencer !)

Utilisation de Sage (en terminal et dans un navigateur)

Le conte de Fibonacci démystifié

Si vous avez suivi le conte https://www.libremaths.fr/2020/05/04/un-reste-loin-dans-la-suite-de-fibonacci/, que vous vous êtes dit « heureusement qu’on a des ordinateurs » et que vous aimez croire qu’ils nous sont indispensables, ne lisez surtout pas la suite !

Hé oui, vous vous en doutiez peut-être, la force de la pensée humaine suffisait. Inutile d’aller chercher l’arsenal technologique pour répondre à cette fameuse question : quel est le reste par 25 du terme d’indice 10^{18} de la suite de Fibonacci ? Question dont, je le rappelle, la réponse est parfaitement inutile, et donc parfaitement indispensable à tout esthète qui se respecte 🙂

Une façon élégante (à mon goût), de voir le problème est de choisir de travailler dans un anneau bien adapté au problème. Allons-y et commençons par considérer A=\mathbb{Z}/25\mathbb{Z}, \chi=X^2-X-1\in A[X] et B=\frac{A}{(\chi)}. On note enfin \pi l’épimorphisme canonique de A sur son quotient B. Les éléments de A seront notés \overline{x} pour x\in \mathbb{Z}.

Alors B est un A module libre de base (\pi(1),\pi(X)). Par récurrence, on en déduit immédiatement que:

    \[\pi\left(X^n\right)=\overline{F_n}\pi(X)+\overline{F_{n-1}}\]

De plus,, en utilisant l’égalité \pi\left(X^{2}\right)=\pi\left(X+1\right) et le fait que \pi est un morphisme d’anneaux, on obtient :

    \[\pi\left(X^{25}\right)=\left(\overline{5}\pi\left(X\right)+\overline{3}\right)^{5}=\sum_{k=0}^{5}\overline{\binom{5}{k}}\overline{5}^{k}\pi\left(X\right)^{k}\overline{3}^{5-k}\]

Or, pour k\in\left\{ 1;\dots;5\right\}, on a \overline{5}^{k}\overline{\binom{5}{k}}=\overline{0} et donc

    \[\pi\left(X^{25}\right)=\overline{3}^{5}=\overline{3}^{3}\times\overline{3}^{2}=\overline{2}\times\overline{9}=\overline{18}\]

donc

    \[\pi\left(X^{25m}\right)=\overline{18}^{m}\]

conjointement au fait que \pi\left(X^{n}\right)=\overline{F_{n}}\pi\left(X\right)+\overline{F_{n-1}} (pour n\geqslant1) et que B est un module libre de base \left(\pi\left(1\right);\pi\left(X\right)\right) on en déduit que F_{25m} est nul modulo 25 pour tout naturel m. Comme 10^{18} est un multiple de 25, on a bien montré que F_{10^{18}} est divisible par 25.

On peut même aller plus loin (attention, on se rapproche de l’infini et l’au delà) : comme \pi\left(X^{25m}\right)=\overline{18}^{m}, et que \overline{18^4}=\overline{-7}^4=\overline{-1}^2=\overline{1}, on en déduit que

    \[\pi\left(X^{100k}\right)=\overline{1}= \overline{F_{100k}}\pi\left(X\right)+\overline{F_{100k-1}}\]

et donc, en résumé : \overline{F_{100k-1}}=\overline{1} et \overline{F_{100k}}=\overline{0} ce qui permet de retrouver la suite de Fibonacci périodiquement, modulo 25, tous les 100 termes !

Et voilà la démystification 🙂

Un reste, loin dans la suite de Fibonacci

Épisode 1 : ça parle de quoi cet article ?

Le plus simple est que je vous le raconte en vidéo 😉

Petite remarque: dans cette vidéo je donne un ordre de grandeur du nombre de chiffres de F_N. Mais en fait en notant r=\frac{\ln\phi}{\ln10}, en majorant \ln(1+x) par x (pour x>0), on obtient assez facilement

    \[nr-\frac{\ln5}{2\ln10}-2^{-n}<x<nr-\frac{\ln5}{2\ln10}+2^{-n}\]


Pour n=N=10^{18} on obtient au dixième près

    \[x\sim208987640249978733,8\]


ce qui montre que F_{N} possède exactement 208987640249978734 chiffres.

Épisode 2 : si on essayait …

…malgré tout de coder le calcul des termes dans un langage compilé ? (ou encore: si je trouvais un prétexte pour jouer avec le langage Ada ?)

Première partie :

Deuxième partie :

Troisième épisode : les maths à la rescousse !

Un peu d’algèbre linéaire et la fameuse « exponentiation rapide ». Un algorithme qui décoiffe 🙂

Quatrième épisode : encore des maths !

Mais là, on part dans le monde de l’arithmétique modulaire pour appliquer l’algorithme d’exponentiation rapide

Épilogue

On implémente tout ce qu’on a vu en Ada pour donner une réponse instantanée à notre problème

Erratum: il s’agit de monsieur Daniel Feneuille (et non David) dont je voulais parler. Au passage, ses cours sont disponibles ici : https://ada.developpez.com/cours/iut/

Je vous parlais aussi d’un papier que j’ai rédigé sur les suites récurrentes linéaires d’ordre 2 (pour un public averti) :