import java.io.IOException;


public class Multiply {
	
	static int[] q = new int[16];
	static int i;
    
	

	public static void main (String[] args) throws IOException{
		int a; int b;
		a = 16; b = 3;
		System.out.format("Multiply %4d * %4d = %4d = %4d %n", a,b,a*b,Mult(a,b) ); 
		System.out.format("Divide   %4d / %4d = %4d = %4d %n", a,b,a/b,Div(a,b) ); 
		a = 0; b = 5;
		System.out.format("Multiply %4d * %4d = %4d = %4d %n", a,b,a*b,Mult(a,b) ); 
		System.out.format("Divide   %4d / %4d = %4d = %4d %n", a,b,a/b,Div(a,b) ); 
		a = 4; b = 5;
		System.out.format("Multiply %4d * %4d = %4d = %4d %n", a,b,a*b,Mult(a,b) ); 
		System.out.format("Divide   %4d / %4d = %4d = %4d %n", a,b,a/b,Div(a,b) ); 
		a = -8; b = 5;
		System.out.format("Multiply %4d * %4d = %4d = %4d %n", a,b,a*b,Mult(a,b) ); 
		System.out.format("Divide   %4d / %4d = %4d = %4d %n", a,b,a/b,Div(a,b) ); 
		a = 8; b = -5;
		System.out.format("Multiply %4d * %4d = %4d = %4d %n", a,b,a*b,Mult(a,b) ); 
		System.out.format("Divide   %4d / %4d = %4d = %4d %n", a,b,a/b,Div(a,b) ); 
		a = -8; b = -5;
		System.out.format("Multiply %4d * %4d = %4d = %4d %n", a,b,a*b,Mult(a,b) ); 
		System.out.format("Divide   %4d / %4d = %4d = %4d %n", a,b,a/b,Div(a,b) ); 
		a = 34; b = 5;
		System.out.format("Multiply %4d * %4d = %4d = %4d %n", a,b,a*b,Mult(a,b) ); 
		System.out.format("Divide   %4d / %4d = %4d = %4d %n", a,b,a/b,Div(a,b) ); 
		a = 32767; b = 5;
		System.out.format("Multiply %4d * %4d = %4d = %4d %n", a,b,a*b,Mult(a,b) ); 
		System.out.format("Divide   %4d / %4d = %4d = %4d %n", a,b,a/b,Div(a,b) ); 
		a = 32767; b = 2;
		System.out.format("Multiply %4d * %4d = %4d = %4d %n", a,b,a*b,Mult(a,b) ); 
		System.out.format("Divide   %4d / %4d = %4d = %4d %n", a,b,a/b,Div(a,b) ); 
		
	}

		
	/***********************************************************************************************/
	/**Input v1,v2      (each <= 2^15-1 = 32767)                                                  **/
	/**Output: v4 = v1*v2                                                                         **/
	/**                                                                                           **/
	/**   JoshJava   Purpose                 MARIE                                                **/
	/**   --------   -------                 -----                                                **/
	/**       v1      Input                    x                                                  **/
	/**       v2      Input                    y                                                  **/
	/**       v4      Output                   z                                                  **/
	/**       a[]     a[i] = 2^i             Multa[]                                              **/
	/**       b[]     a[i] = 2^i * v2        Multb[]                                              **/
	/**       v3      index for a&b            i                                                  **/
	/**       v5      boolean sign flag       neg                                                 **/
	/**                                                                                           **/
	/**Written by Jeff    See notes for proof of correctness                                      **/
	/***********************************************************************************************/

	public static int Mult(int v1, int v2) {
		int[] a = new int[16];
		int[] b = new int[16];
		int v3,v4,v5;

		v5=0;
		if( v1<0 ) {
			v1 = 0-v1;
			v5=1;
		}
		a[0]=1;
		b[0]=v2;
		v3 = 0;
		while( a[v3]<=v1 ) {
			a[v3+1] = a[v3] + a[v3];
			b[v3+1] = b[v3] + b[v3];
			v3 = v3+1;		    
		}
		v4=0;
		while(v3>0) { 
			v3 = v3-1;
			if(a[v3]<=v1) {
				v1 = v1-a[v3];
				v4 = v4+b[v3];  
			}
		}
		if( v5==1 )  
			v4 = 0-v4;
		System.out.format("v1 = %4d v2 = %4d v3 = %4d v4 = %4d %n", v1,v2,v3,v4,v5 ); 

		return v4;
	}

	/***********************************************************************************************/
	/**Input v1,v2      (v1 <= 2^15-1 = 32767)                                                    **/
	/**Output: v4 = v1/v2   (Also computes the remainder)                                         **/
	/**  i.e. v4 and r   so that v1=v4*v2+r   and r in [0,v2)                                     **/ 
	/**                                                                                           **/
	/**   JoshJava   Purpose                 MARIE                                                **/
	/**   --------   -------                 -----                                                **/
	/**       v1      Input & output r         x                                                  **/
	/**       v2      Input                    y                                                  **/
	/**       v4      Output                   z                                                  **/
	/**       a[]     a[i] = 2^i             Multa[]                                              **/
	/**       b[]     a[i] = 2^i * v2        Multb[]                                              **/
	/**       v3      index for a&b            i                                                  **/
	/**       v5      boolean sign flag       neg                                                 **/
	/**                                                                                           **/
	/**Written by Jeff    See notes for proof of correctness                                      **/
	/***********************************************************************************************/

	public static int Div(int v1, int v2) {
		int[] a = new int[16];
		int[] b = new int[16];
		int v3,v4,v5;

		v5=0;
		if( v1<0 ) {
			v1 = 0-v1;
			v5=1;
		}
		if( v2<0 ) {
			v2 = 0-v2;
			v5=1-v5;
		}
		a[0]=1;
		b[0]=v2;
		v3 = 0;
		while( b[v3]<=v1 ) {
			a[v3+1] = a[v3] + a[v3];
			b[v3+1] = b[v3] + b[v3];
			v3 = v3+1;		    
		}
		v4=0;
		while(v3>0) { 
			v3 = v3-1;
			if(b[v3]<=v1) {
				v1 = v1-b[v3];
				v4 = v4+a[v3];  
			}
		}
		if( v5==1 )  
			v4 = 0-v4;
		System.out.format("v1 = %4d v2 = %4d v3 = %4d v4 = %4d %n", v1,v2,v3,v4,v5 ); 
		return v4;
	}

}