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.

Out of interest, our best mate is going to cost $35 as of March ... — StuartLC, Feb 08 '11 at 10:30

score 21 · Accepted Answer · edited May 23 '21 at 18:34

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.

Hsns, Many Thanks for the in-depth answer. – Raghu Feb 11 '11 at 12:53 — Raghu, Feb 11 '11 at 12:53

score 4 · Answer 2 · answered Feb 08 '11 at 10:32

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.

score 2 · Answer 3 · answered Feb 08 '11 at 10:34

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)

It's still software even if it's stored in the hardware and called a micro-program. — Serge Wautier, Feb 08 '11 at 10:39

score 1 · Answer 4 · answered Feb 08 '11 at 10:36

1

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?"

answered Feb 08 '11 at 10:36

Jaroslav Jandek

9,463
1
28
30

I'm not sure if that will get the least significant bit(s) correct. – CodesInChaos Feb 08 '11 at 10:38
Well, of course. That is why I stated it is very `crude`, of course, you can iterate many more times to reach a sufficient margin of error, but that would make the algorithm less readable. `2d` is `2` as `double`. – Jaroslav Jandek Feb 08 '11 at 10:41

score 0 · Answer 5 · answered Feb 10 '21 at 18:25

0

To recreate the System.Math.Sqrt function, just do this:

public static double Sqrt(double n) => Math.Pow(n, 1 / 2);

answered Feb 10 '21 at 18:25

DerickXIGamer

1
3

c# Math.Sqrt Implementation

5 Answers5

Linked

Related