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.

Il y a dix ans, pour sortir un peu des maths pûres, je travaillais pendant quelques semaines dans la forêt guyanaise sur le tournage d'un film documentaire scientifique sur les fourmis. Le monde des insectes sociaux (fourmis, abeilles, guêpes, termites) est fascinant, pas seulement du point de vue de la biologie, mais aussi du point de vue mathématique. A part les questions de génétique (forcément liées à la combinatoire et aux probabilités), il y a aussi beaucoup de théorie de jeux dans le comportment de ces "automates vivants", ainsi que de la théorie des graphes et même des algorithmes de fourmis.

A tous ceux qui veulent en savoir davantage je recommande vivement (comme cadeau de Noël?) le livre de vulgarisation scientifique Voyage chez fourmis de Bert Hölldobler et Edward O. Wilson ainsi que Le gène égoïste de Richard Dawkins.

Lors du tournage du film j'avais le temps d'observer un peu les fourmis et de calculer certaines distances qu'elles parcourent périodiquement. Voici un joli petit problème sur les fourmis.

Devinette
Une colonie de 101 fourmis se trouve sur une fine tige de longueur 100cm. Chaque fourmi se déplace à la vitesse de 1cm par seconde dans un sens fixe, mais si deux fourmis se rencontrent elles changent de sens. Lorsqu'une fourmi arrive à l'un des deux bouts de la tige elle tombe.

Est-ce que toute la colonie va disparaître de la tige? Si oui, après combien de temps?

Réponse
A vous de chercher! Je la divulguerai prochainement...

En attendant, je vous invite à regarder un petit film amusant en Super8 que j'ai réalisé après le dernier jour du tournage officiel et auquel les auteurs du film sur les fourmis ont gracieusement participé en tant qu'acteurs.

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

Après quelques billets de maths, il est temps de polémiser un peu ;-) Voici un texte écrit par un collègue que j'ai rencontré recemment, Bertrand Rungaldier, professeur en PCSI au Lycée Janson-de-Sailly à Paris. On pourra le lire comme complément à l'article sur la désaffection des jeunes pour les filières scientifiques de Fabien Besnard.

Les Etats généraux des Mathématiques. Le constat est alarmant. Alors que le besoin de mathématiciens n’a jamais été aussi important, la France manque de mathématiciens ; pourquoi donc les jeunes scientifiques délaissent-ils les sciences dures et notamment les Mathématiques ? Ah, voilà une question qu’elle est bonne !!
Pour ce qui est de se poser la question, gageons qu’on va se la poser, mais pour ce qui est d’apporter un semblant de réponse…
Car les doctes qui se réunissent vont prendre soin de se mettre un bandeau noir sur les yeux, de se boucher les oreilles avec de la cire et de chausser des lunettes équipées de prismes pour ne surtout pas voir la réalité en face.

Car bien avant que de se poser la question « Pourquoi les jeunes scientifiques français rechignent-ils à devenir mathématicien ? » il conviendrait de se poser à soi même la simple question « Pourquoi moi-même, j’ai choisi de faire des Mathématiques ? »
Je fais ici le pari qu’on ne posera jamais cette question car si la question fâche, la réponse tue ! S’imagine-t-on vraiment que la réponse pourrait être « parce que les mathématiques c’est utile à la vie ! » ? Peuvent-ils vraiment croire une seule seconde qu’on choisit de se lancer dans une discipline de l’extrême, et les mathématiques pures en sont une à leur façon, parce que « ça sert » ? Ou parce qu’en tant que lycéen démocrate j’ai choisi de faire des Mathématiques citoyennes et de lutter contre les inégalités de convexité ou des accroissements finis !

NON ! On se lance dans de pareilles études aussi difficiles et sélectives parce qu’on a été ébloui, émerveillé par un cours, un professeur ou un devoir en classe ou à la maison. Parce qu’à cette occasion on a vu un feu d’artifice intellectuel de concepts et de raisonnements et qu’on a été frappé par la grâce comme Saül ou par une flèche de Cupidon mais en tous cas parce qu’on a trouvé ça beau.
Alors posons maintenant la question qui tue : Croyez vous vraiment messieurs les doctes que les programmes actuels aient de quoi toucher, émerveiller et éveiller des vocations ? Cela fait vingt ans que les programmes de lycée et de collège sont vidés de leur contenus pour, disent les Inspecteurs Généraux, inciter les élèves à « faire des études scientifiques ». Et depuis vingt ans que c’est le contraire qui se produit. Plus les programmes se vident et moins il y a d’élèves voulant devenir scientifique.

Tandis que nous abaissons, que dis-je, que nous aplatissons le niveau d’exigence l’Inde ou la Chine elles augmentent le leur. Et plus elles l’augmentent et plus il y a de candidats. Etonnant non ?
Dans les années 1970-80 il y avait à peine 25000 bacheliers C par an dont presque 10.000 se lançait dans les sciences dures. Aujourd’hui ce ne sont pas moins de 125.000 à 130.000 bacheliers déclarés « scientifiques » qui quittent le lycée, et alors… les amphithéâtres de Mathématiques se vident peu à peu. Voilà la réalité.
Tant qu’à faire, pourquoi ne pas organiser une grande « tombola scientifique » : « Devenez scientifique en participant à notre jeux concours ! » On pourrait ainsi décréter 200.000 jeunes gens scientifiques chaque année. Et en moins de 10 ans il n’y aurait plus du tout d’étudiants en sciences et cela permettrait de faire des économies.

On ne devient pas alpiniste en contemplant les steppes d’Asie centrales. On devient alpiniste en regardant des sommets couronnés de blanc avec le ciel bleu sombre au dessus et le soleil et qu’on se dit « Je veux monter la haut ! ». On ne devient pas pilote de catamarans de course au large en faisant du pédalo sur un étang « parce que c’est ludique », mais en regardant la mer, déchaînée, et qu’on est aspiré par l’immensité des forces de la nature.
On ne devient pas virtuose parce qu’on a téléchargé « Au clair de la lune » joué au tam-tam sur son portable, mais parce qu’on a écouté Czyfra jouer les Etudes d’Execution Transcendantes de Liszt ou Evgeni Kissin jouer l’Appassionata ou Glenn Gould jouer des partitas de Bach. Voilà qui motive et qui peut éveiller des vocations.

Alors quand on ouvre un livre de TS de mathématiques avec ses 450 pages de « Pour prendre un bon départ », « Un peu d’histoire », « Ce qu’il faut retenir », « L’Essentiel du cours », « Travaux Dirigés », « C’est nouveau au BAC », « A quoi ça sert ? », « Exercice corrigés », « Comment utiliser le cours », « Problèmes corrigés », « Réfléchissons », « Approfondir », et pourquoi pas « Mickey et les intégrales » ou « relie les points et devine où est caché Pluto » ; où l’on découvre par hasard trois pages d’un pseudo cours avec de vagues recettes sans la moindre démonstration rigoureuse (ça ne sert à rien or « Les Maths c’est utile ! »), sans définitions précises (parce que c’est trop abstrait), sans concept (parce que c’est « élitiste »), tout cela dans un déluge de bleu, de vert, de rouge, de jaune de photos et de dessins et bientôt sans doute des pages qui clignoteront et qui feront « pin-pon » quand on les ouvre ou bien qui téléchargeront un tube sur internet parce que « c’est plus motivant pour les élèves »… alors, si l’on a réussi à se retenir de pleurer on se dit qu’à moins d’avoir des parents eux-mêmes mathématiciens, un adolescent aujourd’hui n’a aucune chance d’être un jour un tant soit peu émerveillé par les Mathématiques.

450 pages de livre et misérablement 50 pages de cours quand j’avais 1200 pages de livre et 600 pages de cours le tout avec seulement 3 heures de mathématiques en plus. 50% d’horaire en plus mais dix fois plus de connaissance. Il y avait de quoi être motivé. Et quand on me rétorque « toi, oui mais moi je n’aimais pas vraiment les maths » je réponds « alors que faisais-tu en TC ? » et là silence !

Pourquoi moi, ai-je voulu faire des mathématiques ? Parce que j’ai été ébloui par un devoir sur le groupe des fonctions arithmétiques, parce qu’en fin de premier trimestre de Maths Sup j’ai pu m’acheter le livre Théorie algébrique des nombres de Pierre Samuel. Et Pourquoi ? Croyez-vous que j’avais l’âme d’un matheux ? Peut-être… mais à coup sûr parce que j’avais des connaissances qui me permettaient de mettre le nez dedans et de trouver ça beau : extension de corps, anneau, quotient, idéal premier, maximal, anneau quotient, factorisation canonique j’en passe et des meilleurs. Toutes ces connaissances qui m’ont motivé qui m’ont ébloui (moi et sans nulle doute bien d’autres) un élève de prépa rentre aujourd’hui rue d’Ulm sans en avoir la moindre trace !

Comment s’étonner qu’il n’y ait plus d’étudiant en géométrie algébrique, LA spécialité française, alors qu’un étudiant arrive en L3 sans jamais avoir vu autre chose comme espace topologique que des « parties d’un evn » tandis que de mon coté, après deux mois de Maths Sup, j’avais déjà vu des points ouverts et le fait qu’un espace était séparé si et seulement si sa diagonale est fermée.
Croit-on que l’on va inciter des étudiants à faire de la cohomologie avec un programme d’algèbre linéaire qui stipule « l’accent devra être mis sur le calcul matriciel », chose utile mais tellement « bovine » qu’elle est justement utilisée dans les ordinateurs. Doit-on rappeler aux zigés qu’un cerveau n’est pas fait en silicium et que ce qui sert à l’un est très précisément ce qui démotive l’autre ?

La vacuité des programmes de Mathématiques de lycée n’a d’égale que celle du grand vide de la constellation d’Eridan. Les sinistres crétins de l’Inspection Générale ont été jusqu’à vouloir supprimer toute la géométrie dans les nouveaux programmes de seconde. Il a fallu un tollé de la part des professeurs pour que le reste d’un embryon de géométrie soit maintenu.
« Les cons, ça osent tout, c’est même à ça qu’on les reconnaît » dit le film, et bien on a osé inscrire au programme de PCSI l’algorithme d’Euclide des polynômes (qui est une horreur) alors que les notions de PGCD et de polynôme premiers entre eux (à quoi sert précisément cet algorithme) sont hors programme ! Bref, il y a à l’heure actuelle au programme un algorithme compliqué dont le résultat est hors programme. Bref, un algorithme qui officiellement ne sert à rien !

Les programmes sont aujourd’hui tellement stupides, tellement vides, tellement insipides que Laurent Lafforgue s’il les avait eu serait sans doute entré à Solesmes pour pouvoir fréquenter un peu l’infini qu’il a pu trouver dans les EGA et dans Grothendieck.
Il faut parler un minimum l’allemand si l’on veut apprécier celui de Goethe. On pourra faire tous les films et toutes les animations sur le sage de Weimar ce n’est pas comme cela qu’on motivera réellement des étudiants. Oh certes ils diront « c’était très intéressant » mais c’en restera là. Ce n’est pas ainsi qu’on les motivera pour étudier le Faust. C’est plutôt en leur donnant un minimum de vraies connaissances.

Tous ces efforts de vulgarisations sont certes louables mais force est de constater qu’il ne fonctionnent pas et cela parce que le niveau de connaissance est tellement loin du minimum que cela fait le même effet à un élève que si on lui récitait le Mahabaratha en sanscrit. On pourrait tout aussi bien lancer une campagne de promotion avec des pom-pom girl parcourant les TS de France en scandant « Vive les maths, vive les maths, Oui, oui, oui ! » ou encore « On est foot des Maths » avec Zinedine Zidane. Cela n’y changera rien. On donne le goût de quelque chose en la faisant goûter...
A vouloir à n’importe quel prix et par pure démagogie, faire des « scientifiques » qui n’en sont pas, on a écœuré tous ceux qui étaient susceptibles de le devenir. Oh certes il restera bien quelques fils et filles de mathématiciens qui seront brillantissimes. Ce seront les arbres qui cachent le désert. La France aura peut-être encore quelques médailles Fields car celles-ci récompensent des gens d’exception, hasards de la génétiques. Mais derrière ces arbres il n’y aura plus que des dunes de sable très mou.

Lorsque parfois l’on s’exclame « mais pourquoi supprimer tel ou tel pan de programme susceptible de motiver des élèves » la réponse est toujours : « ça ne sert à rien et ceux qui aiment les mathématiques pourront apprendre cela plus tard ». Et bien non ! Ils ne l’apprennent pas ni plus tard ni jamais parce qu’ils n’éprouvent aucune envie d’étudier des choses aussi ennuyeuses et qu’ils ignorent même qu’il puisse exister des choses passionnantes.
Le cas des Mathématiques est à ce titre particulier car la matière ne peut pas se vulgariser sans se livrer à une dénaturation telle qu’il ne reste rien de la chose même. Or l’absence de connaissance n’est pas une motivation pour en acquérir. Pour motiver des adolescents à se lancer dans les Mathématioques il faudrait des programme de Lycée difficile, abstrait sélectif. Précisément ce que font Chinois, Indiens, Russes qui oh miracle ! ont des étudiants à ne savoir où les mettre.

Ci gît l’Ecole Mathématiques Française, trahie et exterminée par un Ministère qui aurait dû la défendre.

(Auteur : Bertrand Rungaldier, professeur de prépa au Lycée Janson-de-Sailly)