/**
 * IntSqrt
 * 
 * Investigates the runtime of two implementations of integer square root
 * 
 * @author anied@cs.washington.edu
 * @version CSE373 au13
 * @date 2013-10-09
 */

import java.io.*;

public class IntSqrt {
	// Just an environmental variable to mark time
	static long time;
	
	// Runs a series of tests comparing the two algorithms
	public static void main(String[] args) {
		
		// Load a file to print results to
		PrintWriter out;
		try {
			out = new PrintWriter(new FileWriter("comparison.txt"));
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
			return;
		} 

		// Print headers to this comparison file
		out.printf("%s\t%s\t%s\t%s\t%s\n", "X", "Result 1", "Time 1", "Result 2", "Time 2");
		
		// Test both methods, getting their resultants and run times
//		for (int i = 1; i < 100; i *= Math.PI) {
		for (int i = 1; i <= Integer.MAX_VALUE; i *= Math.PI) {
			
			// Do the first intSqrt method
			tStart();
			int method1_result = intSqrt1(i);
			long method1_duration = duration()/1000;
			
			// Do the second intSqrt method
			tStart();
			int method2_result = intSqrt2(i);
			long method2_duration = duration()/1000;

			//Print this out to a file (and system for debugging)
			out.printf("%d\t%d\t%d\t%d\t%dn", i, method1_result, method1_duration, method2_result, method2_duration);
			System.out.printf("%d\t%d\t%d\t%d\t%d\n", i, method1_result, method1_duration, method2_result, method2_duration);
		}
		
		// Close the file, saving it
		out.close();
	}
	
	// Marks the start of a timing computation
	private static void tStart() {
		time = System.nanoTime();
	}
	
	// Returns the duration since the time start was set
	private static long duration() {
		return System.nanoTime() - time;
	}
	
	// The first implementation that files the integer square root of x, in O(n^0.5)
	public static int intSqrt1(int x) {
		int i = 1;
		while(i * i <= x)
			i++;
		return i - 1;
	}
	
	// The second implementation that finds the integer square root of x, in O(log(n))
	public static int intSqrt2(int x) {
		return search(x, x, x);
	}
	
	// Helper class for the second implementation, does a recursive search to find the integer square root
	private static int search(int x, int i, int jump) {
		//System.out.printf("%d\t%d\t%d\n", x, i, jump);
		
		// Is i squared less than or equal to x?
		if((long) i * i <= x) {
			
			// Is i+1 squared more than x?
			if((long) (i + 1) * (i + 1) > x) {
				
				// We found the integer square root! return it
				return i;
			} else {
				
				// We are too small, search upwards (but halve the space we are searching since the space has shrunk)
				jump /= 2;
				jump = Math.max(jump, 1);
				return search(x, i + jump, jump);
			}
		} else {
			
			// We are too large, search downwards (but halve the space we are searching since the space has shrunk)
			i = (int) ((double) i - (double) jump / 2.0);
			jump /= 2;
			jump = Math.max(jump, 1);
			return search(x, i, jump);
		}
	}
}