Реализация c # Math.Sqrt - PullRequest
Новая
       31

Реализация c # Math.Sqrt

10 голосов
/ 08 февраля 2011

В последнее время я довольно часто использую System.Math, а на днях мне стало интересно, как Microsoft реализовала бы метод Sqrt в библиотеке.Поэтому я открыл свой лучший помощник Reflector и попытался разобрать метод в библиотеке, но он показал: 

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

В тот день я впервые понял, насколько зависимы мои дети от фреймворка,кушать.

Шутки, но мне было интересно, какой алгоритм MS использовал бы для реализации этого метода или другими словами, как бы вы написали свою собственную реализацию Math.Sqrt в C #, если бы у вас не было поддержки библиотеки.

Приветствия

Ответы [ 4 ]

17 голосов
/ 08 февраля 2011

Любой из методов, найденных вами в Reflector или Reference Source, имеющих атрибут MethodImplOptions.InternalCall, фактически реализован в C ++ внутри CLR.Вы можете получить исходный код для них из дистрибутива SSCLI20.Соответствующий файл - clr / src / vm / ecall.cpp, он содержит таблицу имен методов с указателями на функции, используемую компилятором JIT для непосредственного встраивания адреса вызова в сгенерированный машинный код.Соответствующий раздел таблицы: 

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

, который приводит вас к clr / src / classlibnative / float / comfloat.cpp 

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

    return (double) sqrt(d);
FCIMPLEND

Он просто вызывает функцию CRT.Но это не то, что происходит в джиттере x86, обратите внимание на «встроенный» в объявлении таблицы.Вы не обнаружите, что в версии джиттера SSLI20 это простой, не обремененный патентами.Тем не менее, поставляемый продукт превращает его во внутреннее: 

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

переводится в 

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

Другими словами, Math.Sqrt () переводится в одну инструкцию машинного кода с плавающей запятой.Проверьте этот ответ для получения подробной информации о том, как это легко превосходит нативный код.

4 голосов
/ 08 февраля 2011

Функция будет переведена в инструкции ассемблера. Например, инструкция fsqrt для x87.

Вы можете реализовать числа с плавающей запятой в программном обеспечении, но это, скорее всего, будет намного медленнее. Я думаю, что для Sqrt итерационный алгоритм типичная реализация.

2 голосов
/ 08 февраля 2011

Google.com даст вам больше ответов, чем StackOverflow.com

Посмотрите на эту страницу: http://en.wikipedia.org/wiki/Methods_of_computing_square_roots Один алгоритм можно найти под заголовком «Двоичная система счисления (база 2)» на приведенной выше странице вики.

Но программные реализации НЕ будут эффективными. Современные процессоры имеют аппаратные реализации для математических функций в FPU. Вам просто нужно вызвать правильные инструкции процессора (на ассемблере или машинном языке)

1 голос
/ 08 февраля 2011 
public double Sqrt(int number)
{
    double x = number / 2;

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

    return x;
}

Очень грубый метод, но если бы я использовал что-то более сложное, такое как метод журнала, вы могли бы спросить "а как я могу реализовать метод журнала?"

...