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

Question

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

412

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

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

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

Pawan Mishra 15 янв. 2012, в 12:56

Источник

15

Точно так же, как к вашему сведению, если вы запутались во всем InternalCall с модификатором extern (так как они кажутся конфликтующими), пожалуйста, посмотрите вопрос (и полученные ответы), который я опубликовал об этой самой вещи.
CraigTP 15 янв. 2012, в 19:33
6

Для операции 2^x если x является целым числом, результатом является операция сдвига. Поэтому, возможно, вы могли бы построить результат, используя мантиссу 2 и показатель степени x .
ja72 17 дек. 2012, в 00:50
0

@SurajJain Ваш комментарий на самом деле вопрос, который вы должны опубликовать отдельно.
ja72 11 окт. 2016, в 22:58
0

@SurajJain Я согласен с тобой. Я не модератор, поэтому я не могу здесь многое сделать. Может быть, вопрос о понижении можно задать на meta.stackoverflow.com
ja72 14 окт. 2016, в 13:00

Показать ещё 2 комментария

Теги:

c#

.net

pow

3 ответа

100

Ответ Hans Passant - это замечательно, но я хотел бы добавить, что если b является целым числом, то a^b можно вычислить очень эффективно с бинарным разложением, Здесь измененная версия от Henry Warren Hacker Delight:

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. Таким образом, в основном это означает, что двоичное разложение так же хорошо, как и получается.

Michael Graczyk 10 июль 2012, в 19:52

11

Этот алгоритм ( квадрат и умножение ) также применяется, если a является числом с плавающей запятой.
CodesInChaos 22 сен. 2012, в 10:25
13

На практике это можно сделать немного лучше, чем родное квадратичное и умножение. Например, подготовка справочных таблиц для малых показателей, чтобы вы могли возводить в квадрат несколько раз и только затем умножение, или создание оптимизированных цепочек сложения квадратов для фиксированных показателей. Проблема такого рода является неотъемлемой частью важных криптографических алгоритмов, поэтому было проведено немало работы по ее оптимизации. NP-твердость касается только асимптотики в худшем случае , мы часто можем предложить оптимальные или почти-оптимальные решения для случаев, возникающих на практике.
CodesInChaos 06 окт. 2013, в 11:12
0

Текст не упоминается a является целым числом, но делает код. Как следствие этого, я задаюсь вопросом о точности результата "очень эффективного" вычисления текста.
Andrew Morton 01 апр. 2018, в 17:09

Показать ещё 1 комментарий

62

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

dasblinkenlight 15 янв. 2012, в 14:59

0

Спасибо за Ваш ответ. Первая ссылка удивила меня, так как я не ожидал такой масштабной технической реализации функции Pow (). Хотя ответ Ханса Пассанта подтверждает, что в мире .Net то же самое. Я думаю, что могу решить проблему, используя некоторые методы, перечисленные в ссылке алгоритма возведения в квадрат. Еще раз спасибо.
Pawan Mishra 15 янв. 2012, в 16:00
2

Я не верю, что этот код эффективен. 30 локальных переменных просто должны поднять все регистры. Я только предполагаю, что это версия ARM, но на x86 30 локальных переменных в методе - это круто.
Alex Zhukovskiy 21 янв. 2015, в 00:32

Ещё вопросы

Точно так же, как к вашему сведению, если вы запутались во всем InternalCall с модификатором extern (так как они кажутся конфликтующими), пожалуйста, посмотрите вопрос (и полученные ответы), который я опубликовал об этой самой вещи.
Для операции 2^x если x является целым числом, результатом является операция сдвига. Поэтому, возможно, вы могли бы построить результат, используя мантиссу 2 и показатель степени x .
@SurajJain Ваш комментарий на самом деле вопрос, который вы должны опубликовать отдельно.
@SurajJain Я согласен с тобой. Я не модератор, поэтому я не могу здесь многое сделать. Может быть, вопрос о понижении можно задать на meta.stackoverflow.com
Этот алгоритм ( квадрат и умножение ) также применяется, если a является числом с плавающей запятой.
На практике это можно сделать немного лучше, чем родное квадратичное и умножение. Например, подготовка справочных таблиц для малых показателей, чтобы вы могли возводить в квадрат несколько раз и только затем умножение, или создание оптимизированных цепочек сложения квадратов для фиксированных показателей. Проблема такого рода является неотъемлемой частью важных криптографических алгоритмов, поэтому было проведено немало работы по ее оптимизации. NP-твердость касается только асимптотики в худшем случае , мы часто можем предложить оптимальные или почти-оптимальные решения для случаев, возникающих на практике.
Текст не упоминается a является целым числом, но делает код. Как следствие этого, я задаюсь вопросом о точности результата "очень эффективного" вычисления текста.
Спасибо за Ваш ответ. Первая ссылка удивила меня, так как я не ожидал такой масштабной технической реализации функции Pow (). Хотя ответ Ханса Пассанта подтверждает, что в мире .Net то же самое. Я думаю, что могу решить проблему, используя некоторые методы, перечисленные в ссылке алгоритма возведения в квадрат. Еще раз спасибо.
Я не верю, что этот код эффективен. 30 локальных переменных просто должны поднять все регистры. Я только предполагаю, что это версия ARM, но на x86 30 локальных переменных в методе - это круто.

Hans Passant · Accepted Answer · 2012-01-15T16-13-00.000Z

MethodImplOptions.InternalCall

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

Взглянув на код, требуется исходный код для 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. Но, конечно же, для других простых операций. Примечательно, что это может сделать математику с плавающей запятой в С# существенно быстрее, чем тот же код в С++, проверьте этот ответ по этой причине.

Кстати, исходный код для 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));
}

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

Отличный ответ, StackOverflow нуждается в большем количестве подобных вещей, а не в «Почему вы хотите это знать?» это случается слишком часто.
Согласна с Томом В. Фантастический ответ. Я узнал больше, чем ожидал. Интересно, что я набрал 1000 баллов, пометив ваш пост как «Ответ». Еще раз спасибо.
@ Я не уверен, что смогу следовать последнему абзацу: если я crt/src/math.h в crt/src/math.h я действительно найду _Pow_int (~ строка 493 на моей установке vs2010), который, по крайней мере, мне кажется, используется для всех Пау звонит. И это похоже на очевидный сдвиг и умножение реализации. Я что-то здесь упускаю? (Я предполагаю, что оптимизированная реализация Intel будет использовать некое волшебство SSE? Кажется, мы могли бы немного распараллелить его, но не уверены, что это будет улучшением)
@Voo - это специализация шаблона для вызовов pow (), которые передают целочисленную степень. Например, pow (x, 2) = x * x. Да, версия Intel использует довольно сложный машинный код SSE2.
@ Hans Ups Я полностью пропустил ту часть, где сила была двойной. Моя вина.
@Blue - я не знаю, если не шутить над инженерами Intel. У моей школьной книги действительно есть проблема, возводящая что-то в силу отрицательного интеграла. Pow (x, -2) отлично вычисляется, Pow (x, -2.1) не определено. Доменные проблемы - сука, чтобы иметь дело с.
@ BlueRaja-DannyPflughoeft: много усилий затрачивается на то, чтобы операции с плавающей запятой были как можно ближе к правильно округленному значению. pow трудно точно реализовать, являясь трансцендентальной функцией (см . Дилемма Table-Maker ). С интегральной силой это намного проще.
@ Ханс Пассант: Почему бы Пау (х, -2,1) быть неопределенным? Математически pow определяется везде для всех x и y. Вы склонны получать комплексные числа для отрицательного x и нецелого y.
@ Emboss: верно, это единственный случай. Хотя некоторые математики определяют его как 1 или 0, у pow действительно есть существенный разрыв при (0,0), поэтому нет единственного способа исправить его (так что, вероятно, лучше всего вообще не исправлять его).
@Jules Сложные числа только что были добавлены в Framework для 4.0, msdn.microsoft.com/en-us/library/… . Теперь он определяет Pow (Комплекс, Двойной) и Pow (Комплекс, Комплекс).
@amoss А они? Это было бы очень удобно пять лет назад, когда я писал геопространственные функции для плитки DIY в настольном приложении. К счастью, Google устарел, пока я не сошел с ума. Марена.
@HansPassant - я думаю, что вы имели в виду Pow(x, -2.1) не определен (или сложен) для отрицательных значений x, верно? Знак показателя не делает его более или менее вычислимым, если x не равно 0.
Это все еще верно для Рослин? Я вижу, что coreclr на Github все еще показывает это как внутренний вызов: github.com/dotnet/coreclr/blob/…
Посмотрите на вопрос, обратите внимание, что он идентичен.
Я думаю, что это фактическая реализация C ++ CLR (по крайней мере, для coreclr) github.com/dotnet/coreclr/blob/…