
Boost : 
From: Vesa Karvonen (vesa.karvonen_at_[hidden])
Date: 20010705 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 16bit numbers.
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk