Vous croyez déjà tout savoir sur la multiplication ? Vous allez être surpris ! Voici trois méthodes pour multiplier deux nombres entiers.

• Multiplication posée du bon élève.




 

• Méthode du cancre.
 




Mode d'emploi : A gauche on prend toujours la moitié en arrondissant, s'il le faut, vers le bas ; à droite on prend toujours le double. Puis on supprime les lignes (en noir) dont le nombre gauche est pair et à droite on additionne les lignes restantes (en rouge).
 
 

• Méthode de Karatsuba (publiée en 1962).
On sépare chaque facteur en deux parties

puis on effectue les multiplications suivantes :



Le résultat est ensuite

Remarque
L'idée de tout ça c'est de se ramener à des opérations élémentaires (opérations entre deux nombres entre 0 et 9). Sur un ordinateur le choix d'un bon algorithme peut accélerer considérablement le temps de calcul — quelques jours pour des facteurs constitués de plusieurs milliards de chiffres ! Le calcul avec de très grands nombres n'est pas une question purement théorique mais a beaucoup d'applications, notamment en théorie de cryptage.
 
Questions

1. Pourquoi la méthode du cancre fonctionne-t-elle ? Les deux facteurs jouent des rôles différents; lequel choisir pour quel rôle ?
2. Utilisez la méthode de Karatsuba pour calculer 3116 x 1014. Pourquoi cette méthode fonctionne-t-elle ?
3. Avec la méthode classique (multiplication posée du bon élève), combien de multiplications élémentaires sont nécessaires pour calculer le produit de deux nombres à n chiffres ?
4. En réitérant la méthode de Karatsuba on obtient un algorithme. Combien de multiplications élémentaires sont alors nécessaires pour calculer le produit de deux nombres à n chiffres ? Comparer avec l'algorithme classique.

Réponses
Cliquez pour afficher les solutions en format pdf.

Et pour finir une vidéo présentant une méthode qui produit une belle calligraphie — elle s'appelle donc la multiplication chinoise !

L'idée de base de la multiplications chinoise est le fait suivant : un ensemble de n droites parallèles coupe un autre ensemble de m droites parallèles en nxm points.

A l'occasion de la solution d'un joli exercice de type colle sur les matrices (voir le blog de Pierre Lecomte), je suis naturellement amené à poser la question suivante.

Soit A une matrice inversible à coefficient dans un corps. Alors par des opérations élémentaires sur les lignes on peut transformer A en la matrice unité. En fait c'est la méthode du pivot de Gauss qui permet cela. On en déduit que A est un produit de matrices correspondantes aux trois types d’opérations élémentaires (permutation de lignes, multiplication d’une ligne par un scalaire non-nul, ajout d’une ligne à une autre).
Cette écriture en produit est pratique car elle permet de prouver plein de choses. Par exemple, pour montrer que le déterminant conserve les produits il suffit de le vérifier pour la multiplication entre une matrice de ce type et une matrice quelconque — et c'est tout facile.

Or comment ça se passe-t-il sur un anneau ? Plus précisément :

Soit R un anneau commutatif et A une matrice carrée avec coefficients dans R telle que det(A) est une unité de R. On sait que A est une matrice inversible (c’est du classique, voir par exemple ici pour la formule qui donne l'inverse en fonction de (det A)^-1 et de la comatrice).
Question : Peut-on ramener A à la matrice unité par des opérations élémentaires ?

Peut-être avez-vous déjà réfléchi là-dessus et connaissez la réponse...

Mystères de la psychologie

Posez les deux questions suivantes à un ami.

"Comment demandes-tu l'heure à un sourd?" — Probablement il fera un geste.
"Comment demandes-tu un peigne à un chauve?" — Probablement il fera également un geste... au lieu de demander simplement!

Exemple:

Presque tout le monde tombe dans ce piège. Et très souvent, si plusieurs personnes sont présentes, ce n'est pas la personne à laquelle on a adressé la parole qui répond mais une autre qui se sent moins observée!

Nous mathématiciens sommes les spécialistes de la généralisation. Si nous avons trouvé une méthode pour résoudre un problème particulier nous essayons de l'adapter à des situations similaires ou plus générales. Nous sommes (dé)formés ainsi et ça fonctionne — au prix que ça n'aboutit pas toujours à la méthode la plus élégante.

Les juristes, en revanche, ont l'habitude de considérer chaque cas de manière indépendante. En effet, tout avocat sait que le fait d'avoir gagné un procès aujourd'hui n'implique pas qu'un procès identique sera gagné demain.
Je posais la question du peigne aussi à mes amis juristes et avocats. Sans avoir procédé à une statistique fiable, j'ai l'impression que le pourcentage des piégés est inférieur chez eux que chez les mathématiciens.

Deux autres exemples:

En économie, physique, ingénierie, on enseigne la méthode des multiplicateurs de Lagrange : Si P est un extrémum d'une fonction f de n variables x₁, ... ,x_n sous m contraintes données par g₁(x₁,...,x_n)=0, ... , g_m(x₁,...,x_n)=0, alors il existe des réels λ₁, ... ,λ_m tels que

Généralement, lorsqu'on enseigne ce théorème à des non-matheux, il est préférable de ne pas faire la démonstration en toute généralité. D'habitude je me contente d'expliquer deux cas particuliers où on "voit" géométriquement ce qui se passe :

• n=3 et m=1. Grâce à la règle de dérivation d'une fonction composée, on montre que les gradients de f et g en P sont orthogonaux au plan tangent à la surface décrite par g(x,y,z) = 0. Donc ces gradients sont colinéaires.


• n=3 et m=2. De même, on montre que les gradients de f, g₁ et g₂ en P sont orthogonaux à la tangente à la courbe décrite par g₁(x,y,z) = g₂(x,y,z) = 0. Ils sont donc coplanaires.

Concernant une application de ce théorème j'ai une question à laquelle vous savez peut-être répondre.

Y a t-il un exemple élémentaire mais non trivial? L'exemple classique de minimisation de coût lorsqu'on construit une boîte rectangulaire dont le volume est fixé et dont le couvercle coûte, au cm², le double des autres côtés n'est pas vraiment intéressant; en effet, on peut isoler l'une des variables dans l'équation de la contrainte et se ramener à une fonction de deux variables indépendantes.

Dans ce billet j'ai posé l'exercice de montrer que la loi binaire

x¤y := x(y²+1)^½+y(x²+1)^½

définit une structure de groupe sur l'ensemble des réels. Le seul obstacle est l'associativité; la preuve n'est pas très difficile (il s'agit d'un simple transport de la loi + par le sinus hyperbolique). Mais avec Maple je n'arrive pas à faire la preuve par force brute; en effet, je ne sais pas comment faire en sorte que le logiciel simplifie l'expression concernée (tandis que le logiciel Xcas y arrive, comme l'a remarqué Tukikun).

Dans le même esprit, je me demande si quelqu'un arrive à démontrer avec Maple que, sur les courbes elliptiques (réelles), l'addition par la méthode des sécantes est associative. Je n'y suis pas arrivé.

Quelques fois on garde un souvenir très complet d'une démonstration mathématique, et ce souvenir inclût également des accessoires absurdes et inutiles comme par exemple le numéro de la page du livre où on l'a apprise ou la couleur de la chemise du professeur qui l'a expliquée...

Ci-dessous j'explique, en forme d'exercice corrigé, pourquoi le groupe SO(3) de rotations dans l'espace peut être identifié à l'espace projectif réel . Et je me rappelle que c'était un collègue d'études qui m'a raconté cette preuve par la méthode de hand waving sous le soleil d'été dans une piscine plein air à Bonn!

Un bel énoncé géométrie et topologie
Le but de l'exercice est de montrer que et

Notations
Dans un premier temps — dont nous nous contentons ici — le symbole signifie simplement qu'il existe une bijection entre les ensembles concernés; c'est clairement une relation d'équivalence.
Comme d'habitude dénote l'espace projectif réel de dimension n, c'est-à-dire l'ensemble des droites vectorielles dans . Fixons aussi les notations pour trois sous-ensembles importants de :

• la boule
  
• la sphère
  
• l'hémisphère nord
  

Le bord de la boule est la sphère . Chaque point x sur ce bord possède un antipode, à savoir le point —x.
Si on ``recolle'' par identification des antipodes sur son bord, alors on obtient un nouvel ensemble que nous notons Ca, c'est du handwaving. De manière ensembliste on pourra écrire




Questions

1. Expliquer par des mots de quelles formes sont la boule et son bord dans les cas n=1,2,3.
2. Démontrer que
   
3. Démontrer que
   
4. Démontrer que
   
5. Démontrer que
   

Cliquez pour lire la Solution.

Le fait que

est une des premières choses qu'un étudiant apprend lorsqu'il étudie les nombres réels. Voici une démonstration de cette égalité.

On pose

X = 0,99999...

Alors on a l'égalité

10X = 9,99999...

dont on soustrait la première,

9X = 9,00000...

D'où X = 1.

Convaincant, n'est-ce pas ? Pour beaucoup de gens il s'agit d'une preuve — mais en réalité ça reste une tricherie car on ômet de réfléchir sur un certain nombre détails (comme par exemple à la signification rigoureuse de 0,99999... ou du produit 10 × 0,99999.... C'est un peu comme en topologie où il faut aussi faire comprendre au débutant que le fait que les boules ouvertes sont des ouverts nécessite une preuve.)
Or qui a bien compris le cours sur les nombres réels n'a pas besoin d'une preuve car l'égalité 0,999999... = 1 est une conséquence immédiate des diverses définitions possibles du corps des réels.

Voici la manière dont j'expliquerai l'égalité 1=0,99999... à quelqu'un qui ne connais pas grand chose en maths :

Une bien meilleure méthode

On pose X = 0,99999... et on part de

0 < 0,9 < 0,99 < 0,999 < 0, 9999 < ... < X

donc par multiplication par -1 les inégalités changent de sens,

0 > - 0,9 > - 0,99 > - 0,999 > - 0,9999 > ... > - X.

En ajoutant 1 à chaque membre de ces inégalités, on obtient

1 > 1 - 0,9 > 1 - 0,99 > 1 - 0,999 > 1 - 0,9999 > ... > 1 - X.

Autrement dit,

Ainsi la différence 1-X est plus petite que tout nombre de la forme 0,000...0001. C'est-à-dire 1-X ne peut pas être strictement positif. D'autre part 1-X n'est pas strictement négatif car X est n'est pas plus grand que 1. Cela prouve que 1-X = 0 , ou encore que X = 1.   CQFD

Avec un tel raisonnement, je crois, le non-initié comprend mieux les idées mathématiques qu'avec une tricherie qui fait seulement appel à ses habitudes de calcul.

Brenoms

D'ailleurs au lieu d'écrire une infinité de chiffres après la virgule on peut aussi écrire une infinité de chiffres devant. On obtient alors ce qu'on appelle un brenom (verlan de nombre). On additionne les brenoms en commencant par la droite. Ca donne des résultats bizarres comme par exemple

Plus de détails sur les brenoms dans ce bel article.

Constat : Lacunes dans le post-bac

Il y a quelques semaines, lors d'une colle en prépa MPSI (math sup) sur les développements limités, une étudiante était amenée à calculer la somme de trois fractions,

Voici comment elle s'y prenait (avec mon téléphone portable j'ai pris la photo du tableau) :

A éviter : dénominateur inutilement grand

Ce qui est gênant dans cette histoire c'est que cette étudiante n'est pas une mauvaise élève, mais apparemment au collège on ne lui a pas enseigné qu'il faut toujours privilégier le plus petit dénominateur commun pour additionner des fractions. En effet, cela évite des grands nombres difficiles à gérer ; le plus petit dénominateur commun n'est pas le produit 40x12x8 des trois dénominateurs ! Il fallait procéder comme suit :

On voit sur la première ligne ci-dessus que le plus petit dénominateur commun est car c'est le plus petit nombre qui contient les facteurs premiers qu'on obtient en décomposant chaque dénominateur. Autrement dit, c'est le plus petit commun multiple (PPCM) des trois dénominateurs.
On remarque d'ailleurs que je n'ai pas vraiment calculé ce dénominateur, je l'ai laissé sous forme de produit car à la fin cela permet de simplifier plus facilement...

Les nombres premiers ont disparu du collège

Comment se fait-il que certains élèves arrivent aujourd'hui en classes préparatoires de sciences et ne savent pas manipuler correctement des fractions ? La réponse est que la décomposition en produit de facteurs premiers est enseignée beaucoup trop tard et seulement à une partie des bacheliers scientifiques ; en effet, elle n'est plus au programme du collège mais seulement au programme de l'option mathématiques en terminale S.

Il fut une époque en France (pas lointaine et dans autres pays on y est toujours) où tout les enfants apprenaient à l'âge de dix ou onze ans de décomposer un nombre entier en facteurs premiers.

Valeurs pédagogiques et conceptuelles de cette décomposition :

• On apprend à décomposer un grand problème en petits problèmes, certaines composantes, les nombres premiers, étant irréductibles comme des atomes — ou les briques d'un jeu de légo.
• On trouve facilement le PGCD et le PPCM de deux, trois, quatre nombres ou plus à partir de leurs décompositions en nombres premiers. (En revanche, l'algorithme d'Euclid s'applique seulement à deux nombres à la fois.)
• Avec le PPCM on rencontre le concept de la réunion d'ensembles et la signification exacte du mot ou.
• Avec le PGCD on rencontre le concept de l'intersection et la signification exacte du mot et. Ce sont d'ailleurs des notions importantes en probabilités.
• On apprend sa table de multiplication...

On se demande vraiment pour quelle raison mystérieuse l'Inspection Générale a-t-elle ôté des programmes le concept simple et fondamental de la décomposition en nombres premiers ? Pour trouver le PGCD de deux nombres elle préconise l'algorithme d'Euclide ! Or cet algorithme est moins intuitif et son fonctionnement plus délicat à comprendre que la décomposition en nombres premiers. Son seul avantage est qu'il marche bien avec les très grands nombres — autrement dit, il n'a aucun intérêt pédagogique... Un jeune esprit a besoin d'apprendre des idées, des concepts et pas quelques recettes pour manipuler de nombres élevés, nombres qui n'ont aucun intérêt, ni pour lui ni pour nous autres mathématiciens (sauf quelques spécialistes en cryptographie, informatique ou théorie des nombres) ! D'abord un enfant doit maîtriser la manipulation des petits nombres, se faire une idée de leurs multiples, de leur diviseurs, et ce défi n'est point gagné à l'époque de la calculatrice...
Supprimer l'enseignement de la décomposition en facteurs premiers était donc une grave erreur et qui plus tard devient source de lacunes ; en plus c'était une occasion manquée de réviser les tables de multiplication.

Plus de vraies constructions géométriques au collège ?

Pour finir, voici deux exemples de l'enseignement actuel de la géométrie, extraits du manuel scolaire Transmath 6e (Nathan 2005). Dans les deux cas l'approximatif remplace une idée de construction simple et précis :

Bissection d'un angle.  On ne fait plus appel à la symétrie !

Bissectrice — méthode approximative avec pauvre valeur pédagogique

Encore une fois, une belle idée conceptuelle est remplacée par un procédé rapide qui n'a pas de valeur pédagogique, comme s'il s'agissait de faire croire aux enfants que plus tard dans la vie ils seraient amenés quotidiennement à diviser des angles ! Or ce qui est intéressant dans la division d'un angle par deux, ce n'est pas le résultat lui-même mais la manière dont on l'obtient, à savoir par un simple concept, la symétrie : si je fais la même construction des deux côtés d'un angle alors j'obtiens une figure symétrique.
Voici donc la vraie construction avec règle et compas telle qu'elle devrait être enseignée :

Bissectrice — la vraie construction intéressante

Parallèle à une droite.  En appliquant la bissection d'un angle au cas particulier de 180° on obtient une perpendiculaire ; et en faisant la même chose à cette perpendiculaire on trouve une parallèle. C'est une idée simple et facile à retenir. Mais qu'est-ce qu'on enseigne à la place ? La construction approximative que voici :

Parallèle passant par un point — méthode avec peu d'intérêt

Une petite erreur de calcul d'ordre 10¹⁰

On peut lire ici et là que la dette de l'état allemand a baissé considérablement en une seule journée. En fait, la comptabilité d'une banque allemande nationalisée en 2009 lors de crise financière a fait une "petite erreur", elle a pris pour une dette ce qui était en réalité un avoir ! Du coup l'état allemand a "gagné" d'un seul coup 55,5 milliards d'euros. C'était juste une petite faute de signe...

Ce "fait divers" du monde des finances sert comme introduction à ce billet sur le niveau de math des bacheliers français d'aujourd'hui, et plus particulièrement de ceux qui se destinent à des études scientifiques. Cette année j'enseigne, entre autres, à deux groupes de première année de licence en sciences (au total une cinquantaine d'étudiants). Puisque j'ai remarqué qu'un bon nombre des étudiants ne sait pas calculer avec des pourcentages et des puissances, j'ai consacré la première semaine à cela. Ce n'est pas vraiment prévu dans un programme qui porte sur les nombres complexes, l'algèbre linéaire, etc. Mais je suis de l'avis qu'un futur chimiste ou physicien doit savoir répondre à une question comme celle-ci : "Si la demi-vie d'une certaine substance radioactive est de 30 ans, quel est le pourcentage de diminution par an?"

Exemples de copies d'étudiants en première année d'université

Au mois d'octobre j'ai posé ce contrôle (45 minutes). Toutes les questions avaient été traitées en cours et TD, avec des énoncés identiques ou similaires (voir le polycopié du cours). Ce n'est donc pas surprenant qu'il y avait quelques très bonnes notes. Mais d'autre part le nombre de copies dépourvues de sens était tellement grand que cela m'inquiète. Avant de poursuivre la lecture de ce billet vous êtes priés de vous faire une idée vous-même en consultant quelques extraits scannés ici :

Quand on corrige de telles copies on est déjà heureux si le résultat est juste, même si l'écriture mathématique qui y conduit est fausse (comme dans cet exemple). Tout le monde fait des erreurs, moi aussi. C'est humain. Mais ici c'est le type d'erreur qui est inquiétant, et leur fréquence. Il y en a trop pour s'en amuser et pour parler de "florilège". Au total il y avait 48 copies (je n'ai pas tout scanné). Les 48 étudiants sont titulaires des bacs suivants: 39 bac S, 1 bac ES, 4 bac STL et 4 bac pro. La majorité des étudiants se destinent aux études de chimie.

Remarques et questions

1. Le bac d'aujourd'hui a-t-il encore une valeur? Si oui, laquelle?
2. Que dit la Cour des comptes? Il y a un grand gâchis d'argent public si l’Éducation Nationale ne parvient pas à enseigner correctement les opérations de bases +, -, × et ÷.
3. Après le bac la gabegie continue puisqu'à la fac on met tous dans le même panier, au lieu de créer des groupes de niveau. (Il est évident qu'avec des cours additionnels de soutien on n'arrive pas à combler ces lacunes du collège.) Pour donner une image : si une école de danse mettait dans un même cours ceux qui doivent apprendre les pas de base et ceux qui exécutent déjà les passes les plus compliquées, alors tous les élèves, les avancés et les débutants, demanderaient de se faire rembourser.
4. Est-ce le rôle de l'université d'enseigner les mathématiques de niveau collège?
5. Quel rôle jouent les conseillers d'orientation? Pourquoi ces étudiants sont-ils orientés vers les études scientifiques?
6. Les programmes scolaires en sciences établis par le ministère de l’Éducation Nationale sont-ils assez stimulants au niveau intellectuel pour attirer les meilleurs élèves vers les études scientifiques (et pas vers les études de droit, de commerce, gestion, etc.)?
7. Faut-il faire des contrôles pareils? Supposez vous êtes parent d'un étudiant qui a obtenu 20 points dans ce contrôle et vous voyez le sujet du contrôle, que feriez-vous? Puisque le niveau d'abstraction de ces exercices est adapté à un élève de troisième et pas à un étudiant en première année de faculté de sciences, vous lui conseilleriez certainement de changer d'établissement.
8. Peut-on enseigner le calcul dans C et dans Rⁿ à des personnes qui ne savent pas calculer dans R?
9. Que faut-il enseigner à un public tellement hétérogène?
10. D'après discussions avec des collègues partout en France je sais que ce constat ne concerne pas seulement mon université.
11. Faut-il en parler? Ce n'est pas politiquement correct d'affirmer que pas tous les bacheliers sont prêts pour des études supérieures. Si on veut la massification de l'enseignement il faut se donner des moyens efficaces. Faire les mêmes mathématiques pour tous et laisser passer tout le monde n'est apparemment pas la bonne méthode.
12. Cette très forte hétérogénéité qui empêche un enseignement efficace (et par suite la réussite des étudiants) n'est pas un phénomène qui ne concerne que la France (voir cet article en provenance des Pays-Bas). On l'attribue en général aux "nouvelles pédagogies". En Allemagne, on fait des constats similaires, pas dans les universités mais dans les FH (sorte de IUT). Lire par exemple cette lettre ouverte qu'un professeur de mathématiques de l'IUT de Berlin adresse à ses étudiants au premier semestre. Là-bas les bons étudiants des semestres supérieurs sont payés pour revoir le programme du collège et du lycée avec certains étudiants de première année repérés au début de l'année par un test sélectif (ils ont même écrit un bon polycopié).
13. Même en prépa le niveau est devenu très hétérogène. Les profs ne savent plus sur quelle base recruter tellement la signification des notes au lycée est devenue relative. Récemment en math sup dans un grand lycée parisien, je collais deux élèves ; l'une a très vite compris un exercice qui définit le logarithme complexe (une nouvelle notion pour elle), tandis que l'autre ne savait même pas dessiner la droite d'équation x+y=1 (elle y arrivait seulement après dix minutes, après m'avoir proposé trois faux dessins). Après on lira dans la presse que la prépa humilie les élèves (Bruno Sire)... mais si on y envoie quelqu'un qui n'a aucune base pour y réussir alors n'est-ce pas prévisible que ça crée des frustrations chez un élève qui ne comprend rien tout au long de la journée?

Encore quelques précisions sur ce contrôle :
La moyenne et la médiane des résultats se situent autour de 11, mais elles auraient été un ou deux points inférieures si j'avais corrigé avec une exigence normale.
Il s'agit d'un deuxième contrôle, sorte de rattrapage d'un contrôle très mal réussi par presque tous. En fait,a semaine avant j'avais fait un premier contrôle. Mon frère, matheux qui travaille dans l'industrie d'appareils médicaux, était chez moi en visite et m'a proposé de corriger les copies. Après vingt minutes il était découragé par les copies catastrophiques et disait: "Annule ce contrôle et rends les copies avec le corrigé. Ensuite tu leur dis que la semaine prochaine il y aura un autre contrôle similaire." Ensuite, c'est lui qui a conçu le nouveau sujet, plus simple, dont il est question dans ce billet. Les exercices étaient pratiquement les mêmes que ceux du premier contrôle, seulement encore plus élémentaires. Les étudiants qui n'ont pas réussi n'ont donc soit pas envie d'apprendre, soit ils n'ont pas les capacités de comprendre le corrigé.