#!/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()