Boost logo

Boost :

From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 2001-07-05 15:04:12

From: "Daryle Walker" <darylew_at_[hidden]>
> on 7/5/01 12:57 AM, Vesa Karvonen at vesa.karvonen_at_[hidden] wrote:
> > You can do many fun things with the preprocessor. For example:
> >
> >
> > turns into:
> >
> > 2 3 - 5 - 7 - - - 11 - 13 - - - 17 - 19 - - - 23 - - - - - 29 - 31
> I don't know whether to be proud or scared.
> What does "PRIME" look like? Does it depend on some top limit, or can it
> process all the way to ULONG_MAX?

#define IS_PRIME(X)\
#define IS_PRIME_F(X,Y)\
  , Y\
#define IS_PRIME_C(X,Y)\

#define PRIME(I,A,B)\

As you can see, PRIME ultimately relies on BOOST_PREPROCESSOR_INC /
BOOST_PREPROCESSOR_DEC so you would need O(N) macro definitions for the

However, it is possible to represent numbers using lists:


It is also possible to create a preprocessor macro that can manipulate numbers
that use the above list representation. E.g. the following:

    ADD( (9,(__,__))), (1,(7,(__,__))) )

would turn into:


So, it is possible to manipulate numbers that can exceed ULONG_MAX. (You can
turn such numbers into literals by using TOKENIZE.)

The real problem comes when you need to test whether a particular number is a
prime. In order to do this, you may need to perform quite a few iterations of
WHILE. The number of prime numbers less than N grows as O(N/log(N)). A simple
method for testing if a number N is prime is to attempt to divide it with all
primes smaller than sqrt(N). This would result in O(sqrt(N)/log(N)) divides
and you would therefore need O(sqrt(N)/log(N)) repetitions of the WHILE
primitive, because the preprocessor does not support recursion. Since at least
some preprocessors seem to be able to handle (simulated) recursion up to a
depth of 256 and beyond, it should be feasible to go up to 16-bit numbers.

Boost list run by bdawes at, gregod at, cpdaniel at, john at