C / C ++ самая быстрая операция cmath log - PullRequest
Новая
       39

C / C ++ самая быстрая операция cmath log

20 голосов
/ 12 июля 2011

Я пытаюсь вычислить log a b (и получить обратно число с плавающей запятой, а не целое число).Я планировал сделать это как log(b)/log(a).Говоря математически, я могу использовать любую из cmath функций журнала (основание 2, e или 10) для выполнения этого вычисления;тем не менее, я буду часто выполнять эти вычисления во время моей программы, поэтому мне было интересно, если один из них значительно быстрее других (или еще лучше, если есть более быстрый, но все же простой способ сделать это).Если это имеет значение, то и a, и b являются целыми числами.

Ответы [ 5 ]

15 голосов
/ 12 июля 2011

Во-первых, предварительно вычислите 1.0/log(a) и умножьте вместо каждого log(b) на это выражение.

Редактировать: Первоначально я говорил, что натуральный логарифм (база e) будет самым быстрым, но другие утверждают, что база 2 поддерживается непосредственно процессором и будет самой быстрой. У меня нет оснований сомневаться в этом.

Редактировать 2: Первоначально я предполагал, что a была константой, но перечитывая вопрос, который никогда не задавался. Если это так, то предварительный расчет не принесет пользы. Однако, если это так, вы можете поддерживать удобочитаемость с помощью соответствующего выбора имен переменных: 

const double base_a = 1.0 / log(a);
for (int b = 0; b < bazillions; ++b)
    double result = log(b) * base_a;

Как ни странно, Microsoft не предоставляет функцию журнала 2, что объясняет, почему я не был знаком с ней. Кроме того, инструкция x86 для вычисления журналов включает умножение автоматически, и константы, необходимые для различных баз, также доступны через оптимизированную инструкцию , поэтому я ожидаю, что 3 различных функции журнала иметь одинаковое время (даже основание 2 должно было бы умножиться на 1).

11 голосов
/ 12 июля 2011

Поскольку b и a являются целыми числами, вы можете использовать всю славу битового тиддлинга , чтобы найти их журналы на базе 2. Вот некоторые из них:

  • Найти основную запись 2 для целого числа с MSB N, установленным в O (N) операциях (очевидный способ)
  • Найти основную запись 2 для целого числа с 64-разрядным IEEE-числом с плавающей запятой
  • Найти базу лога 2 целого числа с помощью таблицы поиска
  • Найти базу лога 2 N-битного целого числа в операциях O (lg (N))
  • Найти журнал2-е основание N-битного целого числа в операциях O (LG (N)) с умножением и поиском

Я оставлю вам выбор лучшей функции «быстрого журнала» для ваших нужд.

4 голосов
/ 12 июля 2011

На платформах, для которых у меня есть данные, log2 очень немного быстрее, чем другие, в соответствии с моими ожиданиями. Тем не менее, обратите внимание, что разница чрезвычайно небольшая (всего пара процентов). Об этом действительно не стоит беспокоиться.

Напишите реализацию, которая понятна. Затем измерьте производительность.

1 голос
/ 12 июля 2011

В наборе команд 8087 есть только инструкция для логарифма для основания 2, поэтому я думаю, что это самая быстрая инструкция.

Конечно, этот тип вопросов во многом зависит от вашего процессора /архитектура, поэтому я бы предложил сделать простой тест и время его.

0 голосов
/ 12 июля 2011

Ответ:

  • это зависит
  • профиль это

Вы даже не упоминаете ваш тип процессора, тип переменной,флаги компилятора, расположение данных.Если вам нужно делать много из них параллельно, я уверен, что будет вариант SIMD.Ваш компилятор будет оптимизировать это, пока вы используете выравнивание и очищаете простые циклы (или valarray, если вам нравятся архаичные подходы).

Скорее всего, у компилятора Intel есть специальные приемы для процессоров Intel в этой области.

Если вы действительно хотите, вы можете использовать CUDA и использовать GPU.

Полагаю, есливам не повезло, что вам не хватает этих наборов инструкций , вы можете перейти на уровень с битами и написать алгоритм, который дает хорошее приближение .В этом случае я могу поспорить больше чем один яблочный пирог, что 2-log будет быстрее, чем любой другой base-log

...