program Moltiplicazione_veloce;

{pre: n,m>=0 interi}
{post: calcolo e stampa di n*m ottenuto velocizzando l'iterazione
       della somma sulla base delle identita':
       
       x * 2y = (x+x) * y
       x * (2y+1) = (x+x) * y + x
 }
 
var n, m, p, q, r: integer;
 
begin
   readln(n,m);
   p:= n; q:= m; r:= 0;     {r + p*q = n*m}
   while q>0 do
       begin                
          if (q mod 2 = 1) then r:= r+p;
          p:= p+p;
          q:= q div 2
          {INVARIANTE: sia q' = q div 2; 
           se q = 2q'+1 allora  r + p*q = r + p + 2p*q'
           se q = 2q'   allora  r + p*q = r + 2p*q'}
       end;
   writeln(r)  {q = 0, dunque r = r + p*0 = n*m}
end.

NOTA: Rispetto agli algoritmi per calcolare la moltiplicazione iterando
      la somma presentati a lezione il 5 Ottobre, questo algoritmo fa
      *meno* somme.  Il numero di somme fatte dai primi due algoritmi e` m, 
      mentre questo algoritmo ne fa un numero proporzionale al log_2(m). 
      Si dice che il secondo algoritmo ha "complessita` minore in termini di 
      tempo" rispetto agli altri due.

Array: Esercizi proposti

Esercizi
	 1. Dato un array di interi, trovare il massimo intero contenuto 
	 nell'array (questo esercizio lo avete gia` visto in aula, ma vale 
	 la pena che lo riscriviate e lo decoriate con le asserzioni 
	 opportune).

	 2. Dato un array di interi, ordinarlo in ordine crescente.