-1
\$\begingroup\$

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$ 
\$\endgroup\$
21
  • 13
    \$\begingroup\$ Things to avoid when writing challenges: non-observable program requirements, such as requiring that answers use a specific algorithm. \$\endgroup\$ – Anders Kaseorg Nov 2 '20 at 10:22
  • 1
    \$\begingroup\$ You could make the algorithm observable by requiring that each step must be output. \$\endgroup\$ – xigoi Nov 2 '20 at 10:55
  • 2
    \$\begingroup\$ @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 \$\endgroup\$ – Kaddath Nov 2 '20 at 11:01
  • 6
    \$\begingroup\$ 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. \$\endgroup\$ – Noodle9 Nov 2 '20 at 11:07
  • 2
    \$\begingroup\$ I've VTCed this as unclear as you don't define the algorithm anywhere in the challenge. \$\endgroup\$ – Shaggy Nov 2 '20 at 18:08
1
\$\begingroup\$

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 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 \$\endgroup\$ – gboffi Nov 2 '20 at 14:55
  • 2
    \$\begingroup\$ @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 ;) \$\endgroup\$ – ovs Nov 2 '20 at 15:09

Not the answer you're looking for? Browse other questions tagged or ask your own question.