integer_roots.py

def integer_root(x):
  i = 0
  step = 1
  sum = 0
  while True:
    if sum + step > x: break
    sum += step
    step += 2
    i += 1
  return i

>>> for i in xrange(2**16):
...   r = math.sqrt(i)
...   t = integer_root(i)
...   if integer_root(i) != int(math.sqrt(i)): print i

def rounded_root(x):
  ir = integer_root(x)
  half_point = (ir << 1) + 1
  half_sqr = half_point * half_point
  target_point = x << 2
  if half_sqr < target_point: return ir+1
  else: return ir

>>> for i in xrange(2**16):
...   if rounded_root(i) != int(round(math.sqrt(i))): print i

integer_roots2.py

def integer_root(x):
  i = 0
  step = 1
  sum = step
  while sum <= x:
    i += 1
    step += 2
    sum += step
  return i

def test():
  for i in xrange(2**16):
    if integer_root(i) != int(math.sqrt(i)): print i

def rounded_root(x):
  ir = integer_root(x)
  if (ir*ir + ir) < x:
    ir += 1
  return ir

def test2():
  for i in xrange(2**16):
    if rounded_root(i) != int(round(math.sqrt(i))): print i