Как внедряется Math.Pow() в .NET Framework?

Question

Я искал эффективный подход для вычисления ^b (скажем, a = 2 и b = 50). Чтобы начать работу, я решил взглянуть на реализацию функции Math.Pow(). Но в .NET Reflector, все я нашел это:

[MethodImpl(MethodImplOptions.InternalCall), SecuritySafeCritical] 
public static extern double Pow(double x, double y); 

Что некоторые из ресурсов, где я могу видеть, как то, что происходит внутри, когда я называю Math.Pow() функцию?

Answer 1

MethodImplOptions.InternalCall

Это означает, что метод на самом деле реализуется в CLR, написанный на C++. Компилятор «точно в срок» обращается к таблице с внутренне реализованными методами и напрямую компилирует вызов функции C++.

Для просмотра кода необходим исходный код для CLR. Вы можете получить это от SSCLI20 distribution. Он был написан вокруг временного интервала .NET 2.0, я нашел реализации на низком уровне, например Math.Pow(), чтобы быть в значительной степени точным для более поздних версий CLR.

Таблица поиска находится в каталоге clr/src/vm/ecall.cpp. Раздел, который релевантен Math.Pow() выглядит следующим образом:

FCFuncStart(gMathFuncs) 
    FCIntrinsic("Sin", COMDouble::Sin, CORINFO_INTRINSIC_Sin) 
    FCIntrinsic("Cos", COMDouble::Cos, CORINFO_INTRINSIC_Cos) 
    FCIntrinsic("Sqrt", COMDouble::Sqrt, CORINFO_INTRINSIC_Sqrt) 
    FCIntrinsic("Round", COMDouble::Round, CORINFO_INTRINSIC_Round) 
    FCIntrinsicSig("Abs", &gsig_SM_Flt_RetFlt, COMDouble::AbsFlt, CORINFO_INTRINSIC_Abs) 
    FCIntrinsicSig("Abs", &gsig_SM_Dbl_RetDbl, COMDouble::AbsDbl, CORINFO_INTRINSIC_Abs) 
    FCFuncElement("Exp", COMDouble::Exp) 
    FCFuncElement("Pow", COMDouble::Pow) 
    // etc.. 
FCFuncEnd() 

Поиск "COMDouble" принимает вас CLR/SRC/classlibnative/плавать/comfloat.cpp. Я пощажу вам код, просто взгляните на себя. Он в основном проверяет угловые случаи, затем называет версию CRT pow().

Единственная другая деталь реализации, которая интересна, это макрос FCIntrinsic в таблице. Это намек на то, что джиттер может реализовать функцию как внутреннюю. Другими словами, замените вызов функции инструкцией машинного кода с плавающей запятой. Что не относится к Pow(), для него нет инструкции FPU. Но, конечно же, для других простых операций. Примечательно, что это может сделать математику с плавающей запятой в C# существенно быстрее, чем тот же код в C++, по этой причине проверьте this answer.

Кстати, исходный код для CRT также доступен, если у вас есть полная версия каталога Visual Studio vc/crt/src. Вы попадете в стену на pow(), хотя Microsoft купила этот код у Intel. Лучше работать, чем инженеры Intel, маловероятно. Хотя идентичность моей средней школы книга была в два раза быстрее, когда я попробовал:

public static double FasterPow(double x, double y) { 
    return Math.Exp(y * Math.Log(x)); 
} 

Но не истинный заменитель, поскольку он накапливает ошибку от 3 операций с плавающей точкой и не иметь дело с проблемами доменных извращенцев, что Pow () имеет. Как 0^0 и -Infinity подняты до любой степени.

Answer 2

Если freely available C version of pow - это любое указание, оно не выглядит так, как вы ожидали бы. Было бы не очень полезно найти версию .NET, потому что проблема, которую вы решаете (т. Е. С целыми числами), упрощает порядки величин и может быть решена в нескольких строках кода C# with the exponentiation by squaring algorithm.

Answer 3

Hans Passant's answer Отлично, но я хотел бы добавить, что если b является целым числом, то a^b может быть вычислено очень эффективно с двоичным разложением.Вот модифицированная версия от Восторга Генри Уоррена Хакера:

public static int iexp(int a, uint b) { 
    int y = 1; 

    while(true) { 
     if ((b & 1) != 0) y = a*y; 
     b = b >> 1; 
     if (b == 0) return y; 
     a *= a; 
    }  
} 

Он отмечает, что эта операция является оптимальной (делает минимальное количество арифметических или логические операции) для всех б < 15. Также нет никакого Известного решения общая задача нахождения оптимальной последовательности факторов для вычисления a^b для любого b, кроме расширенного поиска. Это проблема NP-Hard. Таким образом, в основном это означает, что двоичное разложение так же хорошо, как и получается.