math.h pow vs ручная мощность

Мне просто было интересно, как работает функция pow библиотеки math.h, реализует ли она простейший последовательный алгоритм или использует еще один?

Я просто знаю алгоритм повторного возведения в квадрат, который сообщает O (log n), может быть, это алгоритм, реализованный функцией pow?

Поэтому я просто провел несколько тестов с использованием последовательного алгоритма против pow и обнаружил, что первая версия почти в 3 раза быстрее второй. Действительно ли вызывающие функции так сильно наказывают за выполнение этого теста? Почему?

Любые другие комментарии, объясняющие, что происходит, или как реализовано pow, приветствуются.

РЕДАКТИРОВАТЬ: я ошибался, pow в 3 раза быстрее последовательного алгоритма.


c++ performance time algorithm math.h
person dabadaba    schedule 31.12.2013    source источник
comment
Это полностью зависит от того, кто написал вашу стандартную библиотеку. Какой вы используете? Кроме того, pow() работает с числами с плавающей запятой.   -  person SLaks    schedule 31.12.2013
comment
Просто откройте файл math.f и проверьте его? Это исходный код, а не скомпилированная библиотека.   -  person PTwr    schedule 31.12.2013
comment
Это зависит от аргументов. Ваш pow, вероятно, менее общий и менее точный.   -  person zch    schedule 31.12.2013
comment
Предположительно, на x86 типичная реализация может выглядеть как this.   -  person Jerry Coffin    schedule 31.12.2013
comment
Я ненавижу добавлять ссылку, но, похоже, это хороший ресурс, поскольку мне тоже было любопытно: stackoverflow.com/questions/388242/   -  person jms_g4    schedule 31.12.2013
comment
Использую библиотеки MinGW32. Очевидно, что открытие файла math.h не помогает.   -  person dabadaba    schedule 31.12.2013
comment
@dabadaba: как чтение исходного кода интересующей вас функции не может помочь?   -  person PTwr    schedule 31.12.2013
comment
Я предполагаю, что повторное возведение в квадрат не будет и дальше превосходить pow при больших значениях x и y.   -  person Lokno    schedule 31.12.2013
comment
@PTwr, потому что я не вижу реализации?   -  person dabadaba    schedule 31.12.2013
comment
Ваш алгоритм повторного возведения в квадрат обрабатывает pow(2, 0.5) и правильно ли возвращает квадратный корень из 2?   -  person Ted Hopp    schedule 31.12.2013
comment
Я не использую свой собственный алгоритм повторного возведения в квадрат, если вы читаете мой пост, я говорю, что использую собственный последовательный алгоритм против функции math.h pow.   -  person dabadaba    schedule 31.12.2013

Ответы (2)


arrow_upward
9
arrow_downward

Реализация pow() в math.h намного сложнее - взгляните на эту свободно доступную реализацию (ссылка).

Проблема с повторным возведением в квадрат состоит в том, что его недостаточно для работы с дробными степенями. pow() из math.h должен справиться с этим, поэтому в некоторых тестовых случаях он обязательно медленнее. Однако, поскольку функция повторного возведения в квадрат не имеет той же функциональности, сравнение не выполняется по принципу «яблоки с яблоками».

Вообще говоря, гораздо проще оптимизировать производительность, если вам не нужно обрабатывать общий случай. Например, если вы никогда не возводите числа в дробные степени, вы потенциально можете создать алгоритм, который превосходит библиотечную функцию 3: 1 в микротест. Это должно происходить с пониманием того, что применение «более быстрой» функции не так широко.

person Sergey Kalinichenko    schedule 31.12.2013

arrow_upward
2
arrow_downward

Согласно стандарту ANSI C99, раздел 7.12.7.4:

Описание

Функции pow вычисляют x в степени y. Ошибка домена возникает, если x является конечным и отрицательным значением, а y является конечным, а не целым значением. Ошибка домена может возникнуть, если x равно нулю, а y меньше или равно нулю.

Возврат

Функции pow возвращают x^y.

Другими словами, в нем не указывается точный алгоритм, который будет использоваться. Вам нужно будет посмотреть исходный код стандартной библиотеки C / C ++, которую вы используете. Я предполагаю, что большинство авторов библиотек использовали сильно оптимизированный алгоритм.

Обновление: в комментариях вы говорите, что используете MinGW32. Это связано со средой выполнения Microsoft, msvcrt. Несмотря на то, что это не открытый исходный код, из документации Microsoft все, что мы знаем, это то, что он использует SSE2. Вероятно, это очень эффективно.

person Nate    schedule 31.12.2013