Могу ли я вычислить pow(10,x) во время компиляции в c?

Можно ли вычислить pow(10,x) во время компиляции?

У меня есть процессор без поддержки плавающей запятой и медленного целочисленного деления. Я пытаюсь выполнить как можно больше вычислений во время компиляции. Я могу значительно ускорить одну конкретную функцию, если передам в качестве аргументов x и C/pow(10,x) (x и C всегда являются постоянными целыми числами, но они являются разными константами для каждого вызова). Мне интересно, могу ли я сделать эти вызовы функций менее подверженными ошибкам, введя макрос, который автоматически выполняет 1/pow(10,x), вместо того, чтобы заставлять программиста вычислять его?

Есть ли трюк с препроцессором? Могу ли я заставить компилятор оптимизировать вызов библиотеки?


person AShelly    schedule 30.06.2009    source источник
comment
Мне кажется, я видел доказательство того, что препроцессор C завершен по Тьюрингу (я думаю, что это была магнитофонная машина, реализованная в запутанном соревновании C в препроцессоре). Так что способ есть. Хотя не знаю, что это за путь.   -  person Greg D    schedule 01.07.2009
comment
Препроцессор #define не может быть рекурсивным, так как это просто замена текста. Так что, как и Грег, вот место, на поиски которого НЕЛЬЗЯ тратить время. :)   -  person Michael Bray    schedule 01.07.2009
comment
@Greg D: Однако начать с машины Тьюринга и реализовать показатель степени 10 кажется мне амбициозным.   -  person David Thornley    schedule 01.07.2009


Ответы (10)


Вы можете использовать научное представление для значений с плавающей запятой, которое является частью языка C. Это выглядит так:

e = 1.602E-19   // == 1.602 * pow(10, -19)

Число перед E (E может быть заглавным или маленьким 1.602e-19) является дробной частью, где (со знаком) цифровая последовательность после E является экспоненциальной частью. По умолчанию число имеет тип double, но вы можете добавить суффикс с плавающей запятой (f, F, l или L), если вам нужен float или long double.

Я бы не рекомендовал упаковывать эту семантику в макрос:

  1. Это не будет работать для переменных, значений с плавающей запятой и т. д.
  2. Научная нотация более читабельна.
person quinmars    schedule 14.10.2011
comment
Хотя вы это не рекомендуете, это именно то, что мне нужно: #define P10(X) (1eX) в сочетании с #define fixedpt(value,digits) ((value)*(1<<15)/P10(digits)) дает мне желаемый результат, не полагаясь на настройки оптимизации. - person AShelly; 17.10.2011
comment
Какой компилятор работал с #define P10(X) (1eX)? В компиляторе Arduino мне нужно было #define P10(X) (1e##X). - person BigBobby; 18.09.2015

Существует очень мало возможных значений до переполнения int (или даже long). Ради ясности, сделайте это таблицей!

редактировать: если вы используете поплавки (похоже, что вы), то нет возможности вызвать функцию pow() во время компиляции без фактического написания кода, который запускается в процессе make и выводит значения в файл ( например файл заголовка), который затем компилируется.

person Bill K    schedule 30.06.2009
comment
Вдохновленный! Для мощностей известного основания. Это не десятичные дроби. :) - person Michael Bray; 01.07.2009
comment
C и x связаны таким образом, что не будет переполнения: при заданном значении v x выбирается таким образом, что 0,1 ‹= v/pow(10,x) ‹ 1, а C устанавливается равным 32768*v. - person AShelly; 01.07.2009
comment
то, что вы хотели сказать, это total = (total<<1) + (total<<3) И большинство компиляторов могут делать это автоматически, когда вы используете total *= 10 - person leiz; 01.07.2009
comment
@leiz - что? Я имел в виду, что C представляет собой 1,15-представление с фиксированной точкой числа от 0,1 до 1. x всегда является целым числом. - person AShelly; 01.07.2009
comment
Нет необходимости использовать таблицу. Для целых чисел вы можете использовать обозначение E, например. 1.0E5. - person quinmars; 02.07.2009
comment
@quinmars, этот комментарий - именно тот ответ, который я искал, просто мне потребовалось так много времени, чтобы понять это. #define P10(x) (1e##x) делает именно то, что мне нужно. Сделайте свой комментарий ответом для быстрых 25 баллов. - person AShelly; 28.09.2011

GCC сделает это на достаточно высоком уровне оптимизации (за меня это делает -O1). Например:

#include <math.h>

int test() {
        double x = pow(10, 4);
        return (int)x;
}

Компилируется в -O1 -m32 в:

        .file   "test.c"
        .text
.globl test
        .type   test, @function
test:
        pushl   %ebp
        movl    %esp, %ebp
        movl    $10000, %eax
        popl    %ebp
        ret
        .size   test, .-test
        .ident  "GCC: (Ubuntu 4.3.3-5ubuntu4) 4.3.3"
        .section        .note.GNU-stack,"",@progbits

Это работает и без приведения — конечно, вы получаете инструкцию загрузки с плавающей запятой, как в Linux ABI передает возвращаемые значения с плавающей запятой в регистры FPU.

person bdonlan    schedule 30.06.2009
comment
Хороший. Мне интересно, как они проверяют, является ли pow чистой функцией или нет в разумное время компиляции. Может быть, у них есть список известных функций, которые так? - person akappa; 01.07.2009
comment
некоторые математические функции, скорее всего, встроены в компилятор; также GCC имеет нестандартный атрибут pure для функций - person Christoph; 01.07.2009
comment
«чистого» недостаточно для такой оптимизации модуля кросс-компиляции; и GCC будет выполнять сворачивание констант после встраивания, если они находятся в одной и той же единице компиляции. pure - это в основном просто намек компилятору на то, что ему не нужно делать недействительными данные в своих регистрах. - person bdonlan; 01.07.2009
comment
Я ненавижу вникать в лексические парсеры кода C, но теоретически вы можете написать свой собственный препроцессор, чтобы иметь точный контроль над оптимизацией. - person ojblass; 01.07.2009
comment
Не столько препроцессор, сколько прекомпилятор - вам придется иметь дело с возможностью указателей локальных функций, затеняющих глобальный pow() и т. д. - person bdonlan; 01.07.2009
comment
Это лучший ответ. - person Hello Goodbye; 17.12.2020

Вы можете сделать это с помощью Boost.Preprocessor:

http://www.boost.org/doc/libs/1_39_0/libs/preprocessor/doc/index.html

Код:

#include <boost/preprocessor/repeat.hpp>

#define _TIMES_10(z, n, data) * 10
#define POW_10(n) (1 BOOST_PP_REPEAT(n, _TIMES_10, _))

int test[4] = {POW_10(0), POW_10(1), POW_10(2), POW_10(3)};
person e.tadeu    schedule 30.06.2009
comment
к сожалению, я использую только c. - person AShelly; 01.07.2009
comment
Однако OP запросил решение C, а Boost - это библиотека C++. - person DaveR; 01.07.2009
comment
Но вы можете использовать его с C (библиотека Boost.Preprocessor), это только препроцессор, я проверил это;) Только настройте свой каталог включения и включите его! - person e.tadeu; 01.07.2009

На самом деле, используя препроцессор C, вы можете заставить его вычислять C pow(10, x) для любого реального C и интегрального x. Обратите внимание, что, как отметил @quinmars, C позволяет использовать научный синтаксис для выражения числовых констант:

#define myexp 1.602E-19   // == 1.602 * pow(10, -19)

использоваться для констант. Имея это в виду и немного смекалки, мы можем создать макрос препроцессора, который принимает C и x и объединяет их в токен возведения в степень:

#define EXP2(a, b) a ## b
#define EXP(a, b) EXP2(a ## e,b)
#define CONSTPOW(C,x) EXP(C, x)

Теперь это можно использовать как постоянное числовое значение:

const int myint = CONSTPOW(3, 4); // == 30000
const double myfloat = CONSTPOW(M_PI, -2); // == 0.03141592653
person Jon Gjengset    schedule 09.03.2014

На самом деле у вас есть M4, препроцессор которого намного мощнее, чем у GCC. Основное различие между ними заключается в том, что GCC не является рекурсивным, в отличие от M4. Это делает возможными такие вещи, как выполнение арифметических операций во время компиляции (и многое другое!). Приведенный ниже пример кода — это то, что вы хотели бы сделать, не так ли? Я сделал его громоздким в однофайловом исходнике; но я обычно помещаю определения макросов M4 в отдельные файлы и настраиваю свои правила Makefile. Таким образом, ваш код защищен от уродливых навязчивых определений M4 в исходный код C, который я сделал здесь.

$ cat foo.c
define(M4_POW_AUX, `ifelse($2, 1, $1, `eval($1 * M4_POW_AUX($1, decr($2)))')')dnl
define(M4_POW, `ifelse($2, 0, 1, `M4_POW_AUX($1, $2)')')dnl

#include <stdio.h>

int                     main(void)
{
  printf("2^0 = %d\n", M4_POW(2, 0));
  printf("2^1 = %d\n", M4_POW(2, 1));
  printf("2^4 = %d\n", M4_POW(2, 4));

  return 0;
}

Командная строка для компиляции этого примера кода использует возможности GCC и M4 для чтения из стандартного ввода.

$ cat foo.c | m4 - | gcc -x c -o m4_pow -
$ ./m4_pow
2^0 = 1
2^1 = 2
2^4 = 16

Надеюсь, это поможет!

person Benoit    schedule 06.06.2012

В последних версиях GCC (около 4.3) добавлена ​​возможность использовать GMP и MPFR для оптимизации времени компиляции путем оценки более сложных функций, которые являются постоянными. Такой подход делает ваш код простым и переносимым, и вы можете доверить компилятору всю тяжелую работу.

Конечно, есть пределы тому, что он может сделать. Вот ссылка на описание в журнале изменений, которое включает список функций, которые поддерживаются этим. "pow" - один из них.

person Chris Arguin    schedule 30.06.2009

Если вам просто нужно использовать значение во время во время компиляции, используйте научное обозначение например 1e2 для pow(10, 2)

Если вы хотите заполнить значения во время компиляции, а затем использовать их позже во время выполнения, просто используйте таблицу поиска, потому что есть только 23 различных степени числа 10, которые точно совпадают представляемый с двойной точностью

double POW10[] = {1., 1e1, 1e2, 1e3, 1e4, 1e5, 1e6, 1e7, 1e8, 1e9, 1e10,
1e11, 1e12, 1e13, 1e14, 1e15, 1e16, 1e17, 1e18, 1e19, 1e20, 1e21, 1e22};

Вы можете получить большую степень 10 во время выполнения из приведенной выше таблицы поиска, чтобы быстро получить результат без необходимости умножать на 10 снова и снова, но результатом будет просто значение, близкое к степени 10, например, когда вы используете 10eX с X > 22

double pow10(int x)
{
   if (x > 22)
      return POW10[22] * pow10(x - 22);
   else if (x >= 0)
      return POW10[x];
    else
        return 1/pow10(-x);
}

Если отрицательные показатели не нужны, то последнюю ветвь можно удалить.

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

person phuclv    schedule 22.04.2015

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

person David Thornley    schedule 30.06.2009

Воспроизведение bdonlan точное, но имейте в виду, что вы можете выполнить почти любую оптимизацию, которую вы выбрали в поле компиляции, если вы готовы разобрать и проанализировать код в своем собственном препроцессоре. В большинстве версий Unix тривиальная задача переопределить неявные правила, которые заставляют компилятор вызывать собственный шаг до того, как он попадет в компилятор.

person ojblass    schedule 01.07.2009