Macro expansion

[Sjouke Burry]

f0 1
f1 1
f2 2
f3 3
f4 5
f5 8
f6 13
f7 21
f8 34
f9 55
f10 89 what do you mean:55?????????????????

Usually, one sets F(0) = 0 and F(1) = 1. Then F(n) is the coefficient
of x in the linear representative of x^n modulo x^2 - x - 1 (see HAKMEM
item 12).

-- [mdw]

fibionachi can start with any set of two ints, however OP
defined the start as: i < 2 ? 1 :
meaning f0=1 f1=1

 

[Ben Pfaff]

Now, I have simplified the recursion:

static int f( int const i ){ return i < 10 ? 720 : 1 + f( i - 1 ); }
int main( void ){ return f( 10 ); }

At least in this case, gcc will eliminate f (with certain options)
and generate:

main:
(...)
MOVL 721, %EAX
(...)
RET

This shows that it might be possible for a C compiler to
calculate the Fibonacci numbers at compile time, too,
without the preprocessor.

One difference is that Fibonacci numbers generated by the
preprocessor could (presumably) be used in initializers and other
constant expressions. Functions calls cannot appear in constant
expressions.

 

[Stefan Ram]

One difference is that Fibonacci numbers generated by the
preprocessor could (presumably) be used in initializers and other
constant expressions. Functions calls cannot appear in constant
expressions.

The following language change might be more safe than the
one proposed in the OP:

static static int example( int const i ){ return i + 1; }

A static-static function call expression MUST BE evaluated
at compile time by the compiler and the compiler MUST
issue an error message if it cannot do this.

Then, given that f is a static-static function and
i_(0), i_(1), ... i(n-1) already are compile-time constants,

f( i_(0), i_(1), ..., i_(n-1) )

also is a compile time constant.

Evaluating a static-static function call should not be
that hard for a compiler, since it can compile the function
and then call it with the argument values already known.
(Ok, assuming it is not a cross compiler! - But even a
cross compiler can do this, when it is the programmers
duty to keep the result portable.)

I am not seriously suggesting this change to the C language,
I only want to say that this would allow the OP to do his
calculation at compile time, while it might be more safe
than a preprocessor extension.

 

[Seebs]

Man I _really_ disagree with this. "Powerful" in this case means
write-only code.

If we take the above spec as literal, it turns out that there are virtually
no programs which would be affected by it.

Please, C standards people, don't do it!

I am pretty sure that the entire C standards community is populated by
people who are legally allowed to dress themselves, and that as such,
there is no risk of any of sandeep's recent proposals being accepted.

-s

 

[Nick]

The following language change might be more safe than the
one proposed in the OP:

static static int example( int const i ){ return i + 1; }

A static-static function call expression MUST BE evaluated
at compile time by the compiler and the compiler MUST
issue an error message if it cannot do this.

Then, given that f is a static-static function and
i_(0), i_(1), ... i(n-1) already are compile-time constants,

f( i_(0), i_(1), ..., i_(n-1) )

also is a compile time constant.

Evaluating a static-static function call should not be
that hard for a compiler, since it can compile the function
and then call it with the argument values already known.
(Ok, assuming it is not a cross compiler! - But even a
cross compiler can do this, when it is the programmers
duty to keep the result portable.)

I am not seriously suggesting this change to the C language,
I only want to say that this would allow the OP to do his
calculation at compile time, while it might be more safe
than a preprocessor extension.

One reason you may not want to do this is that you need to build an
entire C interpreter into your compiler.

You can't just spin off the code into a skeleton, compile and run it and
get the value back, as you might be compiling on one machine for one of
a completely different architecture. If your function contains a
sizeof, for example, you'll get the wrong answer.

As many have said, if you want to do more than the standard preprocessor
allows, use another - there are plenty around.

 

[Ian Collins]

FYI:

// fib.c
#include<stdio.h>
#include<chaos/preprocessor.h>

#define FIB(n) \
CHAOS_PP_ARBITRARY_DEMOTE( \
CHAOS_PP_VARIADIC_ELEM( \
2, \
CHAOS_PP_EXPR(CHAOS_PP_WHILE_X( \
20, \
FIB_P, FIB_O, \
CHAOS_PP_ARBITRARY_DEC( \
CHAOS_PP_IIF(CHAOS_PP_IS_VARIADIC(n))( \
n, \
CHAOS_PP_ARBITRARY_PROMOTE(n) \
) \
), \
(0), (1) \
)) \
) \
) \
/**/
#define FIB_P(s, n, a, b) \
CHAOS_PP_ARBITRARY_BOOL(n) \
/**/
#define FIB_O(s, n, a, b) \
CHAOS_PP_ARBITRARY_DEC(n), b, CHAOS_PP_ARBITRARY_ADD(a, b) \
/**/

int main(void) {
printf(CHAOS_PP_STRINGIZE(FIB(500)) "\n");
return 0;
}

The program above computes the 500th Fibonacci number with the
preprocessor. It takes about 20 seconds to compile with GCC on the Linux
VM that I'm running on a mid-range machine.

A C++ solution is somewhat shorter, but this only works over the range
of long long. It does however produce a compile time constant, which
may be closer to the OP's intent:

void f( size_t );

template <unsigned N>
struct Fib
{
static const size_t value = Fib<N-1>::value+Fib<N-2>::value;
};

template <>
struct Fib<1> { enum { value = 1 }; };

template <>
struct Fib<0> { enum { value = 0 }; };

int main()
{
int n[Fib<10>::value];

f( Fib<65>::value );
}

 

[Paul Mensonides]

On 11/20/10 10:31 PM, Paul Mensonides wrote:
[snip]

The program above computes the 500th Fibonacci number with the
preprocessor. It takes about 20 seconds to compile with GCC on the
Linux VM that I'm running on a mid-range machine.

A C++ solution is somewhat shorter, but this only works over the range
of long long. It does however produce a compile time constant, which
may be closer to the OP's intent:

Sure, and, if you wanted to, you could define arbitrary-precision
values. In C++0x, you can do it even better with generalized constant
expressions. However, I was restricting my comments to C. More
importantly, the above was simply a demonstration that it *could* be
done, not that it *should* be done. I'd personally find it difficult to
find a context in typical programming where the Fibonacci numbers are
useful--even at runtime--except in a highly-specialized domain. However
contrived it might be as an example, it does serve to illustrate several
important concepts (e.g. the requirement for either iteration or
recursion to compute).

Regards,
Paul Mensonides

 

[Tim Rentsch]

[snip]

Look, I am writing a Masters thesis and my subject of expertise is "The
development of the ISO C Standard". [snip]

Have any of your thesis advisors read your postings in this
newsgroup and the various responses to them? Maybe you could
ask one of them to vouch for you.