 # Boost :

From: Stephen Nutt (snutt_at_[hidden])
Date: 2003-09-18 21:25:26

but using enums directly. Makes a BIG improvement. I'll update when I've
made the changes, and some others I have in mind. (BTW, uses a little over
half the memory in half the time when used with another change I made!)

The square root template I agree is not optimised. However this shouldn't
present a problem as only one square root is used for each prime candidate.
I was actually hoping to breaking both power and root out into a separate
file, perhaps adding a floating point version (not sure how feasible that
would be) so fractions and negative powers could be passed.

Stephen

----- Original Message -----
From: "Daniel Frey" <daniel.frey_at_[hidden]>
To: <boost_at_[hidden]>
Sent: Thursday, September 18, 2003 9:22 AM

> 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:

>
> 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
>
>
> _______________________________________________
> Unsubscribe & other changes:
http://lists.boost.org/mailman/listinfo.cgi/boost