# Find the first n digits of the square root of a number

Given two integers m and n, return the first m digits of sqrt(n), with the decimal point. They will be given with a space in between.

You only have to produce m digits: so if m=5, n=500, then the output will be 22.360, not 22.36067.

Do not use anything that will increase the precision of any operation.

Test Cases:
20 99 -> 9.9498743710661995473
15 12345678 -> 3513.64170057221
16 256 -> 16.00000000000000
2 10000 -> 10

Shortest code wins.

• Looks like your second test case gives the square root of 12345678 not 1234567 (which is 1111.11070555548 according to my J program). – Gareth Aug 4 '12 at 23:26
• When you say 'do not use anything that will increase the precision of floating points.' does that disqualify arbitrary precision languages (such as bc) – Matt Aug 4 '12 at 23:32
• @Gareth: Yeah, it's probably 12345678, I probably copied it from WA wrong. – beary605 Aug 4 '12 at 23:53
• @Matt: No, as long as you don't use any command that explicitly sets the precision. – beary605 Aug 4 '12 at 23:55
• What should 2 10000 output? 100? – Inkbug Aug 5 '12 at 6:54

## Python, 143 chars

m,n=map(int,raw_input().split())
d=10**m
n*=d*d
a=0
b=n
while a<b-1:c=(a+b)/2;a,b=[[c,b],[a,c]][c*c>n]
print('%d.%0*d'%(a/d,m,a%d))[:m+(a/d<d)]


Computes the answer by multiplying n by 10^2m, doing an integer square root (using binary search), then "dividing" the result by 10^m.

• This doesn't work for large perfect squares that request small numbers of digits. ex: m=2 n=1000000 will print 100 instead of 10 – Matt Aug 5 '12 at 18:54
• @Matt: fixed... – Keith Randall Aug 6 '12 at 22:55

# Mathematica 66272 240 chars

New approach

This uses the same, reasonably efficient (59 chars), method for obtaining the smallest useful convergent of Sqrt[n]. It takes a slightly different approach for dividing the numerator by the denominator, accurate to m places.

t = ToString; q = QuotientRemainder;
w = FixedPoint[(# + n/# )/2 &, 1, SameTest -> (Abs[#1 - #2] < 10^(-m) &)];
r = q[Numerator@w, k = Denominator@w];
h[{c_, d_, e_}] := {Append[c, q[d, e][[1]]], 10 q[d, k][[2]], k};
t@r[[1]] <> "." <> t@FromDigits@Nest[h, {{}, 10 r[[2]], k}, m][[1]]


Example: Find the Square root of 5 accurate to 18 places

n=5; m=18;
<run the above code>

(* out *)
"2.236067977499789696"


By the way, the convergent, w, for the above case is given below.

This is still long-winded but it works.

Old approach

The following 59 chars suffice to produce a fraction that will, in decimal form, solve the problem, assuming m, n are entered programmatically:

FixedPoint[(# + n/# )/2 &, 1, SameTest -> (Abs[#1 - #2] < 10^(-m) &)]


When m=18, n=5, here's the fraction:

(* out *)
562882766124611619513723647/251728825683549488150424261


The trick is to convert this fraction into a decimal. The easy way is to use N;

N[%, m+1]
(* out *)
2.236067977499789696


However, N violates the rules by specifying the precision to work with.

Back to the drawing board:

q = FixedPoint[(# + n/# )/2 &, 1, SameTest -> (Abs[#1 - #2] < 10^(-m) &)];
f[{a_, n_, d_}] :=
With[{q = QuotientRemainder[n, d]}, {Append[a, q[[1]]], q[[2]], d/10}]
StringInsert[IntegerString@FromDigits@#[[1]],  ".", -1/Log[Denominator@#[[3]], 10]]
&[NestWhile[f, {{}, Numerator@q, Denominator@q}, Length@#[[1]] < m &]]


Unfortunately, it takes another 205 characters (by my reckoning) to generate a decimal expression from the fraction. Surely there must be a more direct way to divide one integer by another to m decimal places!

main=interact$(\[x,y]->(\s->if '.'elems then(x+1)takes else xtakes)$(show.sqrt.fromIntegral)y++cycle"0").map read.words


Darn sqrt not taking Ints, and fromIntegral being so long!

C# 41 chars

Math.Sqrt(n).ToString().Substring(0,m+1);


Version-1

C# 364 Characters (Short Version)

using System;namespace X{class T{static void Main(string[] a){int m=int.Parse(Console.ReadLine()),n=int.Parse(Console.ReadLine());Console.WriteLine("{2}",f(n,m));}static string f(long s,int l){decimal x=s;for(int i=0;i<20;x=(((x*x)+s)/(2*x)),i++);var b=x.ToString(string.Format("F{0}",l));return(x.ToString().Contains("."))?b.Substring(0,l+1):b.Substring(0,l);}}}


code can be ran from OneIDE - http://ideone.com/9tZsD.

C# Normal Version

using System;

namespace X
{
class T
{
static void Main(string[] a)
{
Console.WriteLine("m:{0}, n:{1} -> {2}", m, n, f(n,m));
}
static string f(long s,int l)
{
decimal x = s;
for(int i = 0; i < 20; x = (((x * x) + s) / (2 * x)), i++) ;
var b=x.ToString(string.Format("F{0}", l));
return(x.ToString().Contains("."))?b.Substring(0,l+1):b.Substring(0,l);
}
}
}

• It doesn't work for all the test cases: test case #4 (2, 10000) should output 10, not 100.00. As well, #1 and #2's outputs are cut off at 13 digit precision. – beary605 Aug 6 '12 at 21:02
• tx @beary605 for pointing out issues around #4, updated code with new oneide link – Saumil Aug 6 '12 at 21:57