1 / 5
Apr 2010

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 ?

  • created

    Apr '10
  • last reply

    Sep '11
  • 4

    replies

  • 222

    views

  • 3

    users

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.

1 year later

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]

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

Suggested Topics

Want to read more? Browse other topics in Python or view latest topics.