Message on Whatsapp 8879355057 for DSA(OA + Interview) + Fullstack Dev Training + 1-1 Personalized Mentoring to get 10+LPA Job
0 like 0 dislike
711 views

I'm using Python's Chudnovsky technique to acquire the best estimate of pi I can. The square root of 640 320 is implied by this procedure.

If you happen to be interested in my code, here it is:

def sqrt(input_number,accuracy):
"""input_number is a list that represents a number we want to get the square root of.
For example, 12.56 would be [[1,2], [5,6], '+']"""
    
    if input_number[2]!="+":
        raise ValueError("Cannot find the real square root of a negative number: '"+pl(input_number)+"'")
    
"""Below creates the right number of elements for the required accuracy of the
square root"""
    if len(input_number[0])%2==1:
        input_number[0].insert(0,0)
        
    if len(input_number[1])<2*accuracy:
        for i in range(2*accuracy-len(input_number[1])):
            input_number[1].append(0)
            
    if len(input_number[1])%2==1:
        input_number[1].append(0)
    
# Below makes the pairs of digits required in the algorithm
    pairs=[[10*input_number[0][2*i]+input_number[0][2*i+1] for i in range(int(len(input_number[0])/2))],[10*input_number[1][2*i]+input_number[1][2*i+1] for i in range(int(len(input_number[1])/2))]]

    
"""Performs the algorithm, where c,x,y and p have the same definition
as on the Wikipedia link above. r is the remainder. pairs[0] is the pairs
of digits before the decimal dot, and pairs[1] represents the pairs of
digits after the dot. square_root is the computed square root of input_number."""
    p=0
    r=0
    square_root=[[],[],"+"]
    for i in range(len(pairs[0])):
        c=100*r+pairs[0][i]
        x=int((-20*p+(40*p**2+4*c)**.5)/2)
        y=20*p*x+x**2
        r=c-y
        p=10*p+x
        square_root[0].append(x)
    
    for i in range(len(pairs[1])):
        print(p,r,c)
        c=100*r+pairs[1][i]
        x=int((-20*p+(40*p**2+4*c)**.5)/2)
        y=20*p*x+x**2
        r=c-y
        p=10*p+x
        square_root[1].append(x)
    
    
    return square_root

After considerable investigation, I discovered a very efficient method for computing square roots; this method is known as "digit-by-digit calculation" (see here). Well, after attempting to implement it, I discovered that the first 13 decimals are right, but the following ones produce bizarre results (the next one is a 0 instead of a 4, then the next 'digit' is 128, then -1024...)

I attempted to test my function, but it appears to be working OK to me (besides, I would probably not find the correct first 13 decimals otherwise). As a result, my question is: are there any limitations to this digit-by-digit computation method?

 

in Algorithms and Problems by Expert (650 points) | 711 views

Please log in or register to answer this question.