c# Math.Sqrt Implementation

Question

I've been using System.Math quite a lot lately and the other day I was wondering, how Microsoft would have implemented the Sqrt method in the library. So I popped open my best mate Reflector and tried to Disassemble the method in the library, but it showed:

[MethodImpl(MethodImplOptions.InternalCall),ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
public static extern double Sqrt(double d);

That day for the first time ever, I realized how dependent my kids are on the framework, to eat.

Jokes apart, but i was wondering what sort of algorithm MS would have used to implement this method or in other words how would you write your own implementation of Math.Sqrt in C# if you had no library support.

Cheers

Answer 1

Any of the methods you find back with Reflector or the Reference Source that have the MethodImplOptions.InternalCall attribute are actually implemented in C++ inside the CLR. You can get the source code for these from the SSCLI20 distribution. The relevant file is clr/src/vm/ecall.cpp, it contains a table of method names with function pointers, used by the JIT compiler to directly embed the call address into the generated machine code. The relevant table section is

FCIntrinsic("Cos", COMDouble::Cos, CORINFO_INTRINSIC_Cos)
FCIntrinsic("Sqrt", COMDouble::Sqrt, CORINFO_INTRINSIC_Sqrt)
FCIntrinsic("Round", COMDouble::Round, CORINFO_INTRINSIC_Round)
...

Which takes you to clr/src/classlibnative/float/comfloat.cpp

FCIMPL1_V(double, COMDouble::Sqrt, double d)
    WRAPPER_CONTRACT;
    STATIC_CONTRACT_SO_TOLERANT;

    return (double) sqrt(d);
FCIMPLEND

It just calls the CRT function. But that's not what happens in the x86 jitter, note the 'intrinsic' in the table declaration. You won't find that in the SSLI20 version of the jitter, it is a simple one unencumbered by patents. The shipping one however does turn it into an intrinsic:

        double d = 2.0;
        Console.WriteLine(Math.Sqrt(d));

translates to

00000008  fld         dword ptr ds:[0072156Ch] 
0000000e  fsqrt 
..etc

In other words, Math.Sqrt() translates to a single floating point machine code instruction. Check this answer for details on how that beats native code handily.

Answer 2

The function will be translated into assembler instructions. Such as the fsqrt instruction of the x87.

You could implement floating point numbers in software, but that will most likely be much slower. I think for Sqrt an iterative algorithm the typical implementation.

Answer 3

Google.com will give you more answers than StackOverflow.com

Have a look at this page: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots One algorithm can be found under the title " Binary numeral system (base 2)" in the above wiki page.

But, software implementations will NOT be efficient. Modern CPU's have hardware implementations for math functions in FPU. You just need to invoke the correct instructions of the processor (in assembly or machine language)

Answer 4

public double Sqrt(int number)
{
    double x = number / 2;

    for (int i = 0; i < 100; i++) x = (x + number / x) / 2d;

    return x;
}

Very crude method but if I used something more elaborate such as log method, you could ask "and how can I implement the log method?"