Skip to content

Instantly share code, notes, and snippets.

@corehello
Last active September 29, 2021 14:44
Show Gist options
  • Save corehello/37afab6f0d3e91d8346e7a994d84462d to your computer and use it in GitHub Desktop.
Save corehello/37afab6f0d3e91d8346e7a994d84462d to your computer and use it in GitHub Desktop.
sqrt function(concept of proof) in python 3
def sqrt(n, p):
# any number can be writen as n = a*10 +b, where a >=0, b is 0~9
# for example 123 = 12 * 10 + 3
# so then any number N = (a*10 + b)^2 + remainer = a^2*100 + b*(b+20*a) + remainer
# then b*(b+20*a) <= N - a^2*100
# then we can calulate max b to match the expression
print("sqrt {} with {} precision is:".format(n, p))
if len(n) %2 != 0:
n = "0"*(2-len(n)%2) + n
splited_n = [n[i:i+2] for i in range(0,len(n),2)]
A,B,Remainer,Result = 0,0,0,""
def findb(N, a, b, remainer, result):
for j in range(0, 11):
c = remainer*100 + int(N)
if j*(20*a+j) > c:
b = j-1
remainer = c - (20*a+b)*b
a = 10*a + b
result = "{}{}".format(result, b)
break
return a,b,remainer,result
for i in splited_n:
A,B,Remainer,Result = findb(i, A, B, Remainer, Result)
if Remainer != 0:
Result = "{}.".format(Result)
for i in ["00" for i in range(p)]:
A,B,Remainer,Result = findb(i, A, B, Remainer, Result)
return Result,A,Remainer
@corehello
Copy link
Author

corehello commented Aug 21, 2021

for example:

sqrt("122", 30)
sqrt 122 with 30 precision is:
('11.045361017187260774210913843344',
 11045361017187260774210913843344,
 7004103155690974173862626897664)
1 | 1 22
   ------
    |100
    -----
  1 | 22
     ----
     | (20*1+1)*1
     ----
    0 | 1 00
       ------
       | 1 00 00
       ---------
    4 | (20*110+4)*4
       ------------
        |  11 84 00
        -----------
     5 | (20 * 1104 +5)*5
        -------------------
           | ..............

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment