/* File: Multiply.java - March 2018 */
package l06;

/**
* Compute a*b using a recursive algorithm like that used
* for Power. A similar technique was used by the Egyptians
* see https://en.wikipedia.org/wiki/Ancient_Egyptian_multiplication
* and is also called "Russian peasant multiplication" though there seems
* to be no evidence that Russian peasants used it!
*
* The underlying idea is essentially long multiplication in binary. 
* 
* Also worth looking at is 
* https://en.wikipedia.org/wiki/Multiplication_algorithm
* which describes a lot of different multiplication algorithms including
* the ones actually used in hardware.
* 
* Sample usage: java l06.Multiply 3 21
*
* @author Michael Albert
*
*/

public class Multiply{

  static int calls = 0;

  public static void main(String[] args) {
    long a = Long.parseLong(args[0]);
    long b = Long.parseLong(args[1]);
    System.out.println(a + " * " + b + " = " + times(a,b));
    System.out.println("Calls required " + calls);
  }

  public static long times(long a, long b) {
    calls++;
    if (b == 0) return 0;
    long result = times(a+a, b/2);
    if (b % 2 == 1) {
      result += a;
    }
    return result;
  }

}