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.

La comatrice com(M) d'une matrice carré M d'ordre n est la matrice des cofacteurs, c'est-à-dire sa composante en (l,k) est fois le déterminant de la matrice qui s'obtient lorsqu'on ôte à M sa l-ème ligne et sa k-ème colonne.
Mais c'est surtout la transposée de la comatrice qui nous intéresse ; elle s'appele matrice complémentaire (en allemand Adjunkte, en anglais adjugate matrix) et on démontre dans tout cours d'algèbre linéaire qu'elle vérifie la propriété fondamentale :

Par conséquence si on travaille avec des coefficients dans un anneau A, alors la matrice M est inversible dans l'anneau matriciel à coefficients dans A si et seulement si le scalaire det(M) est inversible dans l'anneau A. Par exemple les matrices inversibles sur sont précisément celles dont le déterminant est 1 ou -1.

Exercice :  Démontrer que  com  est compatible avec la multiplication matricielle,

com(I) = I      et      com(MN) = com(M) com(N).

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...

Après une longue absence je viens de faire un peu le ménage dans les commentaires du billet précédent sur les exercices de la liste de Vladimir Arnol'd et je me suis rendu compte que PB y a posé un petit problème que toute le monde a oublié dans la déferlante de solutions (dues pour la plupart à JLT). Le voilà, dans un billet à lui tout seul !

Le nom du blog
peut faire penser à Math Ol’ Man, à mythomane, à math zéro man, à Mannomann !

Le logo du site
illustre la fameuse formule    qui réunit huit symboles et nombres fondamentaux en mathématiques :

• la relation d’égalité =
• l’addition +
• la multiplication
• le nombre 0 (élément neutre de l’addition)
• le nombre 1 (élément neutre de la multiplication)
• le nombre transcendant (pour calculer l'aire d’un cercle)
• le nombre transcendant e (pour la croissance exponentielle)
• le nombre imaginaire i (solution de l’équation ).

L’auteur du blog
c'est moi, , alias MathOMan.
J'ai étudié les mathématiques en Allemagne (Munich et Bonn) et en France (Nice et Paris) pour terminer avec une thèse de doctorat (directeur de thèse : Frédéric Pham, rapporteur : Mikhaïl Zaidenberg, rapporteur et président du jury : Pierre Cartier). D'ailleurs à cette occasion j'ai formulé une conjecture à l'apparence simple et toujours ouverte actuellement... peut-être elle vous tente !

J'ai aussi passé l'agrégation (année 2002 r.83) et, après avoir enseigné dans divers établissements de l'Education Nationale, j'ai donné des cours, TD et heures d'interrogation dans des écoles d'ingénieurs et classes préparatoires parisiennes ; aujourd'hui je suis professeur agrégé à l'Université de Versailles.

Avec d'autres auteurs j'ai écrit le livre Mathématiques L1 (publié chez Pearson Education) destiné aux étudiants en première année d'université ou classe prépa. (Lisez ici un chapitre extrait de ce manuel.)

Septembre 2008 a vu la naissance de ce blog éclectique sur divers sujets liés aux maths qui me passent par la tête. Pour des questions ou suggestions je vous prie de me contacter via ce formulaire.

Adresse professionnelle
Université de Versailles Saint Quentin
Département de Mathématiques — Bureau G-212
45 avenue des États-Unis
F-78035 Versailles
Tél.: +33 139254620

Un magma est un ensemble G muni d'une loi de composition interne ¤.
Si en plus cette loi est associative, c'est-à-dire (x¤y)¤z = x¤(y¤z) pour tous x,y,z dans G, alors on dit que (G,¤) est un demi-groupe.
Et si en plus il existe un élément neutre e dans G, c'est-à-dire e¤x = x¤e = x pour tout x dans G, alors on dit que (G,¤) est un monoïde.
Enfin, si chaque élément x de G possède un neutralisant x' dans G, c'est-à-dire x¤x' = x'¤x = e, alors on dit que (G,¤) est un groupe.

On dit aussi le symétrique de x pour l'élément neutralisant x' de x. Si la loi est notée par une addition on le note souvent -x (opposé) et si la loi est notée par une multiplication on le note souvent x^-1 (inverse).

Exemples :

• Considérons la loi de l'addition habituelle de nombres. Muni de cette loi l'ensemble des naturels strictements positifs N*={1,2,3,...} est un semi-groupe. Il manque l'élément neutre 0 ; on l'ajoute et on obtient le monoïde N={0,1,2,3,...}. Il manque les neutralisants (les opposés) -1, -2, -3, ... ; on les ajoute et on obtient le groupe des entiers Z={0,±1,±2,±3,...}.
• Considérons la loi de la multiplication habituelle de nombres. Muni de cette loi l'ensemble des naturels N est un monoïde, son élément neutre étant 1. Que faut-il ajouter ou enlever pour en faire un groupe ? D'abord on remarque que 0 multiplié avec tout nombre donne 0, donc jamais 1, autrement dit on ne pourra jamais trouver un neutralisant de 0 (on ne peut pas diviser par zéro...). Il faut donc enlever le 0, on trouve N*. Ensuite il faut ajouter les inverses : l'union de N* et de l'ensemble des 1/n où n parcourt N*, est-il un groupe ? Non, pas encore, car il faut aussi s'assurer que les produits restent dedans et donc on doit en fait ajouter toutes les fractions de la forme m/n avec m et n dans N*. On trouve le groupe multiplicatif Q*⁺ des rationnels strictement positifs.
  De même l'ensemble des nombres rationnels non nuls Q* est un groupe.
• Il existe des loi internes non-associatifs. L'ensemble Z muni de la soustraction est un magma (mais pas un demi-groupe). L'ensemble R³ muni du produit vectoriel
  (x₁, x₂, x₃) × (y₁, y₂, y₃) = (x₂y₃-x₃y₂, x₃y₁-x₁y₃, x₁y₂-x₂y₁)
  en est un autre.

Pour résumer, un groupe est un ensemble muni d'une loi interne associative, possédant un élément neutre et tel que chaque élément a un neutralisant. Il s'agit alors de vérifier ces trois axiomes pour montrer qu'un objet proposé est un groupe. Beaucoup d'exercices sont de ce type et très souvent ce sont de simples vérifications mécaniques, permettant au débutant de se familiariser avec la notion de groupe. La rédaction de la réponse à la question suivante m'a pris un peu plus de temps, à savoir toute la durée d'un examen que j'ai surveillé hier — pas terrible de réussir un seul exo pendant que les étudiants doivent en faire cinq ;-) mais évidemment cet exo ne faisait pas partie de l'examen...

Exercice : On définit x¤y := x(y²+1)^½+y(x²+1)^½. L'ensemble des réels muni de cette loi est-il un groupe ?

Toutes les solutions sont acceptées... en particulier celles utilisant la force brute du logiciel de calcul formel Maple car j'aimerais bien savoir si Maple arrive à faire ça. J'ai essayé de forcer Maple mais il ne voulait pas ; soit ça dépasse ses capacités, soit ça dépasse mes compétences maple-istiques.

Je me rappelle qu'une fois, en plein concert à la Philharmonie de Munich, le pianiste Alfred Brendel interrompit son jeu car le public qui toussait. Il se retournait vers la salle et disait : "Die Grundlage der Musik ist die Stille." Traduction : la base de la musique c'est le silence.

J'aimerais adapter cette phrase aux mathématiques : "La base des mathématiques c'est le calcul". Et je pense au calcul le plus simple, les opérations élémentaires qui devraient être maîtrisées par tous les citoyens d'un pays moderne (à l'exception de quelques rares personnes souffrant d'une sorte de dyslexie des nombres) : addition, soustraction, multiplication et division. Si les élèves ne savent plus calculer, le professeur devrait arrêter son cours, comme Alfred Brendel, et le reprendre plus tard...

Autrefois, grâce à la scolarisation, le savoir progressait d'une génération à l'autre
Dans cet extrait de film des années cinquante un représentant essaie en vain de dissuader Ma and Pa Kettle que 25 divisé par 5 donne 14.

Aujourd'hui c'est le récul: beaucoup de bachéliers ne savent plus calculer
Lorsque j'enseignais en deux classes de terminale ES dans un lycée en région parisienne, j'étais confronté à un problème majeur : le programme du baccalauréat porte sur les dérivées et les intégrales, les logarithmes et les exponentielles. Or la majorité de ces élèves en terminale ne connaissait pas les règles élémentaires de calcul, beaucoup confondaient l'addition avec la multiplication et la soustraction avec la division. Voici un florilège extraits de quelques copies de bacs blancs :

              

Tout ça pourrait faire rire si ce n'étaient que quelques cas isolés. Mais ce type d'erreurs n'est plus exceptionnel, il est devenu la règle (voir mes statistiques). Il semble qu'aujourd'hui il est impossible de demander à un élève en terminale d'effectuer un calcul élémentaire sans faire d'erreur. Le nombre d'élèves acceptés en première (même en section S) et qui ne connaissent pas la table de multiplication est légion.

Le roi est nu
Certains diront que tout cela n'a pas d'importance car les mathématiques n'interviennent que peu dans notre vie quotidienne et que d'autres facilités sont plus déterminantes pour bien réussir dans la vie. Peut-être. Je serais le dernier à exiger que tous mes co-citoyens connaissent les logarithmes et les intégrales. Mais ce qui me gêne beaucoup c'est que le calcul élémentaire n'est pas acquis et qu'en même temps on habitue les élèves à utiliser un langage de bois mathématique qui prétend qu'il y a une compréhension des objets impliqués tandis qu'au fond rien n'est compris. Sous un splendide manteau de termes savants (intégrales, limites, théorème des valeurs intermédiaires, etc.), le roi est nu ! C'est digne des Impostures intellectuelles à la Sokal-Bricmont...
Evidemment il est impossible, en dernière année de lycée, de rattraper avec des cours de soutien toutes ces bases manquées. Soit on fait les choses correctement dès le départ, soit on ne les fait pas, c'est-à-dire on élimine des programmes scolaires le calcul supérieur avec les fonctions.

Ci-dessous un dernier exemple qui me rend heureux et triste à la fois — triste car cet élève ne maîtrise pas du tout le programme du collège (règles de calcul avec les fractions), et heureux car il a appris ce que je lui enseignais en terminale (règles de dérivation). Mais en fin de compte, quelle est la valeur de ses connaissances en calcul différentiel s'il ne sait pas simplifier correctement la fraction qu'il obtient ?

La question posée était de dériver la fonction Voici sa réponse :

Il peut arriver en plein dimanche, quand tous les magasins sont fermés, qu'on doit effectuer un calcul avec la calculatrice, mais les piles de celle-ci sont vides. Pas de panique, il existe une

qui permet de faire les calculs de base et avec des fonctions trigonométriques, exponentielles et logarithmes. (Mais elle ne possède pas la possibilité de dessiner des graphes.)

Il bien connu (voir par exemple mon billet ou celui de Fabien sur les connaissances de élèves en terminale ou encore l'article de Michel Delord sur la maîtrise générale du calcul à l’entrée en sixième) que les exigences pour passer d'une classe à l'autre du cursus scolaire ont baissé. Les lacunes ainsi accumulées deviennent presque insurmontables, de manière qu'à la fin on est obligé de donner le bac assez facilement (voir par exemple cet excellent article sur la baisse de niveau du bac de physique ou ces réflexions sur la différence de niveau du bac entre la métroploe et la Réunion).

Quelles sont les conséquences pour les études supérieures que, selon les projets politiques, devraient entamer et réussir 50% des jeunes ? Voici un constat pratique. Recemment j'étais à la cafétéria d'une université parisienne. Sur le comptoir on avait posé cette affiche :

Vu à la fac : tableau de prix pour les nuls

D'abord je me suis dit que le CROUS de Paris propose un tarif dégressif pour des commandes groupées — mais non, il s'agit simplement d'un tableau nécessaire aux nombreux étudiants qui ne savent pas calculer quatre fois six... Le socle commun pour entrer en fac, finalement à quel niveau est-il ? Faut-il introduire les nombres négatifs pour le mesurer ?

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.

La langue des français ne finit pas par me surprendre. Ils ne faut pas toujours prendre à la lettre ce qu'ils disent. Par exemple il a quarante balais ne signifie pas qu'il s'agit d'un collectionneur d'outils de nettoyage, non mais quel manque d'imagination de la part de l'étranger que je suis, évidemment il fallait comprendre qu'on compte ici les années...

Mais encore plus bizarres sont les deux expressions suivantes qui inversent le sens. Contrairement à ce qu'on devrait croire t'inquiète ne signifie pas inquiète-toi mais ne t'inquiète pas ! Et fais gaffe ne veut pas dire fais une gaffe mais ne fais pas de gaffe !

J'avoue qu'en ma patrie, la Bavière, aussi il y a des illogismes. Par exemple, on peut entendre des bavarois dire i hob koa Mo net gsehn. Traduction en allemand correct : ich habe keinen Mann nicht gesehen. La double-négation kein/nicht en allemand fait une affirmation, mais pas chez les bavarois car ils aiment faire chose à part du reste de l'Allemagne.

En général, une négation en mathématiques et en langue est ce qu'on appelle une involution, c'est-à-dire une opération qui appliquée deux fois nous ramène au point de départ. Comme la multiplication avec -1. Si je multiplie deux fois par -1 je retrouve le nombre initial car -(-x)=x. Un autre exemple d'involution est une réflexion, par exemple par rapport à un plan : l'image miroir d'un image miroir est l'image initial.

Blague : A Krka lors de la conférence mondiale bi-annuelle des linguistes un chercheur fait un exposé détaillé sur les principes de la double-négation. Il explique alors qu'une double-négation est équivalente à une affirmation, mais qu'une double-affirmation ne peut jamais, mais vraiment jamais produire une négation. Après une heure son exposé compliqué en MindMaps et PowerPoint, avec des matrices, des équations comme et se termine, les scientifiques s'apprêtent à applaudir quand soudainement vient du dernier rang de l'amphi un Oui, oui...

Exercice : Un condamné est dans une pièce avec deux portes, chacune gardée par un gardien. Il sait que l'une des portes amène à la liberté et l'autre à la prison et que l'un des gardiens dit toujours la vérité tandis que l'autre ment toujours. Il a le droit de poser à un gardien au choix une seule question à réponse oui/non, puis il a le droit de sortir par la porte qu'il veut. Quelle question posera-t-il et quelle porte prendra-t-il ensuite ?

Remarque : Il existe une solution bien connue. Mais il existe aussi une autre qui ne suppose même pas que chaque gardien soit au courant qu'il existe une autre porte avec un autre gardien.