Как Math.Pow () реализован в .NET Framework?

433

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

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

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

Паван Мишра
источник
15
Точно так же, как к вашему сведению, если вас смущает целое InternalCallс externмодификатором (так как они кажутся противоречивыми), пожалуйста, посмотрите вопрос (и полученные ответы), который я разместил об этой самой вещи.
CraigTP
6
Для 2^xоперации, если xцелое число, результатом является операция сдвига. Поэтому, возможно, вы могли бы построить результат, используя мантиссу 2и показатель степени x.
ja72
@SurajJain Ваш комментарий на самом деле вопрос, который вы должны опубликовать отдельно.
ja72
@SurajJain Я согласен с тобой. Я не модератор, поэтому я не могу здесь многое сделать. Может быть, вопрос о понижении можно задать на meta.stackoverflow.com
ja72

Ответы:

855

MethodImplOptions.InternalCall

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

Для просмотра кода требуется исходный код CLR. Вы можете получить это из дистрибутива SSCLI20 . Он был написан в течение периода времени .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 / float / comfloat.cpp. Я избавлю вас от кода, просто посмотрите сами. Он в основном проверяет угловые случаи, затем вызывает версию CRT pow().

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

Кстати, исходный код для 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 и бесконечность, возведенная в любую степень.

Ганс Пассант
источник
437
Отличный ответ, StackOverflow нуждается в большем количестве подобных вещей, а не в «Почему вы хотите это знать?» это случается слишком часто.
Том Вт
16
@Blue - я не знаю, если не шутить над инженерами Intel. У моей школьной книги действительно есть проблема, возводящая что-то в силу отрицательного интеграла. Pow (x, -2) отлично вычисляется, Pow (x, -2.1) не определено. Доменные проблемы - сука, чтобы иметь дело с.
Ганс Пассант
12
@ BlueRaja-DannyPflughoeft: много усилий затрачивается на то, чтобы операции с плавающей запятой были как можно ближе к правильно округленному значению. powобщеизвестно, что трудно осуществить точно, будучи трансцендентной функцией (см . Дилемма Table-Maker ). Это намного проще с интегральной силой.
Porges
9
@ Ханс Пассант: Почему бы Пау (х, -2,1) быть неопределенным? Математически pow определяется везде для всех x и y. Вы склонны получать комплексные числа для отрицательного x и нецелого y.
Жюль
8
@Jules pow (0, 0) не определено.
выбить
110

Ответ Ханса Пассанта великолепен, но я хотел бы добавить, что если 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;
    }    
}

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

Михаил Грачик
источник
11
Этот алгоритм ( квадрат и умножение ) также применяется, если aэто число с плавающей запятой.
CodesInChaos
14
На практике это можно сделать немного лучше, чем родное квадратичное и умножение. Например, подготовка таблиц подстановки для малых показателей, чтобы вы могли возводить в квадрат несколько раз и только затем умножение, или создание оптимизированных цепочек сложения квадратов для фиксированных показателей. Проблема такого рода является неотъемлемой частью важных криптографических алгоритмов, поэтому было проведено немало работы по ее оптимизации. NP-твердость касается только асимптотики в худшем случае , мы часто можем предложить оптимальные или почти-оптимальные решения для случаев, возникающих на практике.
CodesInChaos
В тексте не упоминается aцелое число, а код -. Как следствие этого, меня интересует точность результата "очень эффективного" вычисления текста.
Эндрю Мортон
69

Если свободно доступная версия Cpow является какой-либо индикацией, она не выглядит так, как вы ожидаете. Вам не очень поможет найти версию .NET, потому что проблема, которую вы решаете (то есть, с целыми числами), на несколько порядков проще и может быть решена в несколько строк кода на C # с возведением в степень по алгоритму возведения в квадрат .

dasblinkenlight
источник
Спасибо за Ваш ответ. Первая ссылка удивила меня, так как я не ожидал такой масштабной технической реализации функции Pow (). Хотя ответ Ханса Пассанта подтверждает, что в мире .Net то же самое. Я думаю, что могу решить эту проблему, используя некоторые методы, перечисленные в ссылке алгоритма возведения в квадрат. Еще раз спасибо.
Паван Мишра
2
Я не верю, что этот код эффективен. 30 локальных переменных просто должны поднять все регистры. Я только предполагаю, что это версия ARM, но на x86 30 локальных переменных в методе - это круто.
Алексей Жуковский