Constant expressions

Discussion in 'C Programming' started by jacob navia, Oct 14, 2011.

  1. jacob navia

    jacob navia Guest

    Continuing with my tutorial about C I have added a small text
    about constant expressions.

    Comments welcome.
    --------------------------------------------------------------

    Constant expressions
    -------------------

    The standard defines constant expressions as follows:

    A constant expression can be evaluated during translation rather than
    runtime, and accordingly may be used in any place that a constant may
    be.

    Constant expressions can have values of the following type:

    o Arithmetic. Any arithmetic operations are allowed. If floating point
    is used the precision of the calculations should be at least the same
    as in the run time environment.

    o A null pointer constant.

    o The address of an object with global scope. Optionally an integer
    offset can be added to the address.

    Since constant expressions are calculated during compilation, even
    inefficient algorithms are useful since the execution time is not
    affected.

    For instance Hallvard B Furuseth proposed (in [1]) a set of clever
    macros to calculate the logarithm base 2 of a number during compilation:

    /*
    * Return (v ? floor(log2(v)) : 0) when 0 <= v < 1<<[8, 16, 32, 64].
    * Inefficient algorithm, intended for compile-time constants.
    */
    #define LOG2_8BIT(v) (8 - 90/(((v)/4+14)|1) - 2/((v)/2+1))
    #define LOG2_16BIT(v) (8*((v)>255) + LOG2_8BIT((v) >>8*((v)>255)))
    #define LOG2_32BIT(v) \
    (16*((v)>65535L) + LOG2_16BIT((v)*1L >>16*((v)>65535L)))
    #define LOG2_64BIT(v)\
    (32*((v)/2L>>31 > 0) \
    + LOG2_32BIT((v)*1L >>16*((v)/2L>>31 > 0) \
    >>16*((v)/2L>>31 > 0)))


    Clever isn't it?

    So much clever that I have been unable to understand how they work. I
    just tested this with the following program:

    #include <math.h>
    #include <stdio.h>
    int main(void)
    {
    printf("LOG2_32BIT(35986)=%ld\n",LOG2_32BIT(35986));
    printf("log2(35986.0)=%g\n",log2(35986.0));
    }
    OUTPUT:
    LOG2_32BIT(35986)=15
    log2(35986.0)=15.1351

    What is also interesting is that lcc-win receives from the preprocessor
    the result of the macro expansion. Here is it, for your amusement
    (Of course that is a single huge line that I had to cut in several
    places to make it fit the text:

    #line 17 "tlog2.c"
    int main(void)
    {
    printf("LOG2_32BIT(35986)=%ld\n",(16*((35986)>65535L) +
    (8*(((35986)*1L >>16*((35986)>65535L))>255) +(8 - 90/
    (((((35986)*1L >>16*((35986)>65535L)) >>8*(((35986)*
    1L >>16*((35986)>65535L))>255))/4+14)|1) - 2/((((35986)*
    1L >>16*((35986)>65535L)) >>8*(((35986)*1L >>16*((35986)
    >65535L))>255))/2+1)))));



    The compiler calculates all those operations during compilation, and
    outputs the 15, that is stuffed into a register as an argument for the
    printf call. Instead of calling an expensive floating point library
    function you get the result with no run time penalty.


    ---
    [1] In a message to the comp.lang.c discussion group posted on June 28th
    2006, 4:37 pm.
    You can find the original message in:

    https://groups.google.com/group/comp.lang.c/msg/706324f25e4a60b0?hl=en\&
     
    jacob navia, Oct 14, 2011
    #1
    1. Advertising

  2. jacob navia

    BartC Guest

    "jacob navia" <> wrote in message
    news:j7a99l$23e$...

    > int main(void)
    > {
    > printf("LOG2_32BIT(35986)=%ld\n",(16*((35986)>65535L) +
    > (8*(((35986)*1L >>16*((35986)>65535L))>255) +(8 - 90/
    > (((((35986)*1L >>16*((35986)>65535L)) >>8*(((35986)*
    > 1L >>16*((35986)>65535L))>255))/4+14)|1) - 2/((((35986)*
    > 1L >>16*((35986)>65535L)) >>8*(((35986)*1L >>16*((35986)
    > >65535L))>255))/2+1)))));

    >
    >
    > The compiler calculates all those operations during compilation, and
    > outputs the 15, that is stuffed into a register as an argument for the
    > printf call. Instead of calling an expensive floating point library
    > function you get the result with no run time penalty.


    My gcc seems to compile log2(35986.0) as a constant anyway, which is what
    one might expect. And that's even without optimising.

    --
    Bartc
     
    BartC, Oct 14, 2011
    #2
    1. Advertising

  3. On 14.10.2011 23:24, jacob navia wrote:

    > For instance Hallvard B Furuseth proposed (in [1]) a set of clever
    > macros to calculate the logarithm base 2 of a number during compilation:
    >
    > /*
    > * Return (v ? floor(log2(v)) : 0) when 0 <= v < 1<<[8, 16, 32, 64].
    > * Inefficient algorithm, intended for compile-time constants.
    > */
    > #define LOG2_8BIT(v) (8 - 90/(((v)/4+14)|1) - 2/((v)/2+1))
    > #define LOG2_16BIT(v) (8*((v)>255) + LOG2_8BIT((v) >>8*((v)>255)))
    > #define LOG2_32BIT(v) \
    > (16*((v)>65535L) + LOG2_16BIT((v)*1L >>16*((v)>65535L)))
    > #define LOG2_64BIT(v)\
    > (32*((v)/2L>>31 > 0) \
    > + LOG2_32BIT((v)*1L >>16*((v)/2L>>31 > 0) \
    > >>16*((v)/2L>>31 > 0)))

    >
    > Clever isn't it?
    >
    > So much clever that I have been unable to understand how they work.


    LOG2_8BIT is a rational function approximation of the log - it is not
    identical to the log and gives false results for x = 0, or for x > 255,
    but only then. That is, it matches the output of log(x) by properly
    tweaking the coefficients.

    LOG2_16 simply uses the functional equation of the log, namely

    log(x * b) = log(b) + log(x)

    and in this case, b = 256. The same goes for LOG2_32 and LOG2_64 which
    simply extend the game to 64 bit by factoring more and more powers out.

    Greetings,
    Thomas
     
    Thomas Richter, Oct 15, 2011
    #3
  4. jacob navia

    jacob navia Guest

    Le 15/10/11 01:47, Thomas Richter a écrit :
    >>
    >> Clever isn't it?
    >>
    >> So much clever that I have been unable to understand how they work.

    >
    > LOG2_8BIT is a rational function approximation of the log - it is not
    > identical to the log and gives false results for x = 0, or for x > 255,
    > but only then. That is, it matches the output of log(x) by properly
    > tweaking the coefficients.
    >
    > LOG2_16 simply uses the functional equation of the log, namely
    >
    > log(x * b) = log(b) + log(x)
    >
    > and in this case, b = 256. The same goes for LOG2_32 and LOG2_64 which
    > simply extend the game to 64 bit by factoring more and more powers out.
    >


    Well, you are more clever than me... Thanks and I will add your
    explanation to the text (of course citing you and not implying
    that I figure it out!)

    Thanks again.
     
    jacob navia, Oct 15, 2011
    #4
  5. jacob navia

    jacob navia Guest

    Le 14/10/11 23:50, BartC a écrit :
    > "jacob navia" <> wrote in message
    > news:j7a99l$23e$...
    >
    >> int main(void)
    >> {
    >> printf("LOG2_32BIT(35986)=%ld\n",(16*((35986)>65535L) +
    >> (8*(((35986)*1L >>16*((35986)>65535L))>255) +(8 - 90/
    >> (((((35986)*1L >>16*((35986)>65535L)) >>8*(((35986)*
    >> 1L >>16*((35986)>65535L))>255))/4+14)|1) - 2/((((35986)*
    >> 1L >>16*((35986)>65535L)) >>8*(((35986)*1L >>16*((35986)
    >> >65535L))>255))/2+1)))));

    >>
    >>
    >> The compiler calculates all those operations during compilation, and
    >> outputs the 15, that is stuffed into a register as an argument for the
    >> printf call. Instead of calling an expensive floating point library
    >> function you get the result with no run time penalty.

    >
    > My gcc seems to compile log2(35986.0) as a constant anyway, which is
    > what one might expect. And that's even without optimising.
    >

    Sure, but you wouldn't want to say to beginners that log2(35986)
    is a constant expression ...

    :)

    P.S. Not all compilers do that. Microsoft compiler doesn't, lcc-win
    doesn't. I started implementing it some time ago but didn't finish it.
     
    jacob navia, Oct 15, 2011
    #5
  6. The integer to log2 problem is one of many hackers' delight in computing.

    I'll give an example that can be done in call by name/vale/address/reference for this trick.

    Suppose that the input x is in the form of 64 bits in width, i.e. 384db in the signal strength,and the question is how to obtain an integer y= log2(x) in an integer in the range 0 to 63. Of course one should remember that log2(1)=0.

    1. First check no negative or zero input in the beginning.
    2. Now x is an integer that ranges from 1 to ( 2's power of 64 -1), thus one has to determine y in the range 1,2,...63.

    3. A binary search like method is enough!
     
    88888 dihedral, Oct 15, 2011
    #6
  7. pete <> writes:
    [...]
    > ((0.0 + 0.0) / 2.0) does not fit the definition
    > of "arithmetic constant expression".
    >
    > (0.0 + 0.0) is not one of the kinds of operands
    > that an "arithmetic constant expression" is described as having.


    Hmm. A literal reading of C99 6.6p8 does seem to imply that:

    An _arithmetic constant expression_ shall have arithmetic
    type and shall only have operands that are integer constants,
    floating constants, enumeration constants, character constants,
    and sizeof expressions. Cast operators in an arithmetic constant
    expression shall only convert arithmetic types to arithmetic
    types, except as part of an operand to a sizeof operator whose
    result is an integer constant.

    But I find it hard to believe that that was the intent. It implies that
    1.0 / 3.0 is an arithmetic constant expression, but (1.0) / 3.0 isn't.

    Is this a flaw in the standard, or am I missing something?

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Oct 18, 2011
    #7
  8. Keith Thompson <> wrote:
    > pete <> writes:
    >
    > [...]
    >
    > > ((0.0 + 0.0) / 2.0) does not fit the definition
    > > of "arithmetic constant expression".

    >
    > > (0.0 + 0.0) is not one of the kinds of operands that
    > > an "arithmetic constant expression" is described as having.


    In what way is (0.0 + 0.0) not a floating constant?

    > Hmm.  A literal reading of C99 6.6p8 does seem to imply that:
    >
    >     An _arithmetic constant expression_ shall have arithmetic
    >     type and shall only have operands that are integer constants,
    >     floating constants, enumeration constants, character constants,
    >     and sizeof expressions. Cast operators in an arithmetic
    > constant expression shall only convert arithmetic types to
    > arithmetic types, except as part of an operand to a sizeof
    > operator whose result is an integer constant.
    >
    > But I find it hard to believe that that was the intent.  It
    > implies that 1.0 / 3.0 is an arithmetic constant expression,
    > but (1.0) / 3.0 isn't.


    In what way? The parentheses in ( expression ) are syntax, not
    operators, in the same way that the comma in an argument-
    expression-list is just syntax, not an operator.

    A parenthesized expression is a primary expression. Its type
    and value are identical to those of the unparenthesized
    expression. It is an lvalue, a function designator, or a void
    expression if the unparenthesized expression is, respectively,
    an lvalue, a function designator, or a void expression.

    > ...am I missing something?


    Am I?

    It seems a greater argument would be that 42 is not an arithmetic
    constant expression since they 'shall only have operands...' and
    42 is not used as an operand. Not that I'm arguing that!

    --
    Peter
     
    Peter Nilsson, Oct 18, 2011
    #8
  9. Peter Nilsson <> writes:
    > Keith Thompson <> wrote:
    >> pete <> writes:
    >>
    >> [...]
    >>
    >> > ((0.0 + 0.0) / 2.0) does not fit the definition
    >> > of "arithmetic constant expression".

    >>
    >> > (0.0 + 0.0) is not one of the kinds of operands that
    >> > an "arithmetic constant expression" is described as having.

    >
    > In what way is (0.0 + 0.0) not a floating constant?


    A floating constant is a single floating-point literal; its grammar is
    defined in C99 6.4.4.2. 0.0 is a floating-constant; (0.0 + 0.0) is not.

    >> Hmm.  A literal reading of C99 6.6p8 does seem to imply that:
    >>
    >>     An _arithmetic constant expression_ shall have arithmetic
    >>     type and shall only have operands that are integer constants,
    >>     floating constants, enumeration constants, character constants,
    >>     and sizeof expressions. Cast operators in an arithmetic
    >> constant expression shall only convert arithmetic types to
    >> arithmetic types, except as part of an operand to a sizeof
    >> operator whose result is an integer constant.
    >>
    >> But I find it hard to believe that that was the intent.  It
    >> implies that 1.0 / 3.0 is an arithmetic constant expression,
    >> but (1.0) / 3.0 isn't.

    >
    > In what way? The parentheses in ( expression ) are syntax, not
    > operators, in the same way that the comma in an argument-
    > expression-list is just syntax, not an operator.


    (0.0 + 0.0) is an operand of the "/" operator. It's a parenthesized
    expression, not any of the permitted kinds of operand listed in
    the standard.

    > A parenthesized expression is a primary expression. Its type
    > and value are identical to those of the unparenthesized
    > expression. It is an lvalue, a function designator, or a void
    > expression if the unparenthesized expression is, respectively,
    > an lvalue, a function designator, or a void expression.
    >
    >> ...am I missing something?

    >
    > Am I?


    It doesn't say that a parenthesized expression is a constant
    expression if the unparenthesized expression is a constant
    expression.

    > It seems a greater argument would be that 42 is not an arithmetic
    > constant expression since they 'shall only have operands...' and
    > 42 is not used as an operand. Not that I'm arguing that!


    Hmm. Well, a hyper-literal reading might imply that, because 42
    has no operands, it *is* a constant expression; all its operands
    (of which there are none) qualify. But that reading also makes
    "x" a constant expression, where x is declared as a variable.

    I think that, rather than placing restrictions on operands, the
    definition should place those same restrictions on all primary
    expressions that are subexpressions of the expression.

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Oct 18, 2011
    #9
  10. jacob navia

    jacob navia Guest

    Le 18/10/11 01:04, pete a écrit :
    > jacob navia wrote:
    >
    >> Constant expressions can have values of the following type:
    >>
    >> o Arithmetic. Any arithmetic operations are allowed. If floating point
    >> is used the precision of the calculations
    >> should be at least the same
    >> as in the run time environment.

    >
    > ((0.0 + 0.0) / 2.0) does not fit the definition
    > of "arithmetic constant expression".
    >
    > (0.0 + 0.0) is not one of the kinds of operands
    > that an "arithmetic constant expression" is described as having.
    >

    Of course it is. The same as ((8+6)/2). Any kind of expressions are
    accepted, the only requirement is that the components of the
    expression should be constants

    For instance:
    #define NB_ELEM(Table) (sizeof(Table)/sizeof(table[0]))

    Most compilers simplify those expressions even if they are very
    complicated as shown in my example.
     
    jacob navia, Oct 18, 2011
    #10
  11. pete <> writes:
    > jacob navia wrote:
    >>
    >> Le 18/10/11 01:04, pete a écrit :
    >> > jacob navia wrote:
    >> >
    >> >> Constant expressions can have values of the following type:
    >> >>
    >> >> o Arithmetic. Any arithmetic operations are allowed. If floating point
    >> >> is used the precision of the calculations
    >> >> should be at least the same
    >> >> as in the run time environment.
    >> >
    >> > ((0.0 + 0.0) / 2.0) does not fit the definition
    >> > of "arithmetic constant expression".
    >> >
    >> > (0.0 + 0.0) is not one of the kinds of operands
    >> > that an "arithmetic constant expression" is described as having.
    >> >

    >> Of course it is. The same as ((8+6)/2). Any kind of expressions are
    >> accepted, the only requirement is that the components of the
    >> expression should be constants

    >
    > The more that I think about it,
    > the more inclined I am to believe
    > that I misinterpreted what the standard meant.


    I do think you misinterpreted what it *means*. I'm not convinced that
    you misinterpreted what it actually *says*.

    I'd like to see an interpretation of the literal words of the standard
    that make ``((0.0 + 0.0) / 2.0)'' -- or even ``(0)'` -- a constant
    expression. (I'm sure beyond reasonable doubt that they're intended to
    be; I just don't think the standard correctly expresses that intent.)

    --
    Keith Thompson (The_Other_Keith) <http://www.ghoti.net/~kst>
    "We must do something. This is something. Therefore, we must do this."
    -- Antony Jay and Jonathan Lynn, "Yes Minister"
     
    Keith Thompson, Oct 18, 2011
    #11
  12. jacob navia

    Tim Rentsch Guest

    Keith Thompson <> writes:

    > pete <> writes:
    > [...]
    >> ((0.0 + 0.0) / 2.0) does not fit the definition
    >> of "arithmetic constant expression".
    >>
    >> (0.0 + 0.0) is not one of the kinds of operands
    >> that an "arithmetic constant expression" is described as having.

    >
    > Hmm. A literal reading of C99 6.6p8 does seem to imply that:
    >
    > An _arithmetic constant expression_ shall have arithmetic
    > type and shall only have operands that are integer constants,
    > floating constants, enumeration constants, character constants,
    > and sizeof expressions. Cast operators in an arithmetic constant
    > expression shall only convert arithmetic types to arithmetic
    > types, except as part of an operand to a sizeof operator whose
    > result is an integer constant.
    >
    > But I find it hard to believe that that was the intent. It implies that
    > 1.0 / 3.0 is an arithmetic constant expression, but (1.0) / 3.0 isn't.
    >
    > Is this a flaw in the standard, or am I missing something?


    The Standard is guilty of sloppy language. Clearly when it talks
    about 'operands' in 6.6p8 the intended meaning is only those
    operands that are primitive, ie, not any larger expression. I
    think most people understand what is meant with no problem (and
    indeed the other meaning never occurs to them). If it were being
    voted on in comp.std.c, I would vote to clarify this paragraph
    (ie, that a clarifying change is warranted), but I don't think
    there is any question about what is meant; in other words, for
    purposes of comp.lang.c I think it's a non-issue.
     
    Tim Rentsch, Jan 25, 2012
    #12
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Christopher M. Lusardi
    Replies:
    1
    Views:
    4,136
  2. Martin Magnusson
    Replies:
    2
    Views:
    536
    John Harrison
    Oct 8, 2004
  3. Tor Erik Soenvisen
    Replies:
    14
    Views:
    593
    Tim Roberts
    Nov 23, 2006
  4. Replies:
    4
    Views:
    359
    Keith Thompson
    Dec 14, 2006
  5. Replies:
    13
    Views:
    13,035
    Kai-Uwe Bux
    Jan 22, 2007
Loading...

Share This Page