 # Boost :

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: +49 (0)241 936737-42, fax: +49 (0)241 936737-99
eMail: daniel.frey_at_[hidden], web: http://www.aixigo.de
```