#!/usr/bin/python

import math
import time
import psyco

psyco.full()

import funnelsort

# It appears that Newton's method of finding a root doesn't work for integer values.
# However, we can still compute the real root of x**3 - input_value == 0 to a low
# degree of precision, and then round up.
# However, this is still too slow, despite very low precision
def newtons_cube_root(input_value):
	#print 'starting', input_value
	float_input_value = float(input_value)
	trial_value = float_input_value / 3.0
	epsilon = 0.499
	one_minus_epsilon = 1 - epsilon
	while True:
		trial_value_squared = trial_value * trial_value
		trial_value_cubed = trial_value_squared * trial_value 
		if trial_value_cubed == float_input_value:
			#print 'ending exact'
			return int(trial_value)
		if abs(trial_value_cubed - float_input_value) < epsilon:
			#print 'ending close enough'
			return int(trial_value + one_minus_epsilon)
		new_trial_value = trial_value - (trial_value_cubed - float_input_value) / (3 * trial_value_squared)
		#print 'got to', new_trial_value, 'from', trial_value
		trial_value = new_trial_value

def float_pow_loop(n):
	one_third = 1.0/3.0
	for i in xrange(9, n):
		dummy = math.ceil(math.pow(i, one_third))

def float_star_star_loop(n):
	one_third = 1.0/3.0
	for i in xrange(9, n):
		dummy = math.ceil(i ** one_third)

def int_pow_loop(n):
	for i in xrange(9, n):
		dummy = funnelsort.int_cube_root_ceil(i)

def int_newtons_cube_root(n):
	for i in xrange(9, n):
		#print 'computing for', i
		#time.sleep(0.1)
		dummy = newtons_cube_root(i)

def time_it(fn, n):
	t0 = time.time()
	fn(n)
	t1 = time.time()
	return t1 - t0

print time_it(float_pow_loop, 2**20)
print time_it(float_star_star_loop, 2**20)
#print time_it(int_pow_loop, 2**20)
print time_it(int_newtons_cube_root, 2**20)