Re: [boost] Re: PREPROCESSOR library review

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:
[SNIP]
> > You can do many fun things with the preprocessor. For example:
> >
> > BOOST_PREPROCESSOR_REPEAT(30,PRIME,A,B)
> >
> > turns into:
> >
> > 2 3 - 5 - 7 - - - 11 - 13 - - - 17 - 19 - - - 23 - - - - - 29 - 31
> [TRUNCATE]
>
> 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)\
  ID( BOOST_PREPROCESSOR_EQUAL WHILE0(IS_PRIME_C,IS_PRIME_F,(2,X)) )
#define IS_PRIME_F(X,Y)\
  ( BOOST_PREPROCESSOR_INC(X)\
  , Y\
  )
#define IS_PRIME_C(X,Y)\
  MOD(X,Y,X)

#define PRIME(I,A,B)\
  BOOST_PREPROCESSOR_IF(IS_PRIME(ADD(0,I,2)),ADD(0,I,2),-)

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

However, it is possible to represent numbers using lists:

    (3,(1,(4,(1,(5,(9,(__,__)))))))

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:

    (2,(6,(__,__)))

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.