# 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). Aug 4, 2012 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, 2012 at 23:32
• @Gareth: Yeah, it's probably 12345678, I probably copied it from WA wrong. Aug 4, 2012 at 23:53
• @Matt: No, as long as you don't use any command that explicitly sets the precision. Aug 4, 2012 at 23:55
• What should 2 10000 output? 100? Aug 5, 2012 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, 2012 at 18:54
• @Matt: fixed... Aug 6, 2012 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][]], 10 q[d, k][], k};
t@r[] <> "." <> t@FromDigits@Nest[h, {{}, 10 r[], k}, m][]


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[]], q[], d/10}]
StringInsert[IntegerString@FromDigits@#[],  ".", -1/Log[Denominator@#[], 10]]
&[NestWhile[f, {{}, Numerator@q, Denominator@q}, Length@#[] < 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. Aug 6, 2012 at 21:02
• tx @beary605 for pointing out issues around #4, updated code with new oneide link Aug 6, 2012 at 21:57

## Pascal, 142 bytes

This full program requires a processor supporting features of “Extended Pascal” (ISO standard 10206). The program will crash if m is negative.

program p(input,output);var n,m:integer;p:string(maxInt);begin read(m,n);writeStr(p,sqrt(abs(n)):1:m);write(p:m+ord(index(p,'.')in[1..m]))end.


Ungolfed:

program findFirstNDigitsOfSquareRootOfANumber(input, output);
var
number, digit: integer;
print: string(maxInt);
begin

{ Sqrt only works on non-negative integers and always returns
the principal root as a real value. The writeStr routine is
defined by Extended Pascal. The :1 specifies the minimum width
of the given argument. The write routines in combination with a
real argument accept a second format specifier (here :digit)
that disables scientific notation and determines the number of
post-decimal (i.e. fractional) digits. }
writeStr(print, sqrt(abs(number)):1:digit);

{ The format specifier :digit… in combination with a string
argument specifies the _exact_ width. We will need to take
account of the radix mark ('.') _if_ it is printed, though. }
writeLn(print:digit + ord(index(print, '.') in [1..digit]));
end.


It is not possible to request maxInt digits since one char value will be occupied by the radix mark (.). You will probably need to replace maxInt by a sufficiently small natural number, though.