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.

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

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 :

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.

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

Définition (selon Wikipédia) : Un Gömböc (mot hongrois) est un corps homogène tridimensionnel convexe comportant un unique point stable et un unique point instable d'équilibre. Posé n'importe comment, il revient toujours à la même position.

La question de trouver un tel corps fût posée par le mathématicien russe Vladimir Arnold et était résolue l'année dernière par deux mathématiciens hongrois. La vidéo suivante montre que certaines tortues ont une carapace qui ressemble à un Gömböc.

Et pour finir avec la même espèce animal voici un très beau dessin connexe (dessiné d'un seul trait) par un artiste de Vanuatu (république en Océanie), spécialisé en dessins de sable. Il part d'une simple grille de référence, donc avec un cahier d'école on devrait pouvoir y arriver... Tout le monde peut s'y entraîner durant des leçons ou séminaires ennuyeux (-;

En 1991 le mathématicien russe Vladimir Arnol'd publia un

Il y vise ceux qu'il appelle les mathématiciens ignorants qui ont étudié les super-variétés ou les théorèmes de plongements mais ne savent pas résoudre des problèmes concrets et simples — ou, avec les mots de Pólya, ceux qui ressemblent à des singes qui sont toujours en haut d'un arbre :

A mathematician who can only generalise is like a monkey who can only climb up a tree, and a mathematician who can only specialise is like a monkey who can only climb down a tree. [...] A real mathematician must be able to generalise and specialise. — George Pólya

Selon Arnold le niveau de la culture mathématique baisse. Et il ne parle pas de la baisse du niveau du bac mais de celle du bac+5. (Or, comme le remarque Martin Andler ici, la question de la baisse de niveau est mal posée à cause de la massification de l'enseignement. Le nombre de mathématiciens en l'an 2000 est beaucoup plus grand que celui en 1900, en absolu et aussi en pourcentage de la population.)
Aux yeux d'Arnold je suis certainement un mathématicien très médiocre, voire ignorant ! De la même manière que je suis étonné quand un étudiant titulaire du bac S puisse avoir du mal à dériver sin(2x) ou à distinguer entre condition nécessaire et condition suffisante, Arnold serait choqué par le fait que je ne sais pas faire d'emblée sa liste de problèmes. En fait, si certains exercices de sa liste me sont très accessibles (par exemple les exercices 45 à 55), il y en a d'autres où je ne sais même pas par où commencer, comme par exemple le no. 72 (un problème de diffusion ?).

Pour Arnold cette collection ne contient pas de questions difficiles, mais seulement des questions qui forment le strict minimum essentiel — il serait alors intéressant de savoir combien un agrégé français moyen en résoudra en une semaine si on lui donne acces à wikipedia et à une bibliothèque de recherche. Quelle est votre estimation ? Plus ou moins que la moitié des problèmes ?

Si on regarde la liste des problèmes proposés on voit bien la préférence de l'auteur pour la géométrie et les équations différentielles. Il y a aussi un peu de topologie algébrique, mais on cherchera en vain des questions d'analyse ou algèbre pures, par exemple.

Vladimir Arnol'd est mort il y a trois semaines pas loin de chez moi, dans l'hôpital Saint-Antoine à Paris.

Mise-à-jour : JLT n'a pas chômé pendant le mois de juillet et a résolu la plupart des exercices !

Restent encore à faire: les no. 27, 41, 51, 58, 68, 69, 70, 73, 74.

Les solutions des exercices se trouvent dans les commentaires (pour déplier cliquer ci-dessous) mais ne sont pas dans l'ordre. Pour s'y retrouver utilisez la fonction find (Ctrl+F) de votre browser et recherchez le numéro de l'exercice par exemple sous la forme "no.54" ou "no.04".