0

Just for personal study and better understanding of C code preprocessor :

I am wondering if it is possible to implement Fibonacci function by preprocessor directives in C language.

Normal definition of Fibonacci function could be:

int f(int i) {  // i should be non-negative integer
    if (i <= 1) {
        return 1;
    }
    return f(i - 1) + f(i - 2);
}

The approach of using the template metaprogramming technique in C++ is not what I need.

It seems that it is not possible to perform recursive calculations by using the code preprocessor?

BinChen
  • 23
  • 11
  • 3
    Why do you want to do it with a macro? – klutt Apr 16 '21 at 10:56
  • You don't need the `if ... else` construct to generate a Fibonacci sequence. You start with two predefined values. – Weather Vane Apr 16 '21 at 10:58
  • In practice, Fibionacci grows very quickly. You want some [memoization](https://en.wikipedia.org/wiki/Memoization) and you should use some [arbitrary precision arithmetic](https://en.wikipedia.org/wiki/Arbitrary-precision_arithmetic) library such as [GMPlibb](http://gmplib.org/) – Basile Starynkevitch Apr 16 '21 at 10:59
  • 1
    A 64-bit integer can store up to the 94th term. – Weather Vane Apr 16 '21 at 11:01
  • Please explain -in more than one paragraph of written English- why you need to use macros and what for. Refer to [this C reference website](https://en.cppreference.com/w/c) – Basile Starynkevitch Apr 16 '21 at 11:12
  • 2
    General advice. Don't use macros when you can use a function. – klutt Apr 16 '21 at 11:23
  • 1
    I suppose this is for fun. [This code](https://gist.github.com/DavidBuchanan314/b9230fe7d335a1caf90483dbb00a5375) implements a Mandelbrot calculation using only the preprocessor, pretty fun stuff BTW. – Jabberwocky Apr 16 '21 at 11:27
  • 1
    The most relevant question, already asked, but deserving of underlining, is why use macros? Also if you want C, present C style code not python, it would take you 30 seconds `return (i <= 1) ? 1 : fib(i - 1) + fib(i - 2);` – anastaciu Apr 16 '21 at 11:29
  • From a time complexity point of view, recursion surely must be about the worst possible way to calculate the Fibonacci sequence, being O(exp(n)). – Ian Abbott Apr 16 '21 at 12:07
  • 3
    @klutt: OP does not say they want to implement the Fibonacci function with a macro. They ask whether it is possible, which indicates only that they want to know, not that they want to do it. Often understanding the capabilities of various tools is useful for understanding them, learning more, inspiring creativity, and knowing what is available in future situations. And they ask whether it is possible with preprocessor directives, not with macros alone. – Eric Postpischil Apr 16 '21 at 12:16
  • 2
    @EricPostpischil I totally agree. However, before OP edited it, the question looked quite different. – klutt Apr 16 '21 at 12:55
  • I'm so sorry, it's really my problem. Thank you very much for your help~ @klutt – BinChen Apr 17 '21 at 03:00
  • I posted the question but then I discovered my inadequate expression, so I edited many times. I think I need more thinking before asking. Thank you~ @EricPostpischil – BinChen Apr 17 '21 at 03:04
  • @BinChen That's not a big problem. I just asked because the reason why you wonder can greatly impact how a proper answer would look like. – klutt Apr 17 '21 at 04:28

3 Answers3

3

I do not think macro in C can support recursive macro. But Fibonacci is possible macro. By using the fomular of nth number

#define Fibonacci(n) (POW(1+POW(5,1/2),n) - POW(1-POW(5,1/2),n))/POW(5,1/2)

Silver
  • 406
  • 2
  • 12
  • 2
    Well, you would need to define `POW`, and be careful that `1/2` doesn't get evaluated as `0`. – Ian Abbott Apr 16 '21 at 11:26
  • @Ian Abbott i agree, but this just an idea – Silver Apr 16 '21 at 12:19
  • I think this is a straight and very good way. But actually, I'm learning the C preprocessor and wondering if there exists a recursive solution to get some of the Fibonacci sequence before running. Thank you for your answer~ @Silver – BinChen Apr 17 '21 at 03:18
3

Recursive macros are not allowed in C or in C++.

Macros — just a text replacement, not computation

RoiS
  • 31
  • 2
  • It seems that it is not possible to perform recursive calculations by using the code pre-processor? – BinChen Apr 16 '21 at 11:15
  • 1
    To some extend it is possible to have recursive macro in C. See https://stackoverflow.com/a/12540675/4989451 – tstanisl Apr 16 '21 at 11:15
  • 3
    (a) Infinite recursion is not possible with macro replacement, but finite practical recursion is. (b) Macros substitute preprocessor tokens, not text. They can also stringize and concatenate. (c) The question asks about using preprocessor directives to evaluate the Fibonacci function, not just using macro replacement. So an answer must consider possibilities of using other directives, such as `#include`, which can be recursive. – Eric Postpischil Apr 16 '21 at 12:13
  • 1
    (I see OP edited their question; it originally asked only about macros. So (c) was not an issue when this answer was written.) – Eric Postpischil Apr 16 '21 at 13:48
  • 1
    And finally it is possible to implement Fibonacci function by preprocessor directives in C language (recursive includes and quite large file after preprocessing). – RoiS Apr 16 '21 at 14:22
  • I'm so sorry, it's really my problem. I posted the question but then I discovered my inadequate expression, so I edited many times. I think I need more thinking before asking. Thank you very much for your help~ @RoiS – BinChen Apr 17 '21 at 03:05
  • I think by reading your tips and some reference manual, I've gotten a better understanding of C macros. Thank you very much~ @EricPostpischil – BinChen Apr 17 '21 at 03:09
2

Using boost preprocessor's slots, and an iterative solution, with the macro I as input:

#ifndef INITIALIZE
#define INITIALIZE
# include <boost/preprocessor/slot.hpp>
# if I<=2
1
# else
#  define BOOST_PP_VALUE 2
#  include BOOST_PP_ASSIGN_SLOT(1)
#  define BOOST_PP_VALUE 1
#  include BOOST_PP_ASSIGN_SLOT(3)
#  define BOOST_PP_VALUE 1
#  include BOOST_PP_ASSIGN_SLOT(4)
#  include __FILE__
# endif
#else
#  define BOOST_PP_VALUE BOOST_PP_SLOT(1) + 1
#  include BOOST_PP_ASSIGN_SLOT(1)
#  define BOOST_PP_VALUE BOOST_PP_SLOT(3)
#  include BOOST_PP_ASSIGN_SLOT(2)
#  define BOOST_PP_VALUE BOOST_PP_SLOT(4)
#  include BOOST_PP_ASSIGN_SLOT(3)
#  define BOOST_PP_VALUE BOOST_PP_SLOT(2) + BOOST_PP_SLOT(3)
#  include BOOST_PP_ASSIGN_SLOT(4)
# if I==BOOST_PP_SLOT(1)
BOOST_PP_SLOT(4)
# else
#  include __FILE__
# endif
#endif

Demo: http://coliru.stacked-crooked.com/a/c399d11dedc306ca

H Walters
  • 2,634
  • 1
  • 11
  • 13