/* Programa per calcular la multiplicacio de dos
   nombres enters. Les uniques multiplicacions,
   divisions i moduls que es fan servir son per la
   constant 2.
*/

class mul {

  // Inicialitzem l'entrada i sortida de dades
  private static inout io = new inout(); 

  public static void main (String args[]) throws Exception {
    /* Pre-condicio: Els arguments del programa son dos nombres naturals
       Escriu el resultat de la multiplicacio
    */

    io.write ("Introdueix el dos nombres a multiplicar: ");
    io.writeln ("Multiplicacio: " + mul_iter(io.readint(),io.readint()));
  }

  // Versio iterativa

  public static int mul_iter (int a, int b) {
    // Precondicio: a>=0, b>=0
    // Retorna a*b

    int res = 0;

    // Anomenem A i B els valor inicials d'a i b
    // Invariant: A*B = a*b+res
    while (b > 0) {
      if (b%2 == 0) {
        a = a*2; b = b/2;
      } else {
        b = b-1; res = res + a;
      }
    }
    return res;
  }

  // Versio recursiva

  public static int mul_rec (int a, int b) {
    // Precondicio: a>=0, b>=0
    // Retorna a*b

    if (b == 0) return 0; // Cas senzill 
    else if (b%2 == 0) return mul_rec (a*2,b/2);
    else return a + mul_rec(a,b-1);
  }
}