# 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 '.'`elem`s then(x+1)`take`s else x`take`s)\$(show.sqrt.fromIntegral)y++cycle"0").map read.words
``````

Darn `sqrt` not taking `Int`s, and `fromIntegral` being so long!

-

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

C# 41 chars

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