# Square root of a base 10 positive integer, digit by digit [closed]

It is possible (Wikipedia reference) to compute the square root of any number in a digit by digit fashion using a simple (I had learned it in primary school) algorithm.

Challenge:

• read a positive integer from the user, in base 10, no error check;
• compute the square root of that integer using a digit-by-digit algorithm (either Wikipedia's or any alternative you may devise);
• display the result, in base 10, with 30 digits after the decimal point (the result must be truncated at the last digit displayed).

Restrictions:

• no use of builtin or library mathematical functions;
• only arithmetic operations on integers (addition, subtraction, multiplication, division and module).

Scores:

the shortest correct implementation will be the winner.

My reference implementation (Python3, 781 bytes) follows:

from math import sqrt

num = input('Give me an integer, ')
n = '0'+num if len(num)%2 else num
couples = [int(''.join(digit for digit in tup))
for tup in zip(*[iter(n)]*2)]

digits = []
n=0
rem = 0
for couple in couples:
target = rem*100 + couple
base = n*20
for i in range(11):
if (base+i)*i > target: break
i = i-1
digits.append(str(i))
n = 10*n+i
rem = target-(base+i)*i

digits.append('.')

for dec_digit in range(30):
target = rem*100 + 0
base = n*20
for i in range(11):
if (base+i)*i > target: break
i = i-1
digits.append(str(i))
n = 10*n+i
rem = target-(base+i)*i

print('From math.sqrt: sqrt(%s) = %r'%(num, sqrt(int(num))))
print('Digit by digit: sqrt(%s) = %s'%(num, ''.join(digits)))


Some test runs:

boffi@debian:~/.../tmp$python3 sqrt.py Give me an integer, 999901 From math.sqrt: sqrt(999901) = 999.9504987748144 Digit by digit: sqrt(999901) = 999.950498774814352559911780286530 boffi@debian:~/.../tmp$ python3 sqrt.py
Give me an integer, 4
From math.sqrt: sqrt(4) = 2.0
Digit by digit: sqrt(4) = 2.000000000000000000000000000000
boffi@debian:~/.../tmp\$

• Things to avoid when writing challenges: non-observable program requirements, such as requiring that answers use a specific algorithm. Nov 2, 2020 at 10:22
• You could make the algorithm observable by requiring that each step must be output. Nov 2, 2020 at 10:55
• @gboffi it's not so much a restriction but rather something to be avoided for practical reasons, for example if my language uses your algorithm for the sqrt function, simply calling this function would fit your requirements as an answer.. that's why it's preferable to rely on things one can observe. Also for golfing, it can be more interesting to let algorithms open as it can lead to surprising answers Nov 2, 2020 at 11:01
• You can do this by making it a series of both the partial $sqrt(a)$ and the remainder as a pair. Challenge to output the $n^{th}$ pair (or series up to that pair, or infinitely many) for a given input $(a,n)$. Answers may use another algo, but you can't control things to that extent anyway on this site. You may just be pleasantly surprised by some different approach. Nov 2, 2020 at 11:07
• I've VTCed this as unclear as you don't define the algorithm anywhere in the challenge. Nov 2, 2020 at 18:08

# Python 3, 156 bytes

Uses the algorithm suggested by OP, since this is a golf of the reference implementation.

K=input()
n=len(K)%2*'0'+K+'0'*60
R=N=0
while n:
a,b,*n=n;R=R*100+int(a+b);i=0;N*=20
while~i*~N<=R:i+=1;N+=1
print(i,end='.'[len(n)^60:]);R-=N*i;N=N+i>>1


Try it online!

• I do not think that it's a golf of a reference implementation, one can use whatever algorithm under the restrictions specified in the question. That said, +1 Nov 2, 2020 at 14:55
• @gboffi I guess my formulation was unclear. I meant that my specific answer is a golf of your reference implementation, not the challenge as a whole. All good ;)
– ovs
Nov 2, 2020 at 15:09