views:

1031

answers:

6

Is it possible to compute pow(10,x) at compile time?

I've got a processor without floating point support and slow integer division. I'm trying to perform as many calculations as possible at compile time. I can dramatically speed up one particular function if I pass both x and C/pow(10,x) as arguments (x and C are always constant integers, but they are different constants for each call). I'm wondering if I can make these function calls less error prone by introducing a macro which does the 1/pow(10,x) automatically, instead of forcing the programmer to calculate it?

Is there a pre-processor trick? Can I force the compiler optimize out the library call?

+15  A: 

There are very few values possible before you overflow int (or even long). For clarities sake, make it a table!

edit: If you are using floats (looks like you are), then no it's not going to be possible to call the pow() function at compile time without actually writing code that runs in the make process and outputs the values to a file (such as a header file) which is then compiled.

Bill K
Inspired! For powers of a known base. That aren't decimals. :)
Michael Bray
C and x are related in such a way that we won't overflow: given a value v, x is chosen so that 0.1 <= v/pow(10,x) < 1, and C is set to 32768*v.
AShelly
what you meant to say is `total = (total<<1) + (total<<3)`And most of compiler can do that automatically when you use `total *= 10`
leiz
@leiz - what? What I meant is that C is a 1.15 fixed-point representation of a number between 0.1 and 1. x is always an integer.
AShelly
There is no need to use a table. For integers you can use the E notation, e.g. 1.0E5.
quinmars
+1  A: 

Unfortunately, you can't use the preprocessor to precalculate library calls. If x is integral you could write your own function, but if it's a floating-point type I don't see any good way to do this.

David Thornley
+13  A: 

GCC will do this at a sufficiently high optimization level (-O1 does it for me). For example:

#include <math.h>

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

Compiles at -O1 -m32 to:

        .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

This works without the cast as well - of course, you do get a floating-point load instruction in there, as the Linux ABI passes floating point return values in FPU registers.

bdonlan
Nice. I'm wondering how they check if pow is a pure function or not in a reasonable compile time.Maybe they have a list of known functions that are so?
akappa
some of the math functions are most likely compiler built-in; also, GCC has a non-standard `pure` attribute for functions
Christoph
'pure' isn't sufficient for cross-compile unit optimization of this kind; and GCC will perform constant folding after inlining if they're in the same compilation unit. pure is mostly just a hint to the compiler that it doesn't need to invalidate the data in its registers.
bdonlan
I hate to get into lexical parsers of c code but you can in theory write your own preprocessor to have exact control of optimizations.
ojblass
Not really a preprocessor so much as a precompiler - you'd have to deal with the possibility of local function pointers shadowing the global pow() etc
bdonlan
+6  A: 

You can do it with Boost.Preprocessor:

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

Code:

#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)};
e.tadeu
unfortunately I am using c only.
AShelly
However the OP asked for a C solution, and Boost is a C++ library
Dave Rigby
But you can use it with C (the Boost.Preprocessor library), it is preprocessor only, I checked it ;)Only configure your include directory and include it!
e.tadeu
+2  A: 

Recent versions of GCC ( around 4.3 ) added the ability to use GMP and MPFR to do some compile-time optimizations by evaluating more complex functions that are constant. That approach leaves your code simple and portable, and trust the compiler to do the heavy lifting.

Of course, there are limits to what it can do. Here's a link to the description in the changelog, which includes a list of functions that are supported by this. 'pow' is one them.

Chris Arguin
A: 

bdonlan's replay is spot on but keep in mind that you can perform nearly any optimization you chose on the compile box provided you are willing to parse and analyze the code in your own custom preprocessor. It is a trivial task in most version of unix to override the implicit rules that call the compiler to call a custom step of your own before it hits the compiler.

ojblass