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

Question

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.

Answer 1

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.

Answer 2

Mathematica 66 272 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!

Answer 3

Haskell 126

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 Ints, and fromIntegral being so long!

Answer 4

C# 41 chars

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

Answer 5

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)
        {
            int m = int.Parse( Console.ReadLine()), n = int.Parse( Console.ReadLine());
            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);
        }
    }       
}

Answer 6

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
        readLn(digit, number);
        
        { `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.