// Arup Guha
// 4/5/07
// A Big Integer class that supports multiplication using two different
// algorithms: the standard one and a divide and conquer one.

import java.math.BigInteger;
import java.util.*;

public class BigInt {
	
	
	private int[] digits;
	
	// Creates a BigInt object from s. s must only have digits.
	public BigInt(String s) {
		digits = new int[s.length()];
		for (int i=0; i<digits.length; i++)
			digits[i] = (s.charAt(digits.length-1-i)-'0');
	}
	
	// Creates a BigInt object from num. num must only have ints from 0
	// to 9 and must be stored in reverse order, with the least significant
	// digit in index 0, the tens digit in index 1, etc.
	public BigInt(int[] num) {
		digits = new int[num.length];
		for (int i=0; i<digits.length; i++)
			digits[i] = num[i];
	}
	
	// Creates a random BigInt with numdigits digits. The leading digit is
	// NOT guaranteed to be zero.
	public BigInt(Random r, int numdigits) {
		digits = new int[numdigits];
		for (int i=0; i<digits.length; i++)
			digits[i] = Math.abs(r.nextInt()%10);
		
	}
	
	// Adds other to the current object and returns the result in a new BigInt.
	public BigInt add(BigInt other) {
		
		// Get the maximum size of the answer and allocate space.
		int longval = Math.max(this.digits.length,other.digits.length);
		int[] answer = new int[longval+1];
									
		int i=0, carry=0;
		
		// Loop through all of the places.
		while (i < longval) {
			
			// Add in the carry digit.
			int digit = carry;
			
			// Add the current digit in the current number if it exists.
			if (i < this.digits.length)
				digit += this.digits[i];
				
			// Do the same for other.
			if (i < other.digits.length)
				digit += other.digits[i];
				
			// Assign both the current digit answer and carry.
			carry = digit/10;
			digit = digit%10;
			answer[i] = digit;
			
			i++;
		}
		
		// Save the carry in the most significant digit.
		answer[i] = carry;
		
		// Return the answer.
		return new BigInt(answer);
		
	}
	
	// Returns the difference between the current object and other and assumes
	// that other is smaller than the current object.
	public BigInt sub(BigInt other) {
		
		// Allocate the maximum amount of space.
		int[] answer = new int[digits.length];
									
		int i=0, carry=0;
		
		// Loop through all the digits.
		while (i< digits.length) {
			
			// Add in the carry and the current digit of the current number.
			int digit = carry;
			digit += this.digits[i];
			
			// Subtract out the appropriate digit if necessary.
			if (i < other.digits.length)
				digit -= other.digits[i];
				
			// Change the current digit and the carry if necessary.
			if (digit < 0) {
				digit += 10;
				carry = -1;
			}
			
			// Must reset carry to 0 here just in case carry was -1 before.
			else
				carry = 0;
				
			// Set the digit.
			answer[i] = digit;
			i++;
		}
		
		// Return the answer.
		return new BigInt(answer);		
	}
	
	/****** FILL THIS IN ******/
	// Returns the product of the current object and onedigit. We assume that
	// onedigit is in between 0 and 9.
	public BigInt mult(int onedigit) {
		
		
	}
	
	// Returns the current object multiplied by 10^(spaces).
	public BigInt leftshift(int spaces) {
		
		// Allocate the necessary space.
		int[] answer = new int[digits.length+spaces];
		
		// Store the zeroes in the least significant digits.
		for (int i=0; i<spaces; i++)
			answer[i] = 0;
			
		// Copy the rest of the digits from the current object.
		for (int i=spaces; i<answer.length; i++)
			answer[i] = digits[i-spaces];
			
		// Return the answer.
		return new BigInt(answer);
	}
	
	
	/****** FILL THIS IN ******/
	// Returns the product of the current object and other utilizing the
	// standard grade school method.
	public BigInt mult(BigInt other) {
		
	}
	
	// Returns a String representation of the current object.
	public String toString() {
		
		// Determine the number of leading zeroes.
		int reallength = digits.length;
		while (reallength>1 && digits[reallength-1] == 0) 
			reallength--;
		
		// Concatenate all the rest of the digits in the correct order,
		String ans = "";
		for (int i=0; i<reallength; i++) {
			
			char[] dig = new char[1];
			dig[0] = (char)(digits[i]+'0');
			String tmp = new String(dig);
			
			// We're placing this digit to the back of the String ans to 
			// reverse the order of the digits.
			ans = tmp + ans;	
		}
		
		return ans;
	}
	
	// Returns a new BigInt that is the right-half of the current object.
	public BigInt righthalf() {
		
		// Allocate the correct space and fill up the appropriate digits.
		int[] ans = new int[digits.length/2];
		for (int i=0; i<ans.length; i++)
			ans[i] = digits[i];
		return new BigInt(ans);		
	}
	
	// Returns a new BigInt that is the left-half of the current object.
	public BigInt lefthalf() {
		
		// Allocate the correct space and fill up the appropriate digits.
		int[] ans = new int[digits.length-digits.length/2];
		for (int i=0; i<ans.length; i++)
			ans[i] = digits[i+digits.length/2];	
		return new BigInt(ans);
	}
	
	/****** FILL THIS IN ******/
	// Uses a Divide and Conquer method to find the product of the current
	// object and other.
	// Only works if other is the same number of digits as this.
	public BigInt multiply(BigInt other) {
			
	}
	
	public static void main(String[] args) {
		
		// Create to large BigInts.
		Random r = new Random();
		BigInt one = new BigInt(r,10000);
		BigInt two = new BigInt(r,10000);
		
		// Try both of the methods above.
		long start = System.currentTimeMillis();
		BigInt three = one.multiply(two);
		long endfast = System.currentTimeMillis();
		
		// This is commented out because it's slow. Put this back in to
		// see that!
		//BigInt four = one.mult(two);
		//long endslow = System.currentTimeMillis();
		
		// Create the same BigIntegers as we tested our BigInt on.
		BigInteger checkone = new BigInteger(one.toString());
		BigInteger checktwo = new BigInteger(two.toString());
		
		// Call Java's method.
		long startjava = System.currentTimeMillis();
		BigInteger checkthree = checkone.multiply(checktwo);
		long endjava = System.currentTimeMillis();
		
		// These are the string representations of the answers.
		String x = three.toString();
		String y = checkthree.toString();
		//String z = four.toString();
		
		// Check if our Divide and Conquer Algorithm Worked.
		if (x.equals(y))
			System.out.println("Div+Conq Worked");
		else
			System.out.println("Div+Conq Wrong");
		
		
		// Check if our Standard Algorithm Worked.
		/*	
		if (y.equals(z))
			System.out.println("Standard Worked");
		else
			System.out.println("Standard Wrong");
		*/
			
		// Print out how long each took.
		System.out.println("Div+Conq took "+(endfast-start));
		//System.out.println("Regular took "+(endslow-endfast));
		System.out.println("Java took "+(endjava-startjava));
			
	}
}