math.h Pow против ручного питания
Мне просто было интересно, как pow функция math.h библиотека работает, реализует ли она самый простой последовательный алгоритм или использует другой?
Я просто знаю алгоритм повторного возведения в квадрат, который сообщает O (log n), может быть, это реализованный алгоритм pow функционировать?
Так что я только что сделал несколько тестов, используя последовательный алгоритм против pow и обнаружил, что первая версия почти в 3 раза быстрее второй. Действительно ли вызывающие функции наказывают так сильно за производительность этого теста? Зачем?
Любые другие комментарии, объясняющие, что происходит, или как pow реализовано приветствуются.
РЕДАКТИРОВАТЬ: Я был неправ, pow в 3 раза Быстрее чем последовательный алгоритм.
Решение
Реализация pow() в math.h намного сложнее, чем это — взгляните на эту свободно доступную реализацию (ссылка на сайт).
Проблема с повторным возведением в квадрат состоит в том, что он не является достаточно общим, чтобы иметь дело с дробными степенями. pow() от math.h должен иметь дело с этим, так что это обязательно медленнее в некоторых тестовых случаях. Однако, поскольку функция многократного возведения в квадрат не имеет той же функциональности, сравнение не является яблоком.
Вообще говоря, гораздо проще оптимизировать производительность, если вам не нужно обрабатывать общий случай. Например, если вы никогда не увеличите числа до дробных степеней, вы можете создать алгоритм, который превосходит библиотечную функцию 3: 1 в микропроцессоре. Это должно прийти с пониманием того, что применимость «более быстрой» функции не так широка.
Другие решения
Согласно стандарту ANSI C99, раздел 7.12.7.4:
Описание
powфункции вычисляютxвозведен во властьy, Ошибка домена возникает, еслиxконечно и отрицательно иyконечно, а не целочисленное значение. Ошибка домена может произойти, еслиxноль иyменьше или равно нулю.Возвращает
powвозврат функцийx^y,
Другими словами, он не определяет точный алгоритм, который будет использоваться. Вам нужно взглянуть на исходный код стандартной библиотеки C / C ++, которую вы используете. Я бы предположил, что большинство авторов библиотек использовали высокооптимизированный алгоритм.
Обновить: В комментариях вы говорите, что используете MinGW32. Это ссылается на среду выполнения Microsoft, msvcrt. Хотя это не с открытым исходным кодом, глядя на Документация Microsoft все, что мы знаем, это то, что он использует SSE2. Это, вероятно, очень эффективно.