Я пытаюсь вычислить logab (и получить обратно число с плавающей запятой, а не целое число). Я планировал сделать это как log(b)/log(a). Математически говоря, я могу использовать любую из cmath логарифмических функций (по основанию 2, e или 10) для выполнения этого вычисления; тем не менее, я буду часто выполнять этот расчет во время своей программы, поэтому мне было интересно, будет ли один из них значительно быстрее, чем другие (или, что еще лучше, если есть более быстрый, но все же простой способ сделать это). Если это имеет значение, то и a, и b являются целыми числами.
C/C++ самая быстрая операция журнала cmath
Ответы (5)
Поскольку b и a являются целыми числами, вы можете использовать всю прелесть перебора битов, чтобы найти их журналы для база 2. Вот некоторые из них:
- Найдите логарифмическую базу 2 целого числа с набором MSB N за O (N) операций (очевидный способ)
- Найдите целое число по основанию 2 целого числа с 64-битным числом с плавающей запятой IEEE.
- Найдите логарифмическую базу 2 целого числа с помощью таблицы поиска
- Найдите логарифмическую базу 2 N-битного целого числа в операциях O (lg (N))
- Найдите логарифмическую базу 2 N-битного целого числа в операциях O (lg (N)) с умножением и поиском
Я оставлю вам возможность выбрать лучшую функцию «быстрого журнала» для ваших нужд.
person
Jacob
schedule
11.07.2011
Классная ссылка. Интересно, какой-либо из этих методов быстрее, чем прямолинейные на современных процессорах?
- person Mark Ransom; 12.07.2011
@MarkRansom: все они будут намного медленнее, чем использование аппаратной инструкции для подсчета ведущих нулей, которую все современные архитектуры имеют , потому что методы циклов будут неверно предсказывать ветвления с разными входными данными. HW Inn очень дешево. Оригинальный x86
bsr неуклюж (не определен, если ввод равен 0), но дает результат log2 напрямую, а не 32-log2(a). Только совсем новые процессоры поддерживают lzcnt, который определен для 0. AVX512CD представит VPLZCNTD, который делает это для каждого элемента в векторе целых чисел.
- person Peter Cordes; 31.01.2016
Кроме того, я думал, что ОП ищет решение, которое не округляет/не усекает промежуточные результаты до целого числа. Конечно, начальные значения целые, но
integer_log2(uint32_t) имеет диапазон только от 0 до 32, поэтому дробная часть имеет большую разницу. Существует огромный диапазон чисел от 2^30 до 2^31, но все они имеют один и тот же ilog2.
- person Peter Cordes; 31.01.2016
Сначала предварительно вычислите 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).
person
Mark Ransom
schedule
11.07.2011
+1 Хорошее наблюдение. Хотя в другом ответе есть смысл, поскольку эти операции настолько быстры, что в любом случае оптимизация - это немного.
- person Jesus Ramos; 12.07.2011
@ Иисус Рамос, я всегда даю вопрос в пользу сомнения. Я работал над операциями с пикселями, которые выполняются миллионы раз за раз, когда пользователь ожидает мгновенных результатов, и не нужно много воображения, чтобы предположить, что у кого-то еще могут быть подобные ограничения.
- person Mark Ransom; 12.07.2011
Это правда, но оптимизация более новыми компиляторами почти устраняет необходимость делать некоторые из этих вещей, что довольно печально. Хотя большинство до сих пор выписывают такие оптимизации.
- person Jesus Ramos; 12.07.2011
Я почти уверен, что логарифм по основанию 2 является самым быстрым, поскольку только он имеет собственную инструкцию ассемблера (по крайней мере, в наборе инструкций 8087).
- person MartinStettner; 12.07.2011
@ Иисус Рамос, я не думаю, что деление на константу часто заменяется умножением на инверсию, поскольку компилятор не может гарантировать, что младшие биты результата будут идентичными. Я думаю, что деление по-прежнему медленнее, чем умножение, даже на современных процессорах, и вы бы заметили разницу.
- person Mark Ransom; 12.07.2011
Я думаю, что в некоторых (по крайней мере, ICC делает это для некоторых инструкций) происходит просмотр повторяющегося используемого значения и сохранение его в памяти, поэтому, если журнал (константа) используется много, он вычисляется один раз и сохраняется где-то, поэтому он не всегда пересчитывается .
- person Jesus Ramos; 12.07.2011
@Mark: точно правильно. Если не установлен такой флаг, как
fast-math, компилятор не может заменить деление обратным умножением (не только потому, что это изменяет округление, но и потому, что это может вызвать ложные переполнения и NaN). И да, деление намного медленнее, чем умножение на большинстве современных процессоров.
- person Stephen Canon; 12.07.2011
Инструкции журнала вряд ли будут использоваться современными компиляторами, поскольку они неточны (по сравнению с тем, что вы можете делать в программном обеспечении) и доступны только в устаревшем наборе инструкций x87.
- person zwol; 30.01.2016
На платформах, для которых у меня есть данные, log2 немного быстрее остальных, что соответствует моим ожиданиям. Однако обратите внимание, что разница чрезвычайно незначительна (всего пара процентов). Об этом действительно не стоит беспокоиться.
Напишите понятную реализацию. Затем измерьте производительность.
person
Stephen Canon
schedule
11.07.2011
В наборе инструкций 8087 есть только инструкция для логарифмирования по основанию 2, так что я бы предположил, что эта будет самой быстрой.
Конечно, такой вопрос во многом зависит от вашего процессора/архитектуры, поэтому я бы предложил провести простой тест и засечь время.
person
MartinStettner
schedule
11.07.2011
На современных процессорах x86 оказывается, что хорошие реализации программного журнала работают быстрее, чем инструкция аппаратного журнала, поэтому база, используемая в этой инструкции, на самом деле не имеет значения для вопроса.
- person Stephen Canon; 12.07.2011
@ Стивен Кэнон, если у вас есть ссылка на некоторые результаты синхронизации, это было бы отличным местом, чтобы рассказать об этом.
- person Mark Ransom; 12.07.2011
@Mark Ransom, в Руководстве по оптимизации Intel указано, что
fyl2x имеет пропускную способность 1 результат каждые 85 циклов и задержку от 140 до 190 циклов. Напротив, используя системную математическую библиотеку в OSX на моем MacBook Pro, я измеряю log2( ) как имеющую задержку ~ 72 цикла и пропускную способность 1 результат каждые 46 циклов. Так что программная реализация здесь примерно в два раза быстрее.
- person Stephen Canon; 12.07.2011
Ответ:
- это зависит
- профиль это
Вы даже не упомянули свой тип процессора, тип переменной, флаги компилятора, расположение данных. Если вам нужно сделать много из этого параллельно, я уверен, что будет опция SIMD. Ваш компилятор будет оптимизировать это, если вы используете выравнивание и очищаете простые циклы (или valarray, если вам нравятся архаичные подходы).
Скорее всего, у компилятора Intel есть специальные приемы для процессоров Intel в этой области.
Если вы действительно хотите, вы можете использовать CUDA и GPU.
Я полагаю, если вам не повезло, что у вас нет этих наборов инструкций, вы могли бы упасть в бит уровня fiddling и написать алгоритм, который делает хорошее приближение. В этом случае я могу поспорить более чем на один яблочный пирог, что 2-log будет быстрее, чем любой другой base-log.
person
sehe
schedule
11.07.2011
(x^2+y^2) < maxdistance^2вместоsqrt(x^2+y^2) < maxdistance, особенно. если вы выполняете эту проверку неоднократно (например, во внутреннем цикле Мандельброта) или с целыми числами. (Скалярное целочисленное деление x86 медленнее, чем деление SIMD FP.) - person Peter Cordes schedule 31.01.2016