Les algorithmes de multiplication

(d'un nombre à plusieurs chiffres par un nombre à plusieurs chiffres)

a. À la française

     45
   x 19
   ----
    405     1) multiplier successivement le 1er nb par chaque chiffre du 2e nb
    45.
   ----
    855     2) additionner les resultats en tenant compte des decalages necessaires
Reste un problème si on ne dispose que d'un additionneur : comment faire 9 x 45 ?

b. À la russe

45| 19       1) écrire les 2 nbs chacun en haut d'une colonne
22| 38
11| 76 2) diviser successivement le nb de la colonne de gauche par 2
5|152
2|304 3) multiplier successivement le nb de la colonne de droite par 2
1|608
STOP=>STOP 4) s'arrêter lorsque 1 apparaît dans la colonne de gauche

45| 19      
22| 38 5) rayer dans la colonne de droite les nbs en face d'un nb pair de la colonne de gauche
11| 76
5|152
2|304
1|608
--------
855 6) additionner les nbs restant dans la colonne de droite

c. Avantages

d. Optimisation

19| 45       1) écrire le plus petit nb dans la colonne de gauche et l'autre dans celle de droite
9| 90
4|180
2|360
1|720
--------
855

e. Spécification

Cette étape de formalisation n'est pas évidente mais est nécessaire pour pouvoir ensuite passer à l'étape de traduction dans un langage de programmation. Cela peut donner ça : 
Soient A et B les 2 entiers positifs à multiplier.
[Obtenir leur valeur]
Soit R le résultat.

SI A est impair
  ALORS  initialiser R à la valeur de B
  SINON  initialiser R à 0
FINSI

TANTQUE A > 1 FAIRE
  - diviser A par 2 (sans reste)
  - multiplier B par 2
  - SI A est impair
      ALORS  ajouter B à R
    FINSI
FINTANTQUE
[Afficher le résultat R]
ou bien, de façon moins verbeuse : 
A,B,R : entiers naturels
Lire A
Lire B

SI reste(A/2)=1
  ALORS  R <- B
  SINON  R <- 0
FINSI

TANTQUE A > 1 FAIRE
  A <- A / 2
  B <- B * 2

  SI reste(A/2)=1
    ALORS  R <- R + B
  FINSI
FINTANTQUE

Afficher R

f. Traduction en Java (incomplète)


public class Russe
{
  // début de la partie principale
  {
    int A = /* récupération du premier nombre  */ ;
    int B = /* récupération du deuxihme nombre */ ;
    int R;
    
    if ( A > B ) { // echange
      R = B;
      B = A;
      A = R;
    } // if
    
    if ( A % 2 == 0 ) // liberté du programmeur
      R = 0;
    else
      R = B;

    while ( A > 1 )
    {
      A /= 2;
      B += B;
      if ( A%2 != 0 )
        R += B;
    }

    /* affichage sous la forme A * B = R */ ;
  } // fin de la partie principale
} // fin de la classe Russe

g. Traduction en Java (complète)

public class Russe
{
  public static void main( String[] inutilise )
  {
    java.util.Scanner clavier = new java.util.Scanner( System.in );
    System.out.print( "A ? " );
    int A = clavier.nextInt();
    System.out.print( "B ? " );
    int B = clavier.nextInt();
    int R;
    
    if ( A > B ) { // echange
      R = B;
      B = A;
      A = R;
    } // if

    if ( A % 2 == 1 ) // plus clair
      R = B;
    else
      R = 0;

    while ( A > 1 ) {
      A = A / 2;      // plus clair
      B = B * 2;      // plus clair
      if ( A%2 == 1 ) // plus clair
        R = R + B;    // plus clair
    } // while

    System.out.println( A + "*" + B + " = " + R );
  } // main(.)
} // Russe

h. Traduction en C++

#include <iostream.h>

int main( void )
{
  unsigned int A, B, R;

  cout << "A ? ";
  cin >> A;
  cout << "B ? ";
  cin >> B;

  if ( A > B ) { // echange
    R = B;
    B = A;
    A = R;
  } // if

  if ( A % 2 == 1 ) // plus clair
    R = B;
  else
    R = 0;

  while ( A > 1 ) {
    A = A / 2;      // plus clair
    B = B * 2;      // plus clair
    if ( A%2 == 1 ) // plus clair
      R = R + B;    // plus clair
  } // while

  cout << A << "*" << B << " = " << R << endl;

  return 0;
} // main()
Voyez-vous des ressemblances avec la version Java ?

i. Traduction en C

#include <stdio.h>

int main( void )
{
  unsigned int A, B, R;

  printf( "A ? " );
  scanf( "%d", &A );
  printf( "B ? " );
  scanf( "%d", &B );

  if ( A > B ) { /* echange */
    R = B;
    B = A;
    A = R;
  } /* if */

  if ( A % 2 == 1 ) /* plus clair */
    R = B;
  else
    R = 0;

  while ( A > 1 ) {
    A = A / 2;      /* plus clair */
    B = B * 2;      /* plus clair */
    if ( A%2 == 1 ) /* plus clair */
      R = R + B;    /* plus clair */
  } // while

  printf( "%d * %d = %d\n", A, B, R );

  return 0;
} /* main() */
Voyez-vous des ressemblances avec la version Java ou C++ ?