#!/usr/bin/python
"""I was thinking about square roots and this fast algorithm came to mind.
The `bsr` operation is an Intel 386 instruction that runs fairly fast.
I can't remember if this turned out to actually work...
"""
def sqrt(u):
if not u: return 0
n = bsr(u)
x = u >> -(-n >> 1)
x += 1 << n
x >>= 1
x += u//x
x >>= 1
return x
def bsr(u):
assert u > 0
i = 0
while u:
i += 1
u >>= 1
return i
def main():
for i in range(1, 2**16):
s = sqrt(i)
ssq = s**2
snsq = (s+1)**2
print i, s, "." if ssq <= i <= snsq else "###!"
if __name__ == '__main__':
main()