The Babylonian method is very simple to implement and converges much faster than the binary search approach referenced by @bwCA.
>>> def babysqrt2(x,tolerance):
... guess=x/2.0
... while True:
... print "guess = ", guess
... if -tolerance <= (guess*guess)-x < tolerance:
... return guess
... guess = (guess + x/guess)/2
...
>>> babysqrt2(1000,0.00001)
guess = 500.0
guess = 251.0
guess = 127.492031873
guess = 67.6678296579
guess = 41.2229503947
guess = 32.7406409949
guess = 31.6418602354
guess = 31.6227823565
guess = 31.6227766017
31.622776601684315
>>> babysqrt2(1000,0.000001)
guess = 500.0
guess = 251.0
guess = 127.492031873
guess = 67.6678296579
guess = 41.2229503947
guess = 32.7406409949
guess = 31.6418602354
guess = 31.6227823565
guess = 31.6227766017
31.622776601684315
>>> babysqrt2(2,0.001)
guess = 1.0
guess = 1.5
guess = 1.41666666667
guess = 1.41421568627
1.4142156862745097
>>> babysqrt2(2,0.00001)
guess = 1.0
guess = 1.5
guess = 1.41666666667
guess = 1.41421568627
1.4142156862745097
Compare with the hi/lo method:
>>> print sqrt(100)
entering iter_sqrt( 100 , 100 , 0 )
entering iter_sqrt( 100 , 50.0 , 0 )
entering iter_sqrt( 100 , 25.0 , 0 )
entering iter_sqrt( 100 , 12.5 , 0 )
entering iter_sqrt( 100 , 12.5 , 6.25 )
entering iter_sqrt( 100 , 12.5 , 9.375 )
entering iter_sqrt( 100 , 10.9375 , 9.375 )
entering iter_sqrt( 100 , 10.15625 , 9.375 )
entering iter_sqrt( 100 , 10.15625 , 9.765625 )
entering iter_sqrt( 100 , 10.15625 , 9.9609375 )
entering iter_sqrt( 100 , 10.05859375 , 9.9609375 )
entering iter_sqrt( 100 , 10.009765625 , 9.9609375 )
entering iter_sqrt( 100 , 10.009765625 , 9.9853515625 )
entering iter_sqrt( 100 , 10.009765625 , 9.99755859375 )
entering iter_sqrt( 100 , 10.0036621094 , 9.99755859375 )
entering iter_sqrt( 100 , 10.0006103516 , 9.99755859375 )
entering iter_sqrt( 100 , 10.0006103516 , 9.99908447266 )
entering iter_sqrt( 100 , 10.0006103516 , 9.99984741211 )
entering iter_sqrt( 100 , 10.0002288818 , 9.99984741211 )
10.000038147
>>> print sqrt(2)
entering iter_sqrt( 2 , 2 , 0 )
entering iter_sqrt( 2 , 2 , 1.0 )
entering iter_sqrt( 2 , 1.5 , 1.0 )
entering iter_sqrt( 2 , 1.5 , 1.25 )
entering iter_sqrt( 2 , 1.5 , 1.375 )
entering iter_sqrt( 2 , 1.4375 , 1.375 )
entering iter_sqrt( 2 , 1.4375 , 1.40625 )
entering iter_sqrt( 2 , 1.421875 , 1.40625 )
1.4140625