[boost] Re: Uploaded Prime.zip

From: Daniel Frey (daniel.frey_at_[hidden])
Date: 2003-09-18 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ß-Rahe-Straße 15, 52072 Aachen, Germany
fon: [phone], fax: [phone]
eMail: daniel.frey_at_[hidden], web: http://www.aixigo.de