TLE in SQRROOT

[suteerth]

Here is my Python implementation of the Babylonian algorithm

Removed after got AC

Is it because its in need of a better implementation and perhaps a few optimizations or is there a better algorithm altogether ?

[numerix]

Is it because its in need of a better implementation and perhaps a few optimizations or is there a better algorithm altogether ?

Algorithm is good, initial value (estimate) is bad.
Generate some random cases (800 digits!) print out the single approximations while finding the root.
Then do some experimenting with the initial value and you'll get AC.

[suteerth]

Thanks

[mehmetinal]

I'm too having TLE, I used the initial guesses as described on wiki page. Can you have a look at the code below pls.

[bbone=Python,295]
from decimal import *

T = int(input())
while(T):
with localcontext() as ctx:
ctx.prec = 800

    Str = input()
    S =Decimal(Str)

    D = len(Str)

    if D % 2 == 0:
        n = int((D-2) / 2)
        s0 = '6'
        while(n):
            s0 += '0'
            n = n-1
        x0 = Decimal(s0)
    else:
        n = int((D-1) / 2)
        s0 = '2'
        while(n):
            s0 += '0'
            n = n-1
        x0 = Decimal(s0)

    x = x0
    x1 = x*x
            
    while(x1.to_integral() != S):
        x = (x + S / x) / 2
        x1 = x * x

    
    print (x.to_integral())

T = T-1

[/bbone]

[numerix]

The decimal module is too slow for that kind of implementation.
Read hendriks comment below the problemset carefully.