
Boost : 
From: Daniel Frey (daniel.frey_at_[hidden])
Date: 20030918 08:22:37
Stephen Nutt wrote:
> I've uploaded Prime.zip to yahoo. It contains two files. The first one
> Please send feedback. If someone can figure out how to do this with
> Fermat's little theorem, it may be possible to do even better when
> generating prime numbers.
I had a look at it and I have some concerns about the implementation. I
think that speed is an issue as you cannot predict how a project is
going to use your templates. Thus, you should attempt to make them as
fast as possible. One thing that might be worth trying is this:
http://tinyurl.com/nt06
Another way to speed things up might be an optimized version for
square_root, something like:
// Warning: Untested!
template< unsigned x > struct square_root
{
private:
enum {
v0 = ( x >= 1<<30 ) ? 1<<15 : 0,
v1 = v0 + ( ( x  v0*v0 >= 1<<28 ) ? 1<<14 : 0 ),
v2 = v1 + ( ( x  v1*v1 >= 1<<26 ) ? 1<<13 : 0 ),
v3 = v2 + ( ( x  v2*v2 >= 1<<24 ) ? 1<<12 : 0 ),
v4 = v3 + ( ( x  v3*v3 >= 1<<22 ) ? 1<<11 : 0 ),
v5 = v4 + ( ( x  v4*v4 >= 1<<20 ) ? 1<<10 : 0 ),
v6 = v5 + ( ( x  v5*v5 >= 1<<18 ) ? 1<<9 : 0 ),
v7 = v6 + ( ( x  v6*v6 >= 1<<16 ) ? 1<<8 : 0 ),
v8 = v7 + ( ( x  v7*v7 >= 1<<14 ) ? 1<<7 : 0 ),
v9 = v8 + ( ( x  v8*v8 >= 1<<12 ) ? 1<<6 : 0 ),
v10 = v9 + ( ( x  v9*v9 >= 1<<10 ) ? 1<<5 : 0 ),
v11 = v10 + ( ( x  v10*v10 >= 1<<8 ) ? 1<<4 : 0 ),
v12 = v11 + ( ( x  v11*v11 >= 1<<6 ) ? 1<<3 : 0 ),
v13 = v12 + ( ( x  v12*v12 >= 1<<4 ) ? 1<<2 : 0 ),
v14 = v13 + ( ( x  v13*v13 >= 1<<2 ) ? 1<<1 : 0 ),
v15 = v14 + ( ( x  v14*v14 >= 1<<1 ) ? 1<<0 : 0 )
};
public:
enum {
value = v15,
remainer = x  value*value
};
};
This avoids recursions and unnecessary instantiations. You might want to
run some benchmarks for it, keeping an eye on both the compile time and
the memory used by the compiler.
Regards, Daniel
 Daniel Frey aixigo AG  financial training, research and technology SchloßRaheStraße 15, 52072 Aachen, Germany fon: +49 (0)241 93673742, fax: +49 (0)241 93673799 eMail: daniel.frey_at_[hidden], web: http://www.aixigo.de
Boost list run by bdawes at acm.org, gregod at cs.rpi.edu, cpdaniel at pacbell.net, john at johnmaddock.co.uk